Skip to main content

Research Repository

Advanced Search

All Outputs (27)

Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs (2024)
Presentation / Conference Contribution
Lozin, V. V., Martin, B., Pandey, S., Paulusma, D., Siggers, M., Smith, S., & van Leeuwen, E. J. (2024, December). Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs. Presented at ISAAC, ISAAC 2024

For a fixed set H of graphs, a graph G is H-subgraph-free if G does not contain any H ∈ H as a (not necessarily induced) subgraph. A recent framework gives a complete classification on H-subgraph-free graphs (for finite sets H) for problems that are... Read More about Complexity framework for forbidden subgraphs II: Edge subdivision and the "H"-graphs.

Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs (2024)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2024, June). Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs. Presented at SWAT 2024, Helsinki, Finland

It is known that the weighted version of Edge Multiway Cut (also known as Multiterminal Cut) is NP-complete on planar graphs of maximum degree 3. In contrast, for the unweighted version, NP-completeness is only known for planar graphs of maximum degr... Read More about Edge Multiway Cut and Node Multiway Cut are hard for planar subcubic graphs.

Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs (2023)
Presentation / Conference Contribution
Johnson, M., Martin, B., Pandey, S., Paulusma, D., Smith, S., & Van Leeuwen, E. J. (2023, August). Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

For any finite set H = {H1,. .. , Hp} of graphs, a graph is H-subgraph-free if it does not contain any of H1,. .. , Hp as a subgraph. In recent work, meta-classifications have been studied: these show that if graph problems satisfy certain prescribed... Read More about Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs.

Few induced disjoint paths for H-free graphs (2022)
Presentation / Conference Contribution
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2022, May). Few induced disjoint paths for H-free graphs. Presented at ISCO 2022, Online

Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs... Read More about Few induced disjoint paths for H-free graphs.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2022)
Presentation / Conference Contribution
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k... Read More about Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs.

The Complexity of L(p,q)-Edge-Labelling (2022)
Presentation / Conference Contribution
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2022, March). The Complexity of L(p,q)-Edge-Labelling. Presented at The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), University of Jember, East Java

The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p,... Read More about The Complexity of L(p,q)-Edge-Labelling.

Partitioning H-free graphs of bounded diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P. A., Martin, B., Paulusma, D., & Smith, S. (2021, December). Partitioning H-free graphs of bounded diameter. Presented at 32nd International Symposium on Algorithms and Computation (ISAAC 2021), Fukuoka, Japan

A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of H-free graphs, that is, graphs that do not contain some graph H as an induced subgraph, have proven to be an ide... Read More about Partitioning H-free graphs of bounded diameter.

Acyclic, star and injective colouring: bounding the diameter (2021)
Presentation / Conference Contribution
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. Acyclic, star and injective colouring: bounding the diameter

We examine the effect of bounding the diameter for wellstudied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively.... Read More about Acyclic, star and injective colouring: bounding the diameter.

QCSP on reflexive tournaments (2021)
Presentation / Conference Contribution
Larose, B., Markovic, P., Martin, B., Paulusma, D., Smith, S., & Zivny, S. (2021, September). QCSP on reflexive tournaments. Presented at The 29th Annual European Symposium on Algorithms (ESA 2021), Lisbon / Online

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H1, . . . , Hn so th... Read More about QCSP on reflexive tournaments.

Disjoint paths and connected subgraphs for H-free graphs (2021)
Presentation / Conference Contribution
Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. Disjoint paths and connected subgraphs for H-free graphs

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint P... Read More about Disjoint paths and connected subgraphs for H-free graphs.

Injective colouring for H-free graphs (2021)
Presentation / Conference Contribution
Bok, J., Jedličková, N., Martin, B., Paulusma, D., & Smith, S. (2023, June). Injective colouring for H-free graphs. Presented at CSR 2021, Sochi

A function c : V (G) → {1, 2, . . . , k} is a k-colouring of a graph G if c(u) 6= c(v) whenever u and v are adjacent. If any two colour classes induce the disjoint union of vertices and edges, then c is called injective. Injective colourings are also... Read More about Injective colouring for H-free graphs.

