In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. We prove that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide.

Bojańczyk, Pilipczuk, and Grohe [LICS '18] proved that for graphs of bounded linear clique-width, clique-width decompositions of small width can be produced by a CMSO transduction. We show that in the case of tournaments, a first-order transduction suffices. This implies that the logics CMSO and existential MSO are equivalent over bounded linear clique-width tournaments.

In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.

Abstract Lettericity is a graph parameter responsible for many attractive structural properties. In particular, graphs of bounded lettericity have bounded linear clique-width and they are well-quasi-ordered by induced subgraphs. The latter property implies that any hereditary class of graphs of bounded lettericity can be described by finitely many forbidden induced subgraphs. This, in turn, implies, in a non-constructive way, polynomial-time recognition of such classes. However, no constructive algorithms and no specific bounds on the size of forbidden graphs are available up to date. In the present paper, we develop an algorithm that recognizes n -vertex graphs of lettericity at most k in time $$f(k) \cdot n^3$$ and show that any minimal graph of lettericity more than k has at most $$2^{O(k^2\log k)}$$ vertices.

Let ${\mathbb{F}}$ be a finite field. We prove that there is an MSO-transduction which, given an ${\mathbb{F}}$-representable matroid of path-width k, produces a branch-decomposition of width at most f(k), for some function f. As a corollary, any recognizable property of ${\mathbb{F}}$-representable matroids with bounded path-width is definable in MSO logic, and therefore recognizability is equivalent to MSO-definability on classes of ${\mathbb{F}}$-representable matroids of bounded path-width. This generalizes the result of Bojańczyk, Grohe and Pilipczuk [Logical Methods in Computer Science 17(1), 2021] which asserts the equivalence of the two notions on graphs of bounded linear clique-width.

We show that given a graph G we can CMSO-transduce its modular decomposition, its split decomposition and its bi-join decomposition. This improves results by Courcelle [Logical Methods in Computer Science, 2006] who gave such transductions using order-invariant MSO, a strictly more expressive logic than CMSO. Our methods more generally yield C_{2}MSO-transductions of the canonical decomposition of weakly-partitive set systems and weakly-bipartitive systems of bipartitions.

Given two graphs G and H , where H is the forbidden subgraph or pattern, G is called H -free if no vertex subset V ′ ⊆ V ( G ) induces a subgraph G [ V ′ ] isomorphic to H . In the edge-induced version of the notion, G is called H -free if no edge subset E ′ ⊆ E ( G ) induces a subgraph G [ E ′ ] isomorphic to H . The goal is to list all the inclusion-maximal subgraphs of G that are H -free, according to both the edge-induced and vertex-induced versions. Apart from its theoretical interest, the problem has application in data modeling, as it corresponds to data cleaning/repairing tasks, where the entire dataset is inconsistent with respect to the constraints given in H , and maximal consistent portions are sought. Several output-sensitive algorithms for the vertex-induced version are presented, which depend on the constraints on H and on G . As for the edge-induced version, we show how output-sensitive algorithms are possible for specific cases, but an efficient general technique is unlikely to exist as simply certifying a solution can be co-NP-complete.

Abstract. We spotted an error in our publication More applications of the d-neighbor equivalence: Acyclicity and Connetivity constraints [ SIAM J. Discrete Math., 35 (2021), pp. 1881–1926]. We explain the problem and suggest a simple correction.

Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simple as path or tree decompositions, such dynamic programming uses space that is exponential in the decomposition's width, and there are good reasons to believe that this is necessary. However, it has been shown that in graphs of low treedepth it is possible to design algorithms which achieve polynomial space complexity without requiring worse time complexity than their counterparts working on tree decompositions of bounded width. Here, treedepth is a graph parameter that, intuitively speaking, takes into account both the depth and the width of a tree decomposition of the graph, rather than the width alone. Motivated by the above, we consider graphs that admit clique expressions with bounded depth and label count, or equivalently, graphs of low shrubdepth (sd). Here, sd is a bounded-depth analogue of cliquewidth, in the same way as td is a bounded-depth analogue of treewidth. We show that also in this setting, bounding the depth of the decomposition is a deciding factor for improving the space complexity. Precisely, we prove that on $n$-vertex graphs equipped with a tree-model (a decomposition notion underlying sd) of depth $d$ and using $k$ labels, we can solve - Independent Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $O(dk^2\log n)$ space; - Max Cut in time $n^{O(dk)}$ using $O(dk\log n)$ space; and - Dominating Set in time $2^{O(dk)}\cdot n^{O(1)}$ using $n^{O(1)}$ space via a randomized algorithm. We also establish a lower bound, conditional on a certain assumption about the complexity of Longest Common Subsequence, which shows that at least in the case of IS the exponent of the parametric factor in the time complexity has to grow with $d$ if one wishes to keep the space complexity polynomial.

Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field F, the list contains only finitely many F-representable matroids, due to the well-quasi-ordering of F-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these F-representable excluded minors in general. We consider the class of matroids of path-width at most k for fixed k. We prove that for a finite field F, every F-representable excluded minor for the class of matroids of path-width at most k has at most 2^{|𝔽|^{O(k²)}} elements. We can therefore compute, for any integer k and a fixed finite field F, the set of F-representable excluded minors for the class of matroids of path-width k, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an F-represented matroid is at most k. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most k has at most 2^{2^{O(k²)}} vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.

We uncover a connection between two seemingly unrelated notions: lettericity, from structural graph theory, and geometric griddability, from the world of permutation patterns. Both of these notions capture important structural properties of their respective classes of objects. We prove that these notions are equivalent in the sense that a permutation class is geometrically griddable if and only if the corresponding class of inversion graphs has bounded lettericity.

The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search, where we are given a system of tunnels (represented by a graph) that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher on a vertex or removes a searcher from a vertex and where an edge is cleaned when both endpoints are simultaneously occupied by searchers. It was proved that the minimum number of searchers required for a successful cleaning strategy is equal to the pathwidth of the graph plus one. Two desired characteristics for a cleaning strategy are to be monotone (no recontamination occurs) and connected (clean territories always remain connected). Under these two demands, the number of searchers is equivalent to a variant of pathwidth called connected pathwidth. We prove that connected pathwidth is fixed parameter tractable; in particular we design a $2^{O(k^2)}\cdot n$ time algorithm that checks whether the connected pathwidth of $G$ is at most $k.$ This resolves an open question by Dereniowski, Osula, and Rzaͅżewski [ Theoret. Comput. Sci., 794 (2019), pp. 85--100]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced by Bodlaender and Kloks [ J. Algorithms, 21 (1996), pp. 358--402] for the design of linear parameterized algorithms for treewidth and pathwidth. While this technique has been later applied to other parameters, none of its advancements was able to deal with the connectivity demand, as it is a “global” demand that concerns an unbounded number of parts of the graph of unbounded size. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted to deliver linear parameterized algorithms for the connected variants of other width parameters as well. An immediate consequence of our result is a $2^{O(k^2)}\cdot n$ time algorithm for the monotone and connected version of the edge search number.

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.

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.

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. For all these problems, we obtain 2^O(k)* n^O(1), 2^O(k log(k))* n^O(1), 2^O(k^2) * n^O(1) and n^O(k) time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and maximum induced matching width. Our approach simplifies and unifies the known algorithms for each of the parameters and match asymptotically also the running time of the best algorithms for basic NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the d-neighbor equivalence defined in [Bui-Xuan, Telle and Vatshelle, TCS 2013]. The results we obtain highlight the importance and the generalizing power of this equivalence relation on width measures. We also prove that this equivalence relation could be useful for Max Cut: a W[1]-hard problem parameterized by clique-width. For this latter problem, we obtain n^O(k), n^O(k) and n^(2^O(k)) time algorithm parameterized by clique-width, Q-rank-width and rank-width.

This paper investigates induced Steiner subgraphs as a variant of the classical Steiner trees, so as to compactly represent the (exponentially many) Steiner trees sharing the same underlying induced subgraph. We prove that the enumeration of all (inclusion-minimal) induced Steiner subgraphs is harder than the well-known Hypergraph Transversal enumeration problem if the number of terminals is not fixed. When the number of terminals is fixed, we propose a polynomial delay algorithm for listing all induced Steiner subgraphs of minimum size. We also propose a polynomial delay algorithm for listing the set of minimal induced Steiner subgraphs when the number of terminals is 3.

We give a polynomial delay algorithm for enumerating the minimal transversals of hypergraphs without induced cycles of length 3 and 4. As a corollary, we can enumerate, with polynomial delay, the vertices of any polyhedron P(A,1)={x in R^n | Ax >= 1, x >= 0}, when A is a balanced matrix that does not contain as a submatrix the incidence matrix of a cycle of length 4. Other consequences are a polynomial delay algorithm for enumerating the minimal dominating sets of graphs of girth at least 9 and an incremental delay algorithm for enumerating all the minimal dominating sets of a bipartite graph without induced 6 and 8-cycles.

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. Maximal cliques are arguably the most widely studied among such models, with early works dating back to the '60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e., of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We characterize the problem by giving a tight bound for the number of such cliques in a graph, and highlighting useful structural properties. We then exploit these properties to produce the first algorithm with polynomial delay for enumerating maximal strongly connected cliques.

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour (J Comb Theory Ser B 96(4):514–528, 2006). Motivated from recent development on graph modification problems regarding classes of graphs of bounded treewidth or pathwidth, we study the Linear Rankwidth-1 Vertex Deletion problem (shortly, LRW1-Vertex Deletion). In the LRW1-Vertex Deletion problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most 1 and find such a vertex set if one exists. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1-Vertex Deletion can be solved in time $$f(k)\cdot n^3$$ for some function f, it is not clear whether this problem allows a running time with a modest exponential function. We first establish that LRW1-Vertex Deletion can be solved in time $$8^k\cdot n^{{\mathcal {O}}(1)}$$ . The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define necklace graphs and investigate their structural properties. Later, we reduce the polynomial factor by refining the trivial branching step based on a cliquewidth expression of a graph, and obtain an algorithm that runs in time $$2^{{\mathcal {O}}(k)}\cdot n^4$$ . We also prove that the running time cannot be improved to $$2^{o(k)}\cdot n^{{\mathcal {O}}(1)}$$ under the Exponential Time Hypothesis assumption. Lastly, we show that the LRW1-Vertex Deletion problem admits a polynomial kernel.

We give linear and polynomial time algorithms for computing the hull number of distance-hereditary and chordal graphs, respectively. The complexity of computing the hull number in chordal and distance-hereditary graphs has been open since the introduction of the notion in [M. G. Everett and S. B. Seidman, Discrete Math., 57 (1985), pp. 217--223]. Prior to our result polynomial time algorithms were only known for subclasses of considered graph classes, e.g., split graphs, cographs, interval graphs. Our techniques allow us to give at the same time a linear time algorithm for computing the geodetic number in distance-hereditary graphs. Another consequence of the techniques used is an incremental output-polynomial algorithm to list the set of (inclusion-wise) minimal hull sets in any graphs.

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approxi-mating clique-width and branch-width. J. Combin. Theory Ser. B, 96(4):514-528, 2006.], and it is similar to pathwidth, which is the linearized variant of treewidth. Motivated from the results on graph modification problems into graphs of bounded treewidth or pathwidth, we investigate a graph modification problem into the class of graphs having linear rankwidth at most one, called the Linear Rankwidth-1 Vertex Deletion (shortly, LRW1-Vertex Deletion). In this problem, given an n-vertex graph G and a positive integer k, we want to decide whether there is a set of at most k vertices whose removal turns G into a graph of linear rankwidth at most one and if one exists, find such a vertex set. While the meta-theorem of Courcelle, Makowsky, and Rotics implies that LRW1-Vertex Deletion can be solved in time f (k) · n 3 for some function f , it is not clear whether this problem allows a runtime with a modest exponential function. We establish that LRW1-Vertex Deletion can be solved in time 8 k · n O(1). The major obstacle to this end is how to handle a long induced cycle as an obstruction. To fix this issue, we define the necklace graphs and investigate their structural properties. We also show that the LRW1-Vertex Deletion has a polynomial kernel.

