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.

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.

Matching games naturally generalize assignment games, a well-known class of cooperative games. Interest in matching games has grown recently due to some breakthrough results and new applications. This state-of-the-art survey provides an overview of matching games and extensions, such as b-matching games and partitioned matching games; the latter originating from the emerging area of international kidney exchange. In this survey we focus on computational complexity aspects of various game-theoretical solution concepts, such as the core, nucleolus and Shapley value, when the input is restricted to a matching game or one of its variants.

Abstract We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs $$ H_{1} $$ H 1 and $$H_2$$ H 2 for all but six pairs $$(H_1,H_2)$$ ( H 1 , H 2 ) . Schweitzer had previously shown that the number of open cases was finite, but without specifying the open cases. Grohe and Schweitzer proved that Graph Isomorphism is polynomial-time solvable on graph classes of bounded clique-width. Our work combines known results such as these with new results. By exploiting a relationship between Graph Isomorphism and clique-width, we simultaneously reduce the number of open cases for boundedness of clique-width for $$(H_1,H_2)$$ ( H 1 , H 2 ) -free graphs to five.

Abstract A graph isH-free if it contains no induced subgraph isomorphic to H. We prove new complexity results for the two classical cycle transversal problemsFeedback Vertex SetandOdd Cycle Transversalby showing that they can be solved in polynomial time on $$(sP_1+ P_3)$$ (sP1+P3) -free graphs for every integer $$s\ge 1$$ s≥1 . We show the same result for the variantsConnected Feedback Vertex SetandConnected Odd Cycle Transversal. We also prove that the latter two problems are polynomial-time solvable on cographs; this was already known forFeedback Vertex SetandOdd Cycle Transversal. We complement these results by proving thatOdd Cycle TransversalandConnected Odd Cycle Transversalare -complete on $$(P_2+ P_5,P_6)$$ (P2+P5,P6) -free graphs.

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set ${\cal H}$ of forbidden induced subgraphs. We study the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the $|{\cal H}|=1$ case by classifying the boundedness of clique-width for every set ${\cal H}$ of self-complementary graphs. We then completely settle the $|{\cal H}|=2$ case. In particular, we determine one new class of $(H,\overline{H})$-free graphs of bounded clique-width (as a side effect, this leaves only five classes of $(H_1,H_2)$-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the $|{\cal H}|=2$ case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for every set ${\cal F}$ of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for $(\{H,\overline{H}\}\cup {\cal F})$-free graphs coincides with the one for the $|{\cal H}|=2$ case if and only if ${\cal F}$ does not include the bull.

A partition $(V_1,\ldots,V_k)$ of the vertex set of a graph $G$ with a (not necessarily proper) colouring $c$ is colourful if no two vertices in any $V_i$ have the same colour and every set $V_i$ induces a connected graph. The COLOURFUL PARTITION problem is to decide whether a coloured graph $(G,c)$ has a colourful partition of size at most $k$. This problem is closely related to the COLOURFUL COMPONENTS problem, which is to decide whether a graph can be modified into a graph whose connected components form a colourful partition by deleting at most $p$ edges. Nevertheless we show that COLOURFUL PARTITION and COLOURFUL COMPONENTS may have different complexities for restricted instances. We tighten known NP-hardness results for both problems and in addition we prove new hardness and tractability results for COLOURFUL PARTITION. Using these results we complete our paper with a thorough parameterized study of COLOURFUL PARTITION.

The NP-complete problem Feedback Vertex Set is that of deciding whether or not it is possible, for a given integer $$k\ge 0$$ , to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding whether or not a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for $$P_4$$ -free graphs. We show that it remains polynomial-time solvable for $$P_5$$ -free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks whether or not a graph has an independent odd cycle transversal of size at most k for a given integer $$k\ge 0$$ . Finally, in line with our underlying research aim, we compare the complexity of Independent Feedback Vertex Set for H-free graphs with the complexity of 3-Colouring, Independent Odd Cycle Transversal and other related problems.

Let vc(G), fvs(G) and oct(G) denote, respectively, the size of a minimum vertex cover, minimum feedback vertex set and minimum odd cycle transversal in a graph G. One can ask, when looking for these sets in a graph, how much bigger might they be if we require that they are independent; that is, what is the price of independence? If G has a vertex cover, feedback vertex set or odd cycle transversal that is an independent set, then we let, respectively, ivc(G), ifvs(G) or ioct(G) denote the minimum size of such a set. We investigate for which graphs H the values of ivc(G), ifvs(G) and ioct(G) are bounded in terms of vc(G), fvs(G) and oct(G), respectively, when the graph G belongs to the class of H-free graphs. We find complete classifications for vertex cover and feedback vertex set and an almost complete classification for odd cycle transversal (subject to three non-equivalent open cases).

The Near-Bipartiteness problem is that of deciding whether or not the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a forest. The set A in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that Near-Bipartiteness is polynomial-time solvable for graphs of diameter 2 and NP-complete for graphs of diameter 4. We show that Near-Bipartiteness is NP-complete for graphs of diameter 3, resolving their open problem. We also generalise their result for diameter 2 by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter 2.

A homomorphism from a graph G to a graph H is a vertex mapping f from the vertex set of G to the vertex set of H such that there is an edge between vertices f(u) and f(v) of H whenever there is an edge between vertices u and v of G. The H-Colouring problem is to decide whether or not a graph G allows a homomorphism to a fixed graph H. We continue a study on a variant of this problem, namely the Surjective $$H$$ -Colouring problem, which imposes the homomorphism to be vertex-surjective. We build upon previous results and show that this problem is NP-complete for every connected graph H that has exactly two vertices with a self-loop as long as these two vertices are not adjacent. As a result, we can classify the computational complexity of Surjective $$H$$ -Colouring for every graph H on at most four vertices.

The NP-complete problem Feedback Vertex Set is to decide if it is possible, for a given integer k>=0, to delete at most k vertices from a given graph so that what remains is a forest. The variant in which the deleted vertices must form an independent set is called Independent Feedback Vertex Set and is also NP-complete. In fact, even deciding if an independent feedback vertex set exists is NP-complete and this problem is closely related to the 3-Colouring problem, or equivalently, to the problem of deciding if a graph has an independent odd cycle transversal, that is, an independent set of vertices whose deletion makes the graph bipartite. We initiate a systematic study of the complexity of Independent Feedback Vertex Set for H-free graphs. We prove that it is NP-complete if H contains a claw or cycle. Tamura, Ito and Zhou proved that it is polynomial-time solvable for P_4-free graphs. We show that it remains in P for P_5-free graphs. We prove analogous results for the Independent Odd Cycle Transversal problem, which asks if a graph has an independent odd cycle transversal of size at most k for a given integer k>=0.

Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class is hereditary if it can be characterized by a (not necessarily finite) set H of forbidden induced subgraphs. We initiate a systematic study into the boundedness of clique-width of hereditary graph classes closed under complementation. First, we extend the known classification for the |H|=1 case by classifying the boundedness of clique-width for every set H of self-complementary graphs. We then completely settle the |H|=2 case. In particular, we determine one new class of (H1, complement of H1)-free graphs of bounded clique-width (as a side effect, this leaves only six classes of (H1, H2)-free graphs, for which it is not known whether their clique-width is bounded). Once we have obtained the classification of the |H|=2 case, we research the effect of forbidding self-complementary graphs on the boundedness of clique-width. Surprisingly, we show that for a set F of self-complementary graphs on at least five vertices, the classification of the boundedness of clique-width for ({H1, complement of H1} + F)-free graphs coincides with the one for the |H|=2 case if and only if F does not include the bull (the only non-empty self-complementary graphs on fewer than five vertices are P_1 and P_4, and P_4-free graphs have clique-width at most 2). Finally, we discuss the consequences of our results for COLOURING.

We continue research into a well-studied family of problems that ask if the vertices of a graph can be partitioned into sets A and B, where A is an independent set and B induces a graph from some specified graph class G. We let G be the class of k-degenerate graphs. The problem is known to be polynomial-time solvable if k=0 (bipartite graphs) and NP-complete if k=1 (near-bipartite graphs) even for graphs of diameter 4, as shown by Yang and Yuan, who also proved polynomial-time solvability for graphs of diameter 2. We show that recognizing near-bipartite graphs of diameter 3 is NP-complete resolving their open problem. To answer another open problem, we consider graphs of maximum degree D on n vertices. We show how to find A and B in O(n) time for k=1 and D=3, and in O(n^2) time for k >= 2 and D >= 4. These results also provide an algorithmic version of a result of Catlin [JCTB, 1979] and enable us to complete the complexity classification of another problem: finding a path in the vertex colouring reconfiguration graph between two given k-colourings of a graph of bounded maximum degree.

For a positive integer |$k$| and graph |$G=(V,E)$|⁠, a |$k$|-colouring of |$G$| is a mapping |$c: V\rightarrow \{1,2,\ldots ,k\}$| such that |$c(u)\neq c(v)$| whenever |$uv\in E$|⁠. The |$k$|-Colouring problem is to decide, for a given |$G$|⁠, whether a |$k$|-colouring of |$G$| exists. The |$k$|-Precolouring Extension problem is to decide, for a given |$G=(V,E)$|⁠, whether a colouring of a subset of |$V$| can be extended to a |$k$|-colouring of |$G$|⁠. A |$k$|-list assignment of a graph is an allocation of a list—a subset of |$\{1,\ldots ,k\}$|—to each vertex, and the List |$k$|-Colouring problem is to decide, for a given |$G$|⁠, whether |$G$| has a |$k$|-colouring in which each vertex is coloured with a colour from its list. We consider the computational complexity of these three decision problems when restricted to graphs that do not contain a cycle on |$s$| vertices or a path on |$t$| vertices as induced subgraphs (for fixed positive integers |$s$| and |$t$|⁠). We report on past work and prove a number of new NP-completeness results.

Abstract A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to find a minimum size transversal in time polynomial in n. In this paper, we show that if it is possible to decide if a set of vertices W ⊆ V is a transversal in time S(n) (where n = |V|), then it is possible to find a minimum size transversal in O(n3S(n)). This result provides a polynomial algorithm for the Source Location Problem: a set of (k,l)‐sources for a digraph D = (V,A) is a subset S of V such that for any v ∈ V there are k arc‐disjoint paths that each join a vertex of S to v and l arc‐disjoint paths that each join v to S. The Source Location Problem is to find a minimum size set of (k,l)‐sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case S(n) is polynomial. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008