Search

We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by Campos and Silva (Algorithmica 80(1), 104–115, 2018) and Bonomo et al. (Graphs and Combinatorics 25(2), 153–167, 2009). This constitutes the first result concerning structural parameterizations of this problem. We show that the problem is FPT when parameterized by the vertex cover number on general graphs, and on chordal graphs when parameterized by the number of colors. Additionally, we observe that our algorithm for graphs of bounded clique-width can be adapted to solve the Fall Coloring problem within the same runtime bound. The running times of the clique-width based algorithms for b -Coloring and Fall Coloring are tight under the Exponential Time Hypothesis. [ABSTRACT FROM AUTHOR]

The generic homomorphism problem, which asks whether an input graph \(G\) admits a homomorphism into a fixed target graph \(H\) , has been widely studied in the literature. In this article, we provide a fine-grained complexity classification of the running time of the homomorphism problem with respect to the clique-width of \(G\) (denoted \({\operatorname{cw}}\)) for virtually all choices of \(H\) under the Strong Exponential Time Hypothesis. In particular, we identify a property of \(H\) called the signature number \(s(H)\) and show that for each \(H\) , the homomorphism problem can be solved in time \(\mathcal{O^{*}}(s(H)^{{\operatorname{cw}}})\). Crucially, we then show that this algorithm can be used to obtain essentially tight upper bounds. Specifically, we provide a reduction that yields matching lower bounds for each \(H\) that is either a projective core or a graph admitting a factorization with additional properties—allowing us to cover all possible target graphs under long-standing conjectures. [ABSTRACT FROM AUTHOR]

In this paper, we study the Harmless Set problem from a parameterized complexity perspective. Given a graph G = (V , E) , a threshold function t : V → N and an integer k, we study Harmless Set, where the goal is to find a subset of vertices S ⊆ V of size at least k such that every vertex v ∈ V has fewer than t(v) neighbours in S. On the positive side, we obtain fixed-parameter algorithms for the problem when parameterized by the neighbourhood diversity, the twin-cover number and the vertex integrity of the input graph. We complement two of these results from the negative side. On dense graphs, we show that the problem is W[1]-hard parameterized by cluster vertex deletion number—a natural generalization of the twin-cover number. We show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, and treedepth—a natural generalization of the vertex integrity. We thereby resolve one open question stated by Bazgan and Chopin (Discrete Optim 14(C):170–182, 2014) concerning the complexity of Harmless Set parameterized by the treewidth of the input graph. We also show that Harmless Set for a special case where each vertex has the threshold set to half of its degree (the so-called Majority Harmless Set problem) is W[1]-hard when parameterized by the treewidth of the input graph. Given a graph G and an irredundant c-expression of G, we prove that Harmless Set can be solved in XP-time when parameterized by clique-width. [ABSTRACT FROM AUTHOR]

Frei et al. (J. Comput. Syst. Sci. 123, 103–121, 2022) show that the stability, vertex stability, and unfrozenness problems with respect to certain graph parameters are complete for Θ 2 P , the class of problems solvable in polynomial time by parallel access to an NP oracle. They studied the common graph parameters α (the independence number), β (the vertex cover number), ω (the clique number), and χ (the chromatic number). We complement their approach by providing polynomial-time algorithms solving these problems for special graph classes, namely for graphs with bounded tree-width or bounded clique-width. In order to improve these general time bounds even further, we then focus on trees, forests, bipartite graphs, and co-graphs. [ABSTRACT FROM AUTHOR]

Computing for all pairs of vertices the shortest paths in a graph is a fundamental and much-studied problem with many applications. Unfortunately, despite intense study, there are still no significantly faster algorithms for it than the O (n 3) time algorithm due to Floyd and Warshall (1962). Somewhat faster algorithms exist for the vertex-weighted version if fast matrix multiplication may be used. Yuster (SODA 2009) gave an algorithm running in time O (n 2. 842) , but no combinatorial, truly subcubic algorithm is known. Motivated by the recent framework of efficient parameterized algorithms (or "FPT in P"), we investigate the influence of the graph parameters clique-width (cw) and modular-width (mw) on the running times of algorithms for solving vertex-weighted all-pairs shortest paths. We obtain efficient (and combinatorial) parameterized algorithms of times O (cw 2 n 2) , resp. O (mw 2 n + n 2). If fast matrix multiplication is allowed then the latter can be improved to O (mw 1. 842 n + n 2) using the algorithm of Yuster as a black box. The algorithm relative to modular-width is adaptive, meaning that the running time matches the best unparameterized algorithm for parameter value mw equal to n , and outperforms it already for mw ∈ O (n 1 − ɛ) for any ɛ > 0. [ABSTRACT FROM AUTHOR]

