Search

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most 2O(n) pairwise non-isomorphic n-vertex graphs. [ABSTRACT FROM AUTHOR]

We study the graph parameter elimination distance to bounded degree, which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d, k decides in time f(k, d) · nc for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most k. [ABSTRACT FROM AUTHOR]

First-order logic (FO) can express many algorithmic problems on graphs, such as the independent set and dominating set problem parameterized by solution size. However, FO cannot express the very simple algorithmic question whether two vertices are connected. We enrich FO with connectivity predicates that are tailored to express algorithmic graph problems that are commonly studied in parameterized algorithmics. By adding the atomic predicates connk (x,y, z1, . . ., zk ) that hold true in a graph if there exists a path between (the valuations of) x and y after (the valuations of) z1, . . ., zk have been deleted, we obtain separator logic FO+conn.We show that separator logic can express many interesting problems, such as the feedback vertex set problem and elimination distance problems to first-order definable classes. Denote by FO + connk the fragment of separator logic that is restricted to connectivity predicates with at most k + 2 variables (that is, at most k deletions), we show that FO + connk+1 is strictly more expressive than FO + connk for all k ≥ 0. We then study the limitations of separator logic and prove that it cannot express planarity, and, in particular, not the disjoint paths problem. We obtain the stronger disjoint-paths logic FO + DP by adding the atomic predicates disjoint-pathsk [(x1,y1), . . ., (xk,yk )] that evaluate to true if there are internally vertex-disjoint paths between (the valuations of) xi and yi for all 1 ≤ i ≤ k. Disjoint-paths logic can express the disjoint paths problem, the problem of (topological) minor containment, the problem of hitting (topological) minors, and many more. Again, we show that the fragments FO + DPk that use predicates for at most k disjoint paths form a strict hierarchy of expressiveness. Finally, we compare the expressive power of the new logics with that of transitive-closure logics and monadic second-order logic. [ABSTRACT FROM AUTHOR]

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [2010, 2011], form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes (parameterized by the length of the input formula). At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighborhood covers for nowhere dense graphs. This extends and improves previous constructions of neighborhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterization of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rankpreserving" version of Gaifman's locality theorem. [ABSTRACT FROM AUTHOR]

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order transductions of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth covers (or colorings), replacing treedepth by its dense analogue called shrubdepth. [ABSTRACT FROM AUTHOR]

For \alpha > 1, an \alpha -approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem \scrQ and outputs an instance (I\prime, k\prime) (of a problem \scrQ \prime) of size bounded by a function of k such that, for every c \geq 1, a c-approximate solution for the new instance can be turned into a (c \cdot \alpha)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every \alpha > 1, Connected Dominating Set admits a polynomial-size \alpha -approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class \scrC is somewhere dense and closed under taking subgraphs, then for some value of r \in N there cannot exist an \alpha -approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on \scrC for any \alpha > 1 (assuming FPT \not = W[1]). [ABSTRACT FROM AUTHOR]

Nowhere dense classes of graphs [21, 22] are very general classes of uniformly sparse graphs with several seemingly unrelated characterisations. From an algorithmic perspective, a characterisation of these classes in terms of uniform quasi-wideness, a concept originating in finite model theory, has proved to be particularly useful. Uniform quasi-wideness is used in many fpt-algorithms on nowhere dense classes. However, the existing constructions showing the equivalence of nowhere denseness and uniform quasi-wideness imply a non-elementary blow up in the parameter dependence of the fpt-algorithms, making them infeasible in practice. As a first main result of this article, we use tools from logic, in particular from a sub-field of model theory known as stability theory, to establish polynomial bounds for the equivalence of nowhere denseness and uniform quasi-wideness. A powerfulmethod in parameterized complexity theory is to compute a problem kernel in a pre-computation step, that is, to reduce the input instance in polynomial time to a sub-instance of size bounded in the parameter only (independently of the input graph size). Our new tools allow us to obtain for every fixed radius r ∈ N a polynomial kernel for the distance-r dominating set problem on nowhere dense classes of graphs. This result is particularly interesting, as it implies that for every class C of graphs that is closed under taking subgraphs, the distance-r dominating set problem admits a kernel on C for every value of r if, and only if, it already admits a polynomial kernel for every value of r (under the standard assumption of parameterized complexity theory that FPT ≠ W[2]). [ABSTRACT FROM AUTHOR]