A dominating set $D$ in a graph is a subset of its vertex set such that each vertex is either in $D$ or has a neighbor in $D$. In this paper, we are interested in the enumeration of (inclusionwise) minimal dominating sets in graphs, called the Dom-Enum problem. It is well known that this problem can be polynomially reduced to the Trans-Enum problem in hypergraphs, i.e., the problem of enumerating all minimal transversals in a hypergraph. First, we show that the Trans-Enum problem can be polynomially reduced to the Dom-Enum problem. As a consequence there exists an output-polynomial time algorithm for the Trans-Enum problem if and only if there exists one for the Dom-Enum problem. Second, we study the Dom-Enum problem in some graph classes. We give an output-polynomial time algorithm for the Dom-Enum problem in split graphs and introduce the completion of a graph to obtain an output-polynomial time algorithm for the Dom-Enum problem in $P_6$-free chordal graphs, a proper superclass of split graphs. Finally, we investigate the complexity of the enumeration of (inclusionwise) minimal connected dominating sets and minimal total dominating sets of graphs. We show that there exists an output-polynomial time algorithm for the Dom-Enum problem (or, equivalently, Trans-Enum problem) if and only if there exists one for the following enumeration problems: minimal total dominating sets, minimal total dominating sets in split graphs, minimal connected dominating sets in split graphs, minimal dominating sets in co-bipartite graphs.

Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs which has good algorithmic and structural properties. We compare two possible definitions of the rank-width of directed graphsn named bi-rank-width and GF(4)-rank-width. They turn out to be equivalent. We propose algebraic graph operations that handle both efficiently, similar to the one that we have given for the rank-width of undirected graphs. We give approximation recognition algorithms for the two parameters, and then, a polynomial time approximation algorithm for the clique-width of directed graphs. We also define a notion of vertex-minor for GF(4)-rank-width and prove that for fixed k there is a finite list C_k of directed graphs such that a directed graph has GF(4)-rank-width at most k if and only if it has no vertex-minor isomorphic to a directed graph in C_k.