2026-07-26T01:42:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14104 2024-03-06T10:53:28Z ddc:004 open_access

Twin-width III: Max Independent Set, Min Dominating Set, and Coloring Bonnet, Édouard Geniet, Colin Kim, Eun Jung Thomassé, Stéphan Watrigant, Rémi Twin-width Max Independent Set Min Dominating Set Coloring Parameterized Algorithms Approximation Algorithms Exact Algorithms We recently introduced the notion of twin-width, a novel graph invariant, and showed that first-order model checking can be solved in time f(d,k)n for n-vertex graphs given with a witness that the twin-width is at most d, called d-contraction sequence or d-sequence, and formulas of size k [Bonnet et al., FOCS '20]. The inevitable price to pay for such a general result is that f is a tower of exponentials of height roughly k. In this paper, we show that algorithms based on twin-width need not be impractical. We present 2^{O(k)}n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence of the graph is given in input. We further show how to solve the weighted version of k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in the slightly worse running time 2^{O(k log k)}n. Up to logarithmic factors in the exponent, all these running times are optimal, unless the Exponential Time Hypothesis fails. Like our FO model checking algorithm, these new algorithms are based on a dynamic programming scheme following the sequence of contractions forward. We then show a second algorithmic use of the contraction sequence, by starting at its end and rewinding it. As an example of such a reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twin-width classes are χ-bounded. This significantly extends the χ-boundedness of bounded rank-width classes, and does so with a very concise proof. It readily yields a constant approximation for Max Independent Set on K_t-free graphs of bounded twin-width, and a 2^{O(OPT)}-approximation for Min Coloring on bounded twin-width graphs. We further observe that a constant approximation for Max Independent Set on bounded twin-width graphs (but arbitrarily large clique number) would actually imply a PTAS. The third algorithmic use of twin-width builds on the second one. Playing the contraction sequence backward, we show that bounded twin-width graphs can be edge-partitioned into a linear number of bicliques, such that both sides of the bicliques are on consecutive vertices, in a fixed vertex ordering. This property is trivially shared with graphs of bounded average degree. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in time O(n log n) and time O(n² log n), respectively. In sharp contrast, even Diameter does not admit a truly subquadratic algorithm on bounded twin-width graphs, unless the Strong Exponential Time Hypothesis fails. The fourth algorithmic use of twin-width builds on the so-called versatile tree of contractions [Bonnet et al., SODA '21], a branching and more robust witness of low twin-width. We present constant-approximation algorithms for Min Dominating Set and related problems, on bounded twin-width graphs, by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping accordingly to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Colin Geniet and Eun Jung Kim and Stéphan Thomassé and Rémi Watrigant 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.35 urn:nbn:de:0030-drops-141044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.35 eng https://creativecommons.org/licenses/by/4.0/legalcode