The simple temporal problem (STP) and its generalization allowing disjunctive constraints (DTP) are some of the most influential reasoning formalisms for temporal information in AI. We study the problem of resolving inconsistency of data encoded in the DTP, i.e. given a DTP instance, find the minimum number of constraints to remove to make it satisfiable. While this problem is NP-hard in general, it is reasonable to assume that the amount of erroneous data will be small in practical instances. We therefore study the parameterized complexity of this problem parameterized by the number of constraints to be removed to achieve satisfiability, and obtain full P/NP-hard and FPT/W[1]-hard dichotomies for all binary DTP languages.

A graph class is monotone if it is closed under taking subgraphs. A monotone class defined by finitely many obstructions has bounded treewidth if and only if one of the obstructions is a tripod, i.e. a disjoint union of subdivided claws and paths. This dichotomy also characterizes exactly those monotone graph classes for which many NP-hard graph problems admit polynomial-time algorithms. These dichotomies do not extend to the universe of all hereditary classes. This leads to the question of whether we can extend known dichotomies for monotone classes to larger families of hereditary classes. We answer this question affirmatively by considering the family of hereditary graph classes closed under self-intersection. This family is known to be located strictly between the monotone and hereditary classes. We prove a new structural characterization of graphs in self-intersection-closed classes excluding a tripod. In contrast to monotone classes excluding a tripod, these classes do not necessarily have bounded treewidth; in fact, they do not even need to be sparse. We use our characterization to give a complete dichotomy for Maximum Independent Set, and its weighted variant, on self-intersection-closed classes defined by finitely many obstructions: these problems are in P if the class excludes a tripod and NP-hard otherwise. Our dichotomy generalizes several known results on Maximum Independent Set in the literature. We also apply our characterization to obtain a dichotomy for Maximum Induced Matching on self-intersection-closed classes of bipartite graphs defined by finitely many obstructions, and for Satisfiability and Counting Satisfiability on self-intersection-closed classes of (bipartite) incidence graphs defined by finitely many obstructions. Finally, we use our characterization to obtain a dichotomy for boundedness of clique-width for self-intersection-closed classes of bipartite graphs defined by finitely many obstructions.

We consider the Min-r-Lin(ℤ_m) problem: given a system S of length-r linear equations modulo m, find Z ⊆ S of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate in polynomial time within any constant factor even when r = m = 2. We focus on parameterized approximation with solution size as the parameter. Dabrowski, Jonsson, Ordyniak, Osipov and Wahlström [SODA-2023] showed that Min-r-Lin(ℤ_m) is in FPT if m is prime (i.e. ℤ_m is a field), and it is W[1]-hard if m is not a prime power. We show that Min-r-Lin(ℤ_{pⁿ}) is FPT-approximable within a factor of 2 for every prime p and integer n ≥ 2. This implies that Min-2-Lin(ℤ_m), m ∈ ℤ^+, is FPT-approximable within a factor of 2ω(m) where ω(m) counts the number of distinct prime divisors of m. The high-level idea behind the algorithm is to solve tighter and tighter relaxations of the problem, decreasing the set of possible values for the variables at each step. When working over ℤ_{pⁿ} and viewing the values in base-p, one can roughly think of a relaxation as fixing the number of trailing zeros and the least significant nonzero digits of the values assigned to the variables. To solve the relaxed problem, we construct a certain graph where solutions can be identified with a particular collection of cuts. The relaxation may hide obstructions that will only become visible in the next iteration of the algorithm, which makes it difficult to find optimal solutions. To deal with this, we use a strategy based on shadow removal [Marx & Razgon, STOC-2011] to compute solutions that (1) cost at most twice as much as the optimum and (2) allow us to reduce the set of values for all variables simultaneously. We complement the algorithmic result with two lower bounds, ruling out constant-factor FPT-approximation for Min-3-Lin(R) over any nontrivial ring R and for Min-2-Lin(R) over some finite commutative rings R.

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over a family of commutative domains (i.e. rings without zero divisors) with a particular Helly property. This set contains, for instance, finite and infinite fields, the ring of integers and univariate polynomial rings with coefficients from a field; more generally, it contains the important class of Prüfer domains. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalises many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not covered by our fpt result. On the technical side, we introduce the notion of important balanced subgraphs, generalising the important separators of Marx to the setting of biased graphs. Furthermore, we use recent results of Kim, Kratsch, Pilipczuk and Wahlström on parameterized MinCSP to efficiently solve a generalisation of Multicut with disjunctive cut requests.

We consider the NP-hard problem of finding a smallest decision tree representing a classification instance in terms of a partially defined Boolean function. Small decision trees are desirable to provide an interpretable model for the given data. We show that the problem is fixed-parameter tractable when parameterized by the rank-width of the incidence graph of the given classification instance. Our algorithm proceeds by dynamic programming using an NLC decomposition obtained from a rank-width decomposition. The key to the algorithm is a succinct representation of partial solutions. This allows us to limit the space and time requirements for each dynamic programming step in terms of the parameter.