Many NP‐complete graph problems are polynomial‐time solvable on graph classes of bounded clique‐width. Several of these problems are polynomial‐time solvable on a hereditary graph class G ${\mathscr{G}}$ if they are so on the atoms (graphs with no clique cut‐set) of G ${\mathscr{G}}$. Hence, we initiate a systematic study into boundedness of clique‐width of atoms of hereditary graph classes. A graph G $G$ is H $H$‐free if H $H$ is not an induced subgraph of G $G$, and it is (H1,H2) $({H}_{1},{H}_{2})$‐free if it is both H1 ${H}_{1}$‐free and H2 ${H}_{2}$‐free. A class of H $H$‐free graphs has bounded clique‐width if and only if its atoms have this property. This is no longer true for (H1,H2) $({H}_{1},{H}_{2})$‐free graphs, as evidenced by one known example. We prove the existence of another such pair (H1,H2) $({H}_{1},{H}_{2})$ and classify the boundedness of clique‐width on (H1,H2) $({H}_{1},{H}_{2})$‐free atoms for all but 18 cases. [ABSTRACT FROM AUTHOR]

We create a framework for hereditary graph classes Gδ built on a two-dimensional grid of vertices and edge sets defined by a triple δ = {β, γ, δ} of objects that define edges between consecutive columns, edges between nonconsecutive columns (called bonds), and edges within columns. This framework captures a large family of minimal hereditary classes of graphs of unbounded clique-width, some previously identified and many new ones, although we do not claim this includes all such classes. We show that a graph class\scrGδ has unbounded clique-width if and only if a certain parameter scrNδ is unbounded. We further show that scrGδ is minimal of unbounded clique-width (and, indeed, minimal of unbounded linear clique-width) if another parameter\scrMγa is bounded, and also δ has defined recurrence characteristics. Both the parameters scrNβ and scrMMδ are properties of a triple δ = (α, β, γ) and measure the number of distinct neighborhoods in certain auxiliary graphs. Throughout our work, we introduce new methods to the study of clique-width, including the use of Ramsey theory in arguments related to unboundedness, and explicit (linear) clique-width expressions for subclasses of minimal classes of unbounded clique-width. [ABSTRACT FROM AUTHOR]

While structural width parameters (of the input) belong to the standard toolbox of graph algorithms, it is not the usual case in computational geometry. As a case study we propose a natural extension of the structural graph parameter of clique-width to geometric point configurations represented by their order type. We study basic properties of this clique-width notion, and show that it is aligned with the general concept of clique-width of relational structures by Blumensath and Courcelle (2006). We also relate the new notion to monadic second-order logic of point configurations. As an application, we provide several linear FPT time algorithms for geometric point problems which are NP-hard in general, in the special case that the input point set is of bounded clique-width and the clique-width expression is also given. [ABSTRACT FROM AUTHOR]

We prove that, for each circle graph H , every graph with sufficiently large rank-width contains a vertex-minor isomorphic to H. [ABSTRACT FROM AUTHOR]

Given an n-vertex m-edge graph G of clique-width at most k, and a corresponding k-expression, we present algorithms for computing some well-known centrality indices (eccentricity and closeness) that run in O (2 O (k) (n + m) 1 + ϵ) time for any ϵ > 0 . Doing so, we can solve various distance problems within the same amount of time, including: the diameter, the center, the Wiener index and the median set. Our run-times match conditional lower bounds of Coudert et al. (SODA'18) under the Strong Exponential-Time Hypothesis. On our way, we get a distance-labeling scheme for n-vertex m-edge graphs of clique-width at most k, using O (k log 2 n) bits per vertex and constructible in O ~ (k (n + m)) time from a given k-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on k in their scheme. As a corollary, we get an O ~ (k n 2) -time algorithm for computing All-Pairs Shortest-Paths on n-vertex graphs of clique-width at most k, being given a k-expression. This partially answers an open question of Kratsch and Nelles (STACS'20). Our algorithms work for graphs with non-negative vertex-weights, under two different types of distances studied in the literature. For that, we introduce a new type of orthogonal range query as a side contribution of this work, that might be of independent interest. [ABSTRACT FROM AUTHOR]

