20 citations · 75 across the 44 of their papers we have counts for
56 papers
Graph Homomorphism, Monotone Classes and Bounded Pathwidth
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
In recent work by Johnson et al. (2022), a framework was described for the study of graph problems over classes specified by omitting each of a finite set of graphs as subgraphs. I…
Complexity Framework for Forbidden Subgraphs IV: The Steiner Forest Problem
Hans L. Bodlaender, Matthew Johnson, Barnaby Martin +5
We study Steiner Forest on -subgraph-free graphs, that is, graphs that do not contain some fixed graph as a (not necessarily induced) subgraph. We are motivated by a recent…
Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Matthew Johnson, Barnaby Martin, Sukanya Pandey +3
For any finite set of graphs, a graph is -subgraph-free if it does not contain any of as a subgraph. In recent work…
Complexity Framework for Forbidden Subgraphs II: Edge Subdivision and the "H"-graphs
Vadim Lozin, Barnaby Martin, Sukanya Pandey +4
For a fixed set of graphs, a graph is -subgraph-free if does not contain any as a (not necessarily induced) subgraph. A recently propo…
Complexity Framework For Forbidden Subgraphs I: The Framework
Matthew Johnson, Barnaby Martin, Jelle J. Oostveen +4
For any particular class of graphs, algorithms for computational problems restricted to the class often rely on structural properties that depend on the specific problem at hand. T…
Complexity Classification Transfer for CSPs via Algebraic Products
Manuel Bodirsky, Peter Jonsson, Barnaby Martin +2
We study the complexity of infinite-domain constraint satisfaction problems: our basic setting is that a complexity classification for the CSPs of first-order expansions of a struc…