3 citations · 8 across the 17 of their papers we have counts for
20 papers
Finding d-Cuts in Claw-free Graphs
Jungho Ahn, Tala Eagling-Vose, Felicia Lucke +2
The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets and such that the edges between and form a m…
Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
Tala Eagling-Vose, Barnaby Martin, Daniel Paulusma +1
We continue the study of the recently-introduced C123-framework, for (simple) graph problems restricted to inputs specified by the forbidding of some finite set of subgraphs, to mo…
Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
Felicia Lucke, Ali Momeni, Daniël Paulusma +1
The d-Cut problem is to decide if a graph has an edge cut such that each vertex has at most d neighbours at the opposite side of the cut. If , we obtain the intensively studie…
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…
Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
Matthew Johnson, Barnaby Martin, Siani Smith +3
We show that Edge Multiway Cut (also called Multiterminal Cut) and Node Multiway Cut are NP-complete on graphs of maximum degree (also known as subcubic graphs). This improves…
Few Induced Disjoint Paths for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer , th…
Induced Disjoint Paths and Connected Subgraphs for -Free Graphs
Barnaby Martin, Daniël Paulusma, Siani Smith +1
Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. The Induced Disjoint Paths…
Colouring Generalized Claw-Free Graphs and Graphs of Large Girth: Bounding the Diameter
Barnaby Martin, Daniel Paulusma, Siani Smith
For a fixed integer, the -Colouring problem is to decide if the vertices of a graph can be coloured with at most colours for an integer , such that no two adjacent vertic…
Disjoint Paths and Connected Subgraphs for H-Free Graphs
Walter Kern, Barnaby Martin, Daniël Paulusma +2
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 deter…
Partitioning H-Free Graphs of Bounded Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +2
A natural way of increasing our understanding of NP-complete graph problems is to restrict the input to a special graph class. Classes of -free graphs, that is, graphs that do n…
Acyclic, Star, and Injective Colouring: Bounding the Diameter
Christoph Brause, Petr Golovach, Barnaby Martin +3
We examine the effect of bounding the diameter for well-studied variants of the Colouring problem. A colouring is acyclic, star, or injective if any two colour classes induce a for…
QCSP on Reflexive Tournaments
Benoit Larose, Petar Markovic, Barnaby Martin +3
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…
Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
Barnaby Martin, Daniel Paulusma, Siani Smith
For , a -colouring of is a mapping from to such that for any two non-adjacent vertices and . The -Colouring…
Hard Problems That Quickly Become Very Easy
Barnaby Martin, Daniël Paulusma, Siani Smith
A graph class is hereditary if it is closed under vertex deletion. We give examples of NP-hard, PSPACE-complete and NEXPTIME-complete problems that become constant-time solvable fo…
The complexity of L(p,q)-Edge-Labelling
Gaetan Berthe, Barnaby Martin, Daniel Paulusma +1
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially class…
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free Graphs
Jan Bok, Nikola Jedlickova, Barnaby Martin +3
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. Hence, every injec…