• Satisfactory Partition is polynomial-time solvable for block graphs. • Satisfactory Partition is FPT parameterized by neighbourhood diversity. • Satisfactory Partition can be solved in polynomial time for graphs of bounded clique-width. • Balanced Satisfactory Partition is W[1]-hard when parameterized by treewidth. Given an undirected graph G , we study the Satisfactory Partition problem, where the goal is to decide whether it is possible to partition the vertex set of G into two parts such that each vertex has at least as many neighbours in its own part as in the other part. The Balanced Satisfactory Partition problem is a variant of the above problem where the two partite sets are required to have the same cardinality. Both problems are known to be NP-complete. This problem was introduced by Gerber and Kobler (2000) [9] and further studied by other authors, but its parameterized complexity remains open until now. We enhance our understanding of the problem from the viewpoint of parameterized complexity. The main results of the paper are the following: (1) Satisfactory Partition is polynomial-time solvable for block graphs, (2) Satisfactory Partition and Balanced Satisfactory Partition are fixed parameter tractable (FPT) when parameterized by neighbourhood diversity. (3) Satisfactory Partition and its balanced version can be solved in polynomial time for graphs of bounded clique-width, and (4) Balanced Satisfactory Partition is W[1]-hard when parameterized by treewidth. [ABSTRACT FROM AUTHOR]

We give a complete structural description of (4K1,C4,C6,C7)‐free graphs that do not contain a simplicial vertex, and we prove that such graphs have bounded clique‐width. Together with the results of Foley et al., this implies that (4K1,C4,C6)‐free graphs that do not contain a simplicial vertex have bounded clique‐width. Consequently, Graph Coloring can be solved in polynomial time for (4K1,C4,C6)‐free graphs, that is, for even‐hole‐free graphs of stability number at most three. [ABSTRACT FROM AUTHOR]

A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether a given graph has a clique coloring with q colors. For fixed q ≥ 2 , we give an O ⋆ (q tw) -time algorithm when the input graph is given together with one of its tree decompositions of width tw . We complement this result with a matching lower bound under the Strong Exponential Time Hypothesis. We furthermore show that (when the number of colors is unbounded) Clique Coloring is XP parameterized by clique-width. [ABSTRACT FROM AUTHOR]

Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (α , β , δ) -clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most δ labels, a) every label consists of at most β sets of twin vertices, and b) all the labels together induce a graph with independence number at most α. We show that for every two constants α , δ > 0 the problem is FPT when parameterized by β plus the smallest width of an (α , β , δ) -clique-width decomposition. [ABSTRACT FROM AUTHOR]

A large number of NP‐hard graph problems are solvable in XP time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider maximum‐induced matching width (mim‐width), a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is "quickly computable" for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim‐width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim‐width from the perspective of hereditary graph classes, and make a comparison with clique‐width, a more restrictive width parameter that has been well studied. We prove that for a given graph H, the class of H‐free graphs has bounded mim‐width if and only if it has bounded clique‐width. We show that the same is not true for (H1,H2)‐free graphs. We identify several general classes of (H1,H2)‐free graphs having unbounded clique‐width, but bounded mim‐width; moreover, we show that a branch decomposition of constant mim‐width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of (H1,H2)‐free graphs, many problems become polynomial‐time solvable, including classical problems, such as k‐ Colouring and Independent Set, domination‐type problems known as Locally Checkable Vertex Subset and Vertex Partitioning (LC‐VSVP) problems, and distance versions of LC‐VSVP problems, to name just a few. We also prove a number of new results showing that, for certain H1 and H2, the class of (H1,H2)‐free graphs has unbounded mim‐width. Boundedness of clique‐width implies boundedness of mim‐width. By combining our results with the known bounded cases for clique‐width, we present summary theorems of the current state of the art for the boundedness of mim‐width for (H1,H2)‐free graphs. In particular, we classify the mim‐width of (H1,H2)‐free graphs for all pairs (H1,H2) with ∣V(H1)∣+∣V(H2)∣≤8. When H1 and H2 are connected graphs, we classify all pairs (H1,H2) except for one remaining infinite family and a few isolated cases. [ABSTRACT FROM AUTHOR]