Colouring graphs of bounded diameter in the absence of small cycles (2021)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & Smith, S. (2021, May). Colouring graphs of bounded diameter in the absence of small cycles. Presented at CIAC 2021, Virtual Event

For k ≥ 1, a k-colouring c of G is a mapping from V (G) to {1, 2, . . . , k} such that c(u) 6= c(v) for any two non-adjacent vertices u and v. The k-Colouring problem is to decide if a graph G has a k-colouring. For a family of graphs H, a graph G is... Read More about Colouring graphs of bounded diameter in the absence of small cycles.

Sherali-Adams and the binary encoding of combinatorial principles (2020)
Presentation / Conference Contribution
Dantchev, S., Ghani, A., & Martin, B. (2020, May). Sherali-Adams and the binary encoding of combinatorial principles. Presented at LATIN 2020, São Paulo, Brazil

We consider the Sherali-Adams ( SA ) refutation system together with the unusual binary encoding of certain combinatorial principles. For the unary encoding of the Pigeonhole Principle and the Least Number Principle, it is known that linear rank is r... Read More about Sherali-Adams and the binary encoding of combinatorial principles.

Acyclic, star and injective colouring: a complexity picture for H-free graphs (2020)
Presentation / Conference Contribution
Bok, J., Jedlickova, N., Martin, B., Paulusma, D., & Smith, S. (2020, September). Acyclic, star and injective colouring: a complexity picture for H-free graphs. Presented at ESA 2020, Pisa, Italy (Virtual Event)

A k-colouring c of a graph G is a mapping V(G) → {1,2,… k} such that c(u) ≠ c(v) whenever u and v are adjacent. The corresponding decision problem is Colouring. A colouring is acyclic, star, or injective if any two colour classes induce a forest, sta... Read More about Acyclic, star and injective colouring: a complexity picture for H-free graphs.

QCSP monsters and the demise of the chen conjecture (2020)
Presentation / Conference Contribution
Zhuk, D., & Martin, B. (2020, June). QCSP monsters and the demise of the chen conjecture. Presented at 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago

We give a surprising classification for the computational complexity of the Quantified Constraint Satisfaction Problem over a constraint language Γ, QCSP(Γ), where Γ is a finite language over 3 elements which contains all constants. In particular, su... Read More about QCSP monsters and the demise of the chen conjecture.

Colouring H-free graphs of bounded diameter (2019)
Presentation / Conference Contribution
Martin, B., Paulusma, D., & Smith, S. (2019, August). Colouring H-free graphs of bounded diameter. Presented at MFCS 2019, Aachen, Germany

The Colouring problem is to decide if the vertices of a graph can be coloured with at most k colours for an integer k, such that no two adjacent vertices are coloured alike. A graph G is H-free if G does not contain H as an induced subgraph. It is kn... Read More about Colouring H-free graphs of bounded diameter.

Resolution and the binary encoding of combinatorial principles (2019)
Presentation / Conference Contribution
Dantchev, S., Galesi, N., & Martin, B. (2019, July). Resolution and the binary encoding of combinatorial principles. Presented at Computational Complexity Conference, New Brunswick, New Jersey, USA

Res(s) is an extension of Resolution working on s-DNFs. We prove tight n (k) lower bounds for the size of refutations of the binary version of the k-Clique Principle in Res(o(log log n)). Our result improves that of Lauria, Pudlák et al. [27] who pro... Read More about Resolution and the binary encoding of combinatorial principles.

The complexity of disjunctive linear Diophantine constraints (2018)
Presentation / Conference Contribution
Bodirsky, M., Mamino, M., Martin, B., & Mottet, A. (2018, August). The complexity of disjunctive linear Diophantine constraints. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

We study the Constraint Satisfaction Problem CSP( A), where A is first-order definable in (Z;+,1) and contains +. We prove such problems are either in P or NP-complete.

Consistency for counting quantifiers (2018)
Presentation / Conference Contribution
Madelaine, F., & Martin, B. (2018, August). Consistency for counting quantifiers. Presented at 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)., Liverpool, UK

We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach f... Read More about Consistency for counting quantifiers.