Skip to main content

Research Repository

Advanced Search

Dr Barnaby Martin's Outputs (60)

Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem (2025)
Journal Article
Bodlaender, H. L., Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem. Journal of Computer and System Sciences, Article 103682. https://doi.org/10.1016/j.jcss.2025.103682

We study Steiner Forest on H-subgraph-free graphs, that is, graphs that do not contain some fixed graph H as a (not necessarily induced) subgraph. In contrast to the related Steiner Tree problem, Steiner Forest falls outside a recent framework that c... Read More about Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem.

Acyclic, star and injective colouring: A complexity picture for H-free graphs (2025)
Journal Article
Bok, J., Jedličková, N., Martin, B., Ochem, P., Paulusma, D., & Smith, S. (2025). Acyclic, star and injective colouring: A complexity picture for H-free graphs. Journal of Computer and System Sciences, 154, Article 103662. https://doi.org/10.1016/j.jcss.2025.103662

A (proper) colouring is acyclic, star, or injective if any two colour classes induce a forest, star forest or disjoint union of vertices and edges, respectively. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective... Read More about Acyclic, star and injective colouring: A complexity picture for H-free graphs.

Complexity Framework for Forbidden Subgraphs I: The Framework (2025)
Journal Article
Johnson, M., Martin, B., Oostveen, J. J., Pandey, S., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2025). Complexity Framework for Forbidden Subgraphs I: The Framework. Algorithmica, 87(3), 429-464. https://doi.org/10.1007/s00453-024-01289-2

For a set of graphs H, a graph G is H-subgraph-free if G does not contain any graph from H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for H-subgraph-free graphs. Namely, a grap... Read More about Complexity Framework for Forbidden Subgraphs I: The Framework.

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.

The Riis Complexity Gap for QBF Resolution (2024)
Journal Article
Beyersdorff, O., Clymo, J., Dantchev, S., & Martin, B. (2024). The Riis Complexity Gap for QBF Resolution. Journal on Satisfiability, Boolean Modeling and Computation, 15(1), 9-25. https://doi.org/10.3233/sat-231505

We give an analogue of the Riis Complexity Gap Theorem in Resolution for Quantified Boolean Formulas (QBFs). Every first-order sentence ϕ without finite models gives rise to a sequence of QBFs whose minimal refutations in tree-like QBF Resolution sys... Read More about The Riis Complexity Gap for QBF Resolution.

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.

Depth lower bounds in Stabbing Planes for combinatorial principles (2024)
Journal Article
Dantchev, S., Galesi, N., Ghani, A., & Martin, B. (2024). Depth lower bounds in Stabbing Planes for combinatorial principles. Logical Methods in Computer Science, 20(1), 1-19. https://doi.org/10.46298/lmcs-20%281%3A1%292024

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prov... Read More about Depth lower bounds in Stabbing Planes for combinatorial principles.

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.

The Complexity of L(p, q)-Edge-Labelling (2023)
Journal Article
Berthe, G., Martin, B., Paulusma, D., & Smith, S. (2023). The Complexity of L(p, q)-Edge-Labelling. Algorithmica, 85(11), 3406-3429. https://doi.org/10.1007/s00453-023-01120-4

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.

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs (2023)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

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.

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.

Few induced disjoint paths for H-free graphs (2022)
Journal Article
Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024

Paths in a graph are mutually induced if any two distinct and 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 of specified vertices contains k mutu... Read More about Few induced disjoint paths for H-free graphs.

QCSP Monsters and the Demise of the Chen Conjecture (2022)
Journal Article
Zhuk, D., & Martin, B. (2022). QCSP Monsters and the Demise of the Chen Conjecture. Journal of the ACM, 69(5), 1-44. https://doi.org/10.1145/3563820

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.

The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation (2022)
Journal Article
Carvalho, C., Madelaine, F., Martin, B., & Zhuk, D. (2023). The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation. ACM Transactions on Computational Logic, 24(1), Article 5. https://doi.org/10.1145/3568397

Let A be an idempotent algebra on a finite domain. By mediating between results of Chen [1] and Zhuk [2], we argue that if A satisfies the polynomially generated powers property (PGP) and B is a constraint language invariant under A (that is, in Inv(... Read More about The complexity of quantified constraints: collapsibility, switchability and the algebraic formulation.

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.

Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter (2022)
Journal Article
Martin, B., Paulusma, D., & Smith, S. (2022). Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter. Theoretical Computer Science, 931, 104-116. https://doi.org/10.1016/j.tcs.2022.07.034

For a fixed integer, the k-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 ind... Read More about Colouring generalized claw-free graphs and graphs of large girth: Bounding the diameter.

Partitioning H-free graphs of bounded diameter (2022)
Journal Article
Brause, C., Golovach, P., Martin, B., Paulusma, D., & Smith, S. (2022). Partitioning H-free graphs of bounded diameter. Theoretical Computer Science, 930, 37-52. https://doi.org/10.1016/j.tcs.2022.07.009

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.