This document is an erratum for a publication titled "More applications of the d-neighbor equivalence: Acyclicity and Connectivity constraints" in the SIAM Journal on Discrete Mathematics. The authors identified an error in their previous publication and provide a correction. The correction involves changing the section and theorem numbers and providing the corrected algorithms for solving partition problems. The authors also mention recent improvements by other researchers in handling acyclicity and removing the dependence on the number of vertices in certain upper bounds. [Extracted from the article]

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$, and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbb{Q}$-rank-width, rank-width, and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic \sf NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [B. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoret. Comput. Sci., (2013), pp. 66--76] and the rank-based approach introduced in [H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Inform. and Comput., 243 (2015), pp. 86--111]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for ${\sf W}[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$, and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbb{Q}$-rank-width, and the rank-width of the input graph. [ABSTRACT FROM AUTHOR]

We discover new hereditary classes of graphs that are minimal (with respect to set inclusion) of unbounded clique-width. The new examples include split permutation graphs and bichain graphs. Each of these classes is characterised by a finite list of minimal forbidden induced subgraphs. These, therefore, disprove a conjecture due to Daligault, Rao and Thomassé from 2010 claiming that all such minimal classes must be defined by infinitely many forbidden induced subgraphs. In the same paper, Daligault, Rao and Thomassé make another conjecture that every hereditary class of unbounded clique-width must contain a labelled infinite antichain. We show that the two example classes we consider here satisfy this conjecture. Indeed, they each contain a canonical labelled infinite antichain, which leads us to propose a stronger conjecture: that every hereditary class of graphs that is minimal of unbounded clique-width contains a canonical labelled infinite antichain. [ABSTRACT FROM AUTHOR]

The cut-set ∂ (S) of a graph G = (V , E) is the set of edges that have one endpoint in S ⊂ V and the other endpoint in V \ S , and whenever G[S] is connected, the cut [ S , V \ S ] of G is called a connected cut. A bond of a graph G is an inclusion-wise minimal disconnecting set of G, i.e., bonds are cut-sets that determine cuts [ S , V \ S ] of G such that G[S] and G [ V \ S ] are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP . Also, we show that Largest Bond and Maximum Connected Cut are NP-hard even for planar bipartite graphs, whereas Maximum Cut is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that Largest Bond and Maximum Connected Cut are NP-hard on split graphs, and restricted to graphs of clique-width w they can not be solved in time f (w) n o (w) unless the Exponential Time Hypothesis fails, but they can be solved in time f (w) n O (w) . Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number. [ABSTRACT FROM AUTHOR]

We resolve the computational complexity of Graph Isomorphism for classes of graphs characterized by two forbidden induced subgraphs H 1 and H 2 for all but six pairs (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) -free graphs to five. [ABSTRACT FROM AUTHOR]

In the present paper, we introduce the notion of graph functionality, which generalises simultaneously several other graph parameters, such as degeneracy or clique-width, in the sense that bounded degeneracy or bounded clique-width imply bounded functionality. Moreover, we show that this generalisation is proper by revealing classes of graphs of unbounded degeneracy and clique-width, where functionality is bounded by a constant. We also prove that bounded functionality implies bounded VC-dimension, i.e., graphs of bounded VC-dimension extend graphs of bounded functionality, and this extension is also proper. [ABSTRACT FROM AUTHOR]

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G , is known to be NP -complete even for very restricted graph classes such as for 2 P 3 -free chordal graphs while it is solvable in polynomial time for P 6 -free chordal graphs (and even for P 6 -free graphs). A standard reduction from the NP -complete Exact Cover problem shows that ED is NP -complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP -complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP -complete for butterfly-free chordal graphs while it is solvable in linear time for 2 P 2 -free graphs. We show that (weighted) ED can be solved in polynomial time for H -free chordal graphs when H is net, extended gem, or S 1 , 2 , 3. [ABSTRACT FROM AUTHOR]

We revisit the complexity of the classical k-COLORING problem parameterized by clique-width. This is a very well-studied problem that becomes highly intractable when the number of colors k is large. However, much less is known on its complexity for small, concrete values of k. In this paper, we completely determine, under the Strong Exponential Time Hypothesis (SETH), for any fixed constant k, the complexity of k-COLORING parameterized by clique-width. Specifically, we show that for all k ≥ 3, ∈ > 0, k-COLORING cannot be solved in time O* ((2k-2-∈)cw), and give an algorithm running in time O*( (2k-2-)cw) . Thus, if the SETH is true, 2k - 2 is the ``correct"" base of the exponent for every fixed k. Along the way, we also consider the complexity of k-COLORING parameterized by the related parameter modular treewidth (mtw). In this case we show that the 'correct"running time under the SETH is O*((k [k/2])mtw). If we base our results on a weaker assumption (the ETH), they imply that k-COLORING cannot be solved in time no(cw), even on instances with O(log n) colors. [ABSTRACT FROM AUTHOR]

The clique-width is a measure of complexity of decomposing graphs into certain tree-like structures. The class of graphs with bounded clique-width contains bounded tree-width graphs. We give a polynomial time graph isomorphism algorithm for graphs with clique-width at most three. Our work is independent of the work by Grohe et al. [1] showing that the isomorphism problem for graphs of bounded clique-width is polynomial time. [ABSTRACT FROM AUTHOR]

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

Graph decompositions are important for algorithmic purposes and for graph structure theory. We relate the split decomposition introduced by Cunnigham to vertex substitution , graph grammars and clique-width. For this purpose, we extend the usual notion of substitution, upon which modular decomposition is based, by considering graphs with dead (or non-boundary) vertices. We obtain a graph grammar for distance-hereditary graphs consisting of four rules collected in a single equation. We also bound the clique-width of a graph in terms of those of the components of a split decomposition that need not be canonical. For extending these results to directed graphs and their split decompositions (that we handle formally as graph-labelled trees), we need another extension of substitution : instead of two types of vertices, dead or alive as for undirected graphs, we need four types, in order to encode edge directions. We bound linearly the clique-width of a directed graph G in terms of the maximal clique-width of a component arising in a graph-labelled tree that defines G. This result concerns all directed graphs, not only the strongly connected ones considered by Cunningham. [ABSTRACT FROM AUTHOR]

Motivated by the construction of FPT graph algorithms parameterized by clique-width or tree-width, we study graph classes for which tree-width and clique-width are linearly related. This is the case for all graph classes of bounded expansion, but in view of concrete applications, we want to have "small" constants in the comparisons between these width parameters. We focus our attention on graphs that can be drawn in the plane with limited edge crossings, for an example, at most p crossings for each edge. These graphs are called p - planar. We consider a more general situation where the graph of edge crossings must belong to a fixed class of graphs D. For p -planar graphs, D is the class of graphs of degree at most p. We prove that tree-width and clique-width are linearly related for graphs drawable with a graph of crossings of bounded average degree. We prove that the class of 1-planar graphs, although conceptually close to that of planar graphs, is not characterized by a monadic second-order sentence. We identify two subclasses that are. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The complexity of Colouring is fully understood for H -free graphs, but there are still major complexity gaps if two induced subgraphs H 1 and H 2 are forbidden. Let H 1 be the s -vertex cycle C s and H 2 be the t -vertex path P t. We show that Colouring is polynomial-time solvable for s = 4 and t ≤ 6 , strengthening several known results. Our main approach is to initiate a study into the boundedness of the clique-width of atoms (graphs with no clique cutset) of a hereditary graph class. As a complementary result we prove that Colouring is NP -complete for s = 4 and t ≥ 9 , which is the first hardness result on Colouring for (C 4 , P t) -free graphs. Combining our new results with known results leads to an almost complete dichotomy for Colouring restricted to (C s , P t) -free graphs. [ABSTRACT FROM AUTHOR]

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G , is known to be NP -complete even for very restricted H -free graph classes such as for 2 P 3 -free chordal graphs while it is solvable in polynomial time for P 6 -free graphs. Here we focus on bipartite graphs: We show that (weighted) ED can be solved in polynomial time for H -free bipartite graphs when H is P 7 or ℓ P 4 for fixed ℓ , and similarly for P 9 -free bipartite graphs with vertex degree at most 3, and when H is S 2 , 2 , 4. Moreover, we show that ED is NP -complete for bipartite graphs with diameter at most 6. [ABSTRACT FROM AUTHOR]

Given a clique-width k -expression of a graph G , we provide 2 O (k) ⋅ n time algorithms for connectivity constraints on locally checkable properties such as Node-Weighted Steiner Tree , Connected Dominating Set , or Connected Vertex Cover. We also propose a 2 O (k) ⋅ n time algorithm for Feedback Vertex Set. The best running times for all the considered problems were 2 O (k ⋅ log ⁡ (k)) ⋅ n O (1). [ABSTRACT FROM AUTHOR]

In (k , r) - Center we are given a (possibly edge-weighted) graph and are asked to select at most k vertices (centers), so that all other vertices are at distance at most r from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: • For any r ≥ 1 , we show an algorithm that solves the problem in O ∗ ( (3 r + 1) cw) time, where cw is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for r = 1 , this closes the gap that previously existed on the complexity of Dominating Set parameterized by cw. • We strengthen previously known FPT lower bounds, by showing that (k , r) - Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if k is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. • We show that the complexity of the problem parameterized by tree-depth is 2 Θ (td 2) , by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth, which work efficiently independently of the values of k , r. In particular, we give algorithms which, for any ϵ > 0 , run in time O ∗ ( (tw ∕ ϵ) O (tw) ) , O ∗ ( (cw ∕ ϵ) O (cw) ) and return a (k , (1 + ϵ) r) -center if a (k , r) -center exists, thus circumventing the problem's W-hardness. [ABSTRACT FROM AUTHOR]