Search

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)n^3$ and show that any minimal graph of lettericity more than $k$ has at most $2^{O(k^2\log k)}$ vertices., Comment: 16pages + 3pages appendix. Submitted to a journal

A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a structural perspective. In this paper we perform the first systematic computational complexity study of pivot-minors. We first prove that the Pivot-Minor problem, which asks if a given graph $G$ contains a pivot-minor isomorphic to a given graph $H$, is NP-complete. If $H$ is not part of the input, we denote the problem by $H$-Pivot-Minor. We give a certifying polynomial-time algorithm for $H$-Pivot-Minor when (1) $H$ is an induced subgraph of $P_3+tP_1$ for some integer $t\geq 0$, (2) $H=K_{1,t}$ for some integer $t\geq 1$, or (3) $|V(H)|\leq 4$ except when $H \in \{K_4,C_3+ P_1\}$. Let ${\cal F}_H$ be the set of induced-subgraph-minimal graphs that contain a pivot-minor isomorphic to $H$. To prove the above statement, we either show that there is an integer $c_H$ such that all graphs in ${\cal F}_H$ have at most $c_H$ vertices, or we determine ${\cal F}_H$ precisely, for each of the above cases., Comment: 33 pages, 9 figures. An extended abstract appeared in the proceedings of WG2018

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., Comment: Conference version to appear at the European Symposium on Algorithms (ESA 2023)

A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or $\star$ (both an arc and a non-arc). In a series of papers, Hell and co-authors proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems, where arcs and non-arcs can be both mapped to $\star$-arcs, while a non-arc cannot be mapped to an arc, and vice-versa. Even though Matrix Partition Problems are generalisations of CSPs, they share with them the property of being ``intrinsically'' combinatorial. So, the question of a possible P-time vs NP-complete dichotomy is a very natural one and was raised in Hell et al.'s papers. We propose a generalisation of Matrix Partitions to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partitions are P-time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partitions on directed graphs are not P-time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partitions. We then turn our attention to Matrix Partitions that can be described by finite sets of (induced-subgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP-complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partitions as it is well-known that CSP is tractable on the class of trees.

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.

Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) 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 from 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: (1) 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; (2) 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., Comment: 26 pages, 5 figures; accepted to SIAM Journal on Discrete Mathematics

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 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 is 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 {\em 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 Rz{\k{a}}{\.{z}}ewski, Finding small-width connected path-decompositions in polynomial time. Theor. Comput. Sci., 794:85-100, 2019]. For our algorithm, we enrich the typical sequence technique that is able to deal with the connectivity demand. Typical sequences have been introduced in [Bodlaender and Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21(2):358-402, 1996] for the design of linear parameterized algorithms for treewidth and pathwidth. The proposed extension is based on an encoding of the connectivity property that is quite versatile and may be adapted so to deliver linear parameterized algorithms for the connected variants of other width parameters as well.

We prove that one can count in polynomial time the number of minimal transversals of $\beta$-acyclic hypergraphs. In consequence, we can count in polynomial time the number of minimal dominating sets of strongly chordal graphs, continuing the line of research initiated in [M.M. Kant\'e and T. Uno, Counting Minimal Dominating Sets, TAMC'17].

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, $\mathbf{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 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] and the rank-based approach introduced in [Bodlaender, Cygan, Kratsch and Nederlof, ICALP 2013]. 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 $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 $\mathbf{Q}$-rank-width and the rank-width of the input graph.

Given a clique-width $k$-expression of a graph $G$, we provide $2^{O(k)}\cdot 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)}\cdot n$ time algorithm for Feedback Vertex Set. The best running times for all the considered cases were either $2^{O(k\cdot \log(k))}\cdot n^{O(1)}$ or worse.