Abstract. A homomorphism [Formula: see text] from a guest graph [Formula: see text] to a host graph [Formula: see text] is locally bijective, injective, or surjective if for every [Formula: see text], the restriction of [Formula: see text] to the neighbourhood of [Formula: see text] is bijective, injective, or surjective, respectively. We prove a number of new FPT (fixed-parameter tractable), W [1]-hard, and paraNP -complete results for the corresponding decision problems LBHom, LIHom, and LSHom by considering a hierarchy of parameters of the guest graph [Formula: see text]. In this way we strengthen several existing results. For our FPT results, we develop a new algorithmic framework that involves a general ILP (integer linear program) model. We also use our framework to prove FPT results for the Role Assignment problem, which originates from social network theory and is closely related to locally surjective homomorphisms.

Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most $k$ constraints, where $k$ is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen's interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set $A$ of 13 basic comparison relations such as ``precedes'' or ``during'' for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP$(Γ)$ for all $Γ\subseteq A$. IA is sometimes extended with unions of the relations in $A$ or first-order definable relations over $A$, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP$(A)$ in general, we then consider (parameterized) approximation algorithms and present a factor-$2$ fpt-approximation algorithm.

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains—a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.02732

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau (2013) [14] and Huang et al. (2013) [47] proved that CSP(Γ) can be solved in nf(w) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f(w)⋅nO(1), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours, and we begin investigating ways of generalising our results to larger families of languages. We also analyse our algorithm with respect to its running time and show that it is optimal (under the Exponential Time Hypothesis) for certain languages such as Allen's Interval Algebra.

The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a computationally hard problem, much work has been devoted to identifying restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints, and a highly successful approach is to bound the treewidth of the underlying primal graph. Bodirsky & Dalmau [J. Comput. System. Sci., 79(1), 2013] and Huang et al. [Artif. Intell., 195, 2013] proved that CSP(Γ) can be solved in n^(f(w)) time (where n is the size of the instance, w is the treewidth of the primal graph and f is a computable function) for certain classes of constraint languages Γ. We improve this bound to f(w)n^(O(1)), where the function f only depends on the language Γ, for CSPs whose basic relations have the patchwork property. Hence, such problems are fixed-parameter tractable and our algorithm is asymptotically faster than the previous ones. Additionally, our approach is not restricted to binary constraints, so it is applicable to a strictly larger class of problems than that of Huang et al. However, there exist natural problems that are covered by Bodirsky & Dalmau's algorithm but not by ours.

The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.'s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in O(c^n) time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by poly(n) can be solved in n^{f(w)} time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i.e. they do not admit a f(w)poly(n)$ time algorithm for any computable function f, under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = NP.

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.

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour [ J. Combin. Theory Ser. B, 35 (1983), pp. 39--61] proved that for every tree $T$, the class of graphs that do not contain $T$ as a minor has bounded path-width. For the pivot-minor relation, rank-width and linear rank-width take over the role of tree-width and path-width. As such, it is natural to examine if, for every tree $T$, the class of graphs that do not contain $T$ as a pivot-minor has bounded linear rank-width. We first prove that this statement is false whenever $T$ is a tree that is not a caterpillar. We conjecture that the statement is true if $T$ is a caterpillar. We are also able to give partial confirmation of this conjecture by proving for every tree $T$, the class of $T$-pivot-minor-free distance-hereditary graphs has bounded linear rank-width if and only if $T$ is a caterpillar; for every caterpillar $T$ on at most four vertices, the class of $T$-pivot-minor-free graphs has bounded linear rank-width. To prove our second result, we only need to consider $T=P_4$ and $T=K_{1,3}$, but we follow a general strategy: first we show that the class of $T$-pivot-minor-free graphs is contained in some class of $(H_1,H_2)$-free graphs, which we then show to have bounded linear rank-width. In particular, we prove that the class of $(K_3,S_{1,2,2})$-free graphs has bounded linear rank-width, which strengthens a known result that this graph class has bounded rank-width.

Expressive temporal reasoning formalisms are essential for AI. One family of such formalisms consists of disjunctive extensions of the simple temporal problem (STP). Such extensions are well studied in the literature and they have many important applications. It is known that deciding satisfiability of disjunctive STPs is NP-hard, while the fine-grained complexity of such problems is virtually unexplored. We present novel algorithms that exploit structural properties of the solution space and prove, assuming the Exponential-Time Hypothesis, that their worst-case time complexity is close to optimal. Among other things, we make progress towards resolving a long-open question concerning whether Allen's interval algebra can be solved in single-exponential time, by giving a 2^{O(nloglog(n))} algorithm for the special case of unit-length intervals.

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.