The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this article, we study two structural properties of these graph classes that are of particular importance in this context: the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide. We provide experimental evaluations of several algorithms that approximate these parameters on real-world graphs. On the theoretical side, we provide a new algorithm for uniform quasi-wideness with polynomial size guarantees in graph classes of bounded expansion and show a lower bound indicating that the guarantees of this algorithm are close to optimal in graph classes with fixed excluded minor. [ABSTRACT FROM AUTHOR]

In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown that nowhere dense classes of graphs admit sparse neighborhood covers of small degree. We show that a monotone graph class admits sparse neighborhood covers if and only if it is nowhere dense. The existence of such covers for nowhere dense classes is established through bounds on so-called weak coloring numbers. The core results of this paper are various lower and upper bounds on the weak coloring numbers and other, closely related, generalized coloring numbers. We prove tight bounds for these numbers on graphs of bounded treewidth. We clarify and tighten the relation between the density of shallow minors and the various generalized coloring numbers. These upper bounds are complemented by new, stronger exponential lower bounds on the weak and strong coloring numbers, and by superpolynomial lower bounds on the weak coloring numbers on classes of polynomial expansion. Finally, we show that computing weak r-coloring numbers is NP-complete for all r ≥ 3 [ABSTRACT FROM AUTHOR]

In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ι two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at mostι vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W[1]-hardness of VCR when parameterized by ι we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W[1]-hard on bipartite graphs, is NP-hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs. [ABSTRACT FROM AUTHOR]

We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [26]. We say that a class ]> ]> C ]> of graphs admits low rank-width colorings if there exist functions ]> ]> N : N → N ]> and ]> ]> Q : N → N ]> such that for all ]> ]> p ϵ N ]> , every graph ]> ]> G ϵ C ]> can be vertex colored with at most N(p) colors such that the union of any ]> ]> i ≤ p ]> color classes induces a subgraph of rank-width at most Q(i). Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class ]> ]> C ]> of bounded expansion and every positive integer r, the class ]> ]> { G r : G ϵ C } ]> of rth powers of graphs from ]> ]> C ]> , as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every graph class admitting low rank-width colorings has the Erdős-Hajnal property and is ]> ]> χ ]> -bounded. [ABSTRACT FROM AUTHOR]

The colouring number col ( G ) of a graph G is the minimum integer k such that there exists a linear ordering of the vertices of G in which each vertex v has back-degree at most k , i.e. v has at most k neighbours u with u < v . The colouring number is a structural measure that measures the edge density of subgraphs of G . For r ≥ 1 , the numbers col r ( G ) and wcol r ( G ) generalise the colouring number, where col 1 ( G ) and wcol 1 ( G ) are equivalent to col ( G ) . For increasing values of r these measures converge to the well-known structural measures tree-width and tree-depth. For an n -vertex graph, col n ( G ) is equal to the tree-width of G and wcol n ( G ) is equal to the tree-depth of G . We show that if G excludes K t as a minor, then col r ( G ) ≤ ( t 2 ) ⋅ ( 2 r + 1 ) and wcol r ( G ) ≤ ( t 2 ) r ⋅ ( 2 r + 1 ) . It is easily observed that if G is planar, then col r ( G ) ≤ 5 r + 3 . The technically most demanding part of the paper is to show that for those graphs, wcol r ( G ) ≤ 5 r 5 . These results generalise to bounded genus graphs, i.e. if G is of genus g , then col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) and wcol r ( G ) ≤ 2 g ( 2 r + 1 ) + 5 r 5 . [ABSTRACT FROM AUTHOR]