In this paper, we prove that, given a clique-width $k$-expression of an $n$-vertex graph, \textsc{Hamiltonian Cycle} can be solved in time $n^{\mathcal{O}(k)}$. This improves the naive algorithm that runs in time $n^{\mathcal{O}(k^2)}$ by Espelage et al. (WG 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)}$ (SIAM. J. Computing 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., Comment: 17 page, 3 figure, Full version of the accepted paper in WADS 2017, corrected the characterization of red-blue Eulerian digraphs

The linear induced matching width (LMIM-width) of a graph is a width parameter defined by using the notion of branch-decompositions of a set function on ternary trees. In this paper we study output-polynomial enumeration algorithms on graphs of bounded LMIM-width and graphs of bounded local LMIM-width. In particular, we show that all 1-minimal and all 1-maximal (\sigma,\rho)-dominating sets, and hence all minimal dominating sets, of graphs of bounded LMIM-width can be enumerated with polynomial (linear) delay using polynomial space. Furthermore, we show that all minimal dominating sets of a unit square graph can be enumerated in incremental polynomial time.

In the companion paper [Linear rank-width of distance-hereditary graphs I. A polynomial-time algorithm, Algorithmica 78(1):342--377, 2017], we presented a characterization of the linear rank-width of distance-hereditary graphs, from which we derived an algorithm to compute it in polynomial time. In this paper, we investigate structural properties of distance-hereditary graphs based on this characterization. First, we prove that for a fixed tree $T$, every distance-hereditary graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to $T$. We extend this property to bigger graph classes, namely, classes of graphs whose prime induced subgraphs have bounded linear rank-width. Here, prime graphs are graphs containing no splits. We conjecture that for every tree $T$, every graph of sufficiently large linear rank-width contains a vertex-minor isomorphic to $T$. Our result implies that it is sufficient to prove this conjecture for prime graphs. For a class $\Phi$ of graphs closed under taking vertex-minors, a graph $G$ is called a vertex-minor obstruction for $\Phi$ if $G\notin \Phi$ but all of its proper vertex-minors are contained in $\Phi$. Secondly, we provide, for each $k\ge 2$, a set of distance-hereditary graphs that contains all distance-hereditary vertex-minor obstructions for graphs of linear rank-width at most $k$. Also, we give a simpler way to obtain the known vertex-minor obstructions for graphs of linear rank-width at most $1$., Comment: 38 pages, 13 figures, 1 table, revised journal version. A preliminary version of Section 5 appeared in the proceedings of WG14

Linear rankwidth is a linearized variant of rankwidth, introduced by Oum and Seymour [Approximating clique-width and branch-width. J. Combin. 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., Comment: 29 pages, 9 figures, An extended abstract appeared in IPEC2015

We provide a doubly exponential upper bound in $p$ on the size of forbidden pivot-minors for symmetric or skew-symmetric matrices over a fixed finite field $\mathbb{F}$ of linear rank-width at most $p$. As a corollary, we obtain a doubly exponential upper bound in $p$ on the size of forbidden vertex-minors for graphs of linear rank-width at most $p$. This solves an open question raised by Jeong, Kwon, and Oum [Excluded vertex-minors for graphs of linear rank-width at most $k$. European J. Combin., 41:242--257, 2014]. We also give a doubly exponential upper bound in $p$ on the size of forbidden minors for matroids representable over a fixed finite field of path-width at most $p$. Our basic tool is the pseudo-minor order used by Lagergren [Upper Bounds on the Size of Obstructions and Interwines, Journal of Combinatorial Theory Series B, 73:7--40, 1998] to bound the size of forbidden graph minors for bounded path-width. To adapt this notion into linear rank-width, it is necessary to well define partial pieces of graphs and merging operations that fit to pivot-minors. Using the algebraic operations introduced by Courcelle and Kant\'e, and then extended to (skew-)symmetric matrices by Kant\'e and Rao, we define boundaried $s$-labelled graphs and prove similar structure theorems for pivot-minor and linear rank-width., Comment: 28 pages, 1 figure

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 neighbour in $D$. In this paper, we are interested in the enumeration of (inclusion-wise) 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. Firstly 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. Secondly, 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 (inclusion-wise) 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., Comment: 15 pages, 3 figures, In revision

An output-polynomial algorithm for the listing of minimal dominating sets in graphs is a challenging open problem and is known to be equivalent to the well-known Transversal problem which asks for an output-polynomial algorithm for listing the set of minimal hitting sets in hypergraphs. We give a polynomial delay algorithm to list the set of minimal dominating sets in chordal graphs, an important and well-studied graph class where such an algorithm was open for a while., Comment: 13 pages, 1 figure, submitted

The Transversal problem, i.e, the enumeration of all the minimal transversals of a hypergraph in output-polynomial time, i.e, in time polynomial in its size and the cumulated size of all its minimal transversals, is a fifty years old open problem, and up to now there are few examples of hypergraph classes where the problem is solved. A minimal dominating set in a graph is a subset of its vertex set that has a non empty intersection with the closed neighborhood of every vertex. It is proved in [M. M. Kant\'e, V. Limouzy, A. Mary, L. Nourine, On the Enumeration of Minimal Dominating Sets and Related Notions, In Revision 2014] that the enumeration of minimal dominating sets in graphs and the enumeration of minimal transversals in hypergraphs are two equivalent problems. Hoping this equivalence can help to get new insights in the Transversal problem, it is natural to look inside graph classes. It is proved independently and with different techniques in [Golovach et al. - ICALP 2013] and [Kant\'e et al. - ISAAC 2012] that minimal edge dominating sets in graphs (i.e, minimal dominating sets in line graphs) can be enumerated in incremental output-polynomial time. We provide the first polynomial delay and polynomial space algorithm that lists all the minimal edge dominating sets in graphs, answering an open problem of [Golovach et al. - ICALP 2013]. Besides the result, we hope the used techniques that are a mix of a modification of the well-known Berge's algorithm and a strong use of the structure of line graphs, are of great interest and could be used to get new output-polynomial time algorithms., Comment: proofs simplified from previous version, 12 pages, 2 figures

Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every $n$-vertex distance-hereditary graph, equivalently a graph of rank-width at most $1$, can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every $n$-element matroid of branch-width at most $2$ can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, provided that the matroid is given by an independent set oracle. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50--79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of `limbs' of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization., Comment: 28 pages, 3 figures, 2 table. A preliminary version appeared in the proceedings of WG'14

We prove that a connected graph has linear rank-width 1 if and only if it is a distance-hereditary graph and its split decomposition tree is a path. An immediate consequence is that one can decide in linear time whether a graph has linear rank-width at most 1, and give an obstruction if not. Other immediate consequences are several characterisations of graphs of linear rank-width 1. In particular a connected graph has linear rank-width 1 if and only if it is locally equivalent to a caterpillar if and only if it is a vertex-minor of a path [O-joung Kwon and Sang-il Oum, Graphs of small rank-width are pivot-minors of graphs of small tree-width, arxiv:1203.3606] if and only if it does not contain the co-K_2 graph, the Net graph and the 5-cycle graph as vertex-minors [Isolde Adler, Arthur M. Farley and Andrzej Proskurowski, Obstructions for linear rank-width at most 1, arxiv:1106.2533]., Comment: 9 pages, 2 figures. Not to be published

In [Rank-Width and Well-Quasi-Ordering of Skew-Symmetric or Symmetric Matrices, arXiv:1007.3807v1] Oum proved that, for a fixed finite field $\mathbf{F}$, any infinite sequence $M_1,M_2,...$ of (skew) symmetric matrices over $\mathbf{F}$ of bounded $\mathbf{F}$-rank-width has a pair $i< j$, such that $M_i$ is isomorphic to a principal submatrix of a principal pivot transform of $M_j$. We generalise this result to $\sigma$-symmetric matrices introduced by Rao and myself in [The Rank-Width of Edge-Coloured Graphs, arXiv:0709.1433v4]. (Skew) symmetric matrices are special cases of $\sigma$-symmetric matrices. As a by-product, we obtain that for every infinite sequence $G_1,G_2,...$ of directed graphs of bounded rank-width there exist a pair $i

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is \emph{nicely locally cwd-decomposable}. This notion generalizes that of a \emph{nicely locally tree-decomposable} class. The graphs of such classes can be covered by graphs of bounded \emph{clique-width} with limited overlaps. We also consider such labelings for \emph{bounded} first-order formulas on graph classes of \emph{bounded expansion}. Some of these results are extended to counting queries.

Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss an extension of the notion of rank-width to edge-colored graphs. A C-colored graph is a graph where the arcs are colored with colors from the set C. There is not a natural notion of rank-width for C-colored graphs. We define two notions of rank-width for them, both based on a coding of C-colored graphs by edge-colored graphs where each edge has exactly one color from a field F and named respectively F-rank-width and F-bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for F-colored graphs and prove that F-colored graphs of bounded F-rank-width are characterised by a finite list of F-colored graphs to exclude as vertex-minors. A cubic-time algorithm to decide whether a F-colored graph has F-rank-width (resp. F-bi-rank-width) at most k, for fixed k, is also given. Graph operations to check MSOL-definable properties on F-colored graphs of bounded rank-width are presented. A specialisation of all these notions to (directed) graphs without edge colors is presented, which shows that our results generalise the ones in undirected graphs., Comment: It is an update of the last version generalising all the results to edge-colored graphs and answering some of the raised questions