We obtain a complete classification of graphs H for which the class of (triangle,H)-free graphs is well-quasi-ordered by the induced subgraph relation and an almost complete classification of graphs H for which the class of (triangle,H)-free graphs has bounded clique-width. In particular, we show that for these graph classes, well-quasi-orderability implies boundedness of clique-width. To obtain our results, we further refine a known method based on canonical decomposition. This leads to a new decomposition technique that is applicable to both notions, well-quasi-orderability and clique-width.

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.

The Colouring problem asks whether the vertices of a graph can be coloured with at most k colours for a given integer k in such a way that no two adjacent vertices receive the same colour. A graph is ( H 1 , H 2 ) -free if it has no induced subgraph isomorphic to H 1 or H 2 . A connected graph H 1 is almost classified if Colouring on ( H 1 , H 2 ) -free graphs is known to be polynomial-time solvable or NP -complete for all but finitely many connected graphs H 2 . We show that every connected graph H 1 apart from the claw K 1 , 3 and the 5-vertex path P 5 is almost classified. We also prove a number of new hardness results for Colouring on ( 2 P 2 , H ) -free graphs. This enables us to list all graphs H for which the complexity of Colouring is open on ( 2 P 2 , H ) -free graphs and all graphs H for which the complexity of Colouring is open on ( P 5 , H ) -free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of Colouring for ( 2 P 2 , H ) -free graphs and for ( P 5 , H ) -free graphs are the same for all known cases.

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.

The Colouring problem is that of deciding, given a graph G and an integer k, whether G admits a (proper) k-colouring. For all graphs H up to five vertices, we classify the computational complexity of Colouring for (diamond,H)-free graphs. Our proof is based on combining known results together with proving that the clique-width is bounded for (diamond,P1+2P2)-free graphs. Our technique for handling this case is to reduce the graph under consideration to a k-partite graph that has a very specific decomposition. As a by-product of this general technique we are also able to prove boundedness of clique-width for four other new classes of (H1,H2)-free graphs. As such, our work also continues a recent systematic study into the (un)boundedness of clique-width of (H1,H2)-free graphs, and our five new classes of bounded clique-width reduce the number of open cases from 13 to 8.

We consider the following graph modification problem. Let the input consist of a graph G = ( V , E ) , a weight function w : V ∪ E → N , a cost function c : V ∪ E → N 0 and a degree function δ : V → N 0 , together with three integers k v , k e and C . The question is whether we can delete a set of vertices of total weight at most k v and a set of edges of total weight at most k e so that the total cost of the deleted elements is at most C and every non-deleted vertex v has degree δ ( v ) in the resulting graph G ′ . We also consider the variant in which G ′ must be connected. Both problems are known to be NP -complete and W [ 1 ] -hard when parameterized by k v + k e . We prove that, when restricted to planar graphs, they stay NP -complete but have polynomial kernels when parameterized by k v + k e .

The class of H-free graphs has bounded clique-width if and only if H is an induced subgraph of the 4-vertex path P4. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs H1 and H2. Prior to our study, it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases, we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results, we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of (H1,H2)-free graphs for all pairs (H1,H2), both of which are connected, except two non-equivalent cases, and for all pairs (H1,H2), at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs {H1,…,Hp} as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colouring problem restricted to (H1,H2)-free graphs.

We investigate the problem of modifying a graph into a connected graph in which the degree of each vertex satisfies a prescribed parity constraint. Let ea, ed and vd denote the operations edge addition, edge deletion and vertex deletion respectively. For any S subseteq {ea,ed,vd}, we define Connected Degree Parity Editing (S) (CDPE(S)) to be the problem that takes as input a graph G, an integer k and a function delta: V(G) -> {0,1}, and asks whether G can be modified into a connected graph H with d_H(v) = delta(v)(mod 2) for each v in V(H), using at most k operations from S. We prove that (*) if S={ea} or S={ea,ed}, then CDPE(S) can be solved in polynomial time; (*) if {vd} subseteq S subseteq {ea,ed,vd}, then CDPE(S) is NP-complete and W-hard when parameterized by k, even if delta = 0. Together with known results by Cai and Yang and by Cygan, Marx, Pilipczuk, Pilipczuk and Schlotter, our results completely classify the classical and parameterized complexity of the CDPE(S) problem for all S subseteq {ea,ed,vd}. We obtain the same classification for a natural variant of the cdpe(S) problem on directed graphs, where the target is a weakly connected digraph in which the difference between the in- and out-degree of every vertex equals a prescribed value. As an important implication of our results, we obtain polynomial-time algorithms for Eulerian Editing problem and its directed variant. To the best of our knowledge, the only other natural non-trivial graph class H for which the H-Editing problem is known to be polynomial-time solvable is the class of split graphs.