The Matching Cut problem is to decide if the vertex set of a connected graph can be partitioned into two non-empty sets B and R such that the edges between B and R form a matching, that is, every vertex in B has at most one neighbour in R, and vice versa. If for some integer d ≥ 1, we allow every vertex in B to have at most d neighbours in R, and vice versa, we obtain the more general problem d-Cut. It is known that d-Cut is NP-complete for every d ≥ 1. However, for claw-free graphs, it is only known that d-Cut is polynomial-time solvable for d = 1 and NP-complete for d ≥ 3. We resolve the missing case d = 2 by proving NP-completeness. This follows from our more general study, in which we also bound the maximum degree. That is, we prove that for every d ≥ 2, d-Cut, restricted to claw-free graphs of maximum degree p, is constant-time solvable if p ≤ 2d+1 and NP-complete if p ≥ 2d+3. Moreover, in the former case, we can find a d-cut in linear time. We also show how our positive results for claw-free graphs can be generalized to S_{1^t,𝓁}-free graphs where S_{1^t,𝓁} is the graph obtained from a star on t+2 vertices by subdividing one of its edges exactly 𝓁 times.

Abstract For a set of graphs $${\mathcal {H}}$$ H , a graph G is $${\mathcal {H}}$$ H -subgraph-free if G does not contain any graph from $${{{\mathcal {H}}}}$$ H as a subgraph. We propose general and easy-to-state conditions on graph problems that explain a large set of results for $${\mathcal {H}}$$ H -subgraph-free graphs. Namely, a graph problem must be efficiently solvable on graphs of bounded treewidth, computationally hard on subcubic graphs, and computational hardness must be preserved under edge subdivision of subcubic graphs. Our meta-classification says that if a graph problem $$\Pi $$ Π satisfies all three conditions, then for every finite set $${{{\mathcal {H}}}}$$ H , it is “efficiently solvable” on $${{{\mathcal {H}}}}$$ H -subgraph-free graphs if $${\mathcal {H}}$$ H contains a disjoint union of one or more paths and subdivided claws, and $$\Pi $$ Π is “computationally hard” otherwise. We apply our meta-classification on many well-known partitioning, covering and packing problems, network design problems and width parameter problems to obtain a dichotomy between polynomial-time solvability and -completeness. For distance-metric problems, we obtain a dichotomy between almost-linear-time solvability and having no subquadratic-time algorithm (conditioned on some hardness hypotheses). Apart from capturing a large number of explicitly and implicitly known results in the literature, we also prove a number of new results. Moreover, we perform an extensive comparison between the subgraph framework and the existing frameworks for the minor and topological minor relations, and pose several new open problems and research directions.

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 completely characterizes the complexity of many problems on H -subgraph-free graphs. Hence, the complexity of Steiner Forest on H -subgraph-free graphs remained open. Our main results are four polynomial-time algorithms for different excluded graphs H that are central to further understand its complexity. We also study the complexity of Steiner Forest for graphs with a small c -deletion set, that is, a small set X of vertices such that each connected component of G − X has size at most c . For this parameter, we give two algorithms that we later employ as subroutines (including a faster algorithm when c = 1 , that is, the vertex cover number) and exhibit a dichotomy theorem.

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 Colouring . We give almost complete complexity classifications for Acyclic Colouring , Star Colouring and Injective Colouring on H -free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours k is fixed, that is, not part of the input. From our study it follows that for fixed k , the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs.

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 conditions, their complexity can be classified on classes of H-subgraph-free graphs. We continue this work and focus on problems that have polynomial-time solutions on classes that have bounded treewidth or maximum degree at most 3 and examine their complexity on H-subgraph-free graph classes where H is a connected graph. With this approach, we obtain comprehensive classifications for (Independent) Feedback Vertex Set, Connected Vertex Cover, Colouring and Matching Cut. This resolves a number of open problems. We highlight that, to establish that Independent Feedback Vertex Set belongs to this collection of problems, we first show that it can be solved in polynomial time on graphs of maximum degree 3. We demonstrate that, with the exception of the complete graph on four vertices, each graph in this class has a minimum size feedback vertex set that is also an independent set.

Abstract Paths $$P^1,\ldots ,P^k$$ P 1 , … , P k in a graph $$G=(V,E)$$ G = ( V , E ) are mutually induced if any two distinct $$P^i$$ P i and $$P^j$$ P j 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 $$(s_i,t_i)$$ ( s i , t i ) contains k mutually induced paths $$P^i$$ P i such that each $$P^i$$ P i starts from $$s_i$$ s i and ends at $$t_i$$ t i . This is a classical graph problem that is -complete even for $$k=2$$ k = 2 . We introduce a natural generalization, Induced Disjoint Connected Subgraphs: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

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. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti. Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-Induced Disjoint Paths is NP-complete. We prove new complexity results for k-Induced Disjoint Paths if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where k is part of the input.

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem \( \mathrm{QCSP}(\mathrm{H}) \) when \( \mathrm{H} \) is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components \( \mathrm{H}_1,\ldots ,\mathrm{H}_n \) so that there exists an edge from every vertex of \( \mathrm{H}_i \) to every vertex of \( \mathrm{H}_j \) if and only if \( i\lt j \) . We prove that if \( \mathrm{H} \) has both its initial and final strongly connected component (possibly equal) of size 1, then \( \mathrm{QCSP}(\mathrm{H}) \) is in \( \mathsf {NL} \) and otherwise \( \mathrm{QCSP}(\mathrm{H}) \) is \( \mathsf {NP} \) -hard.

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 H₁,…,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i < j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.

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 injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as $L(1,1)$-Labelling). A classical complexity result on Colouring is a well-known dichotomy for $H$-free graphs (a graph is $H$-free if it does not contain $H$ as an induced subgraph). In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We perform such a study and give almost complete complexity classifications for Acyclic Colouring, Star Colouring and Injective Colouring on $H$-free graphs (for each of the problems, we have one open case). Moreover, we give full complexity classifications if the number of colours $k$ is fixed, that is, not part of the input. From our study it follows that for fixed $k$ the three problems behave in the same way, but this is no longer true if $k$ is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs of multigraphs.

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, star forest or disjoint union of vertices and edges, respectively. Hence, every injective colouring is a star colouring and every star colouring is an acyclic colouring. The corresponding decision problems are Acyclic Colouring, Star Colouring and Injective Colouring (the last problem is also known as L(1,1)-Labelling). A classical complexity result on Colouring is a well-known dichotomy for H-free graphs, which was established twenty years ago (in this context, a graph is H-free if and only if it does not contain H as an induced subgraph). Moreover, this result has led to a large collection of results, which helped us to better understand the complexity of Colouring. In contrast, there is no systematic study into the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring despite numerous algorithmic and structural results that have appeared over the years. We initiate such a systematic complexity study, and similar to the study of Colouring we use the class of H-free graphs as a testbed. We prove the following results: 1) We give almost complete classifications for the computational complexity of Acyclic Colouring, Star Colouring and Injective Colouring for H-free graphs. 2) If the number of colours k is fixed, that is, not part of the input, we give full complexity classifications for each of the three problems for H-free graphs. From our study we conclude that for fixed k the three problems behave in the same way, but this is no longer true if k is part of the input. To obtain several of our results we prove stronger complexity results that in particular involve the girth of a graph and the class of line graphs.

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 known that Colouring is NP-complete for H-free graphs if H contains a cycle or claw, even for fixed k >= 3. We examine to what extent the situation may change if in addition the input graph has bounded diameter.