Twin-width III: Max Independent Set and Coloring
Bonnet, Edouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2021), Twin-width III: Max Independent Set and Coloring, in Bansal, Nikhil; Merelli, Emanuela; Worrell, James, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, p. 35:1--35:20. 10.4230/LIPIcs.ICALP.2021.35
TypeCommunication / Conférence
Conference title48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Book title48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Book authorBansal, Nikhil; Merelli, Emanuela; Worrell, James
MetadataShow full item record
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)We recently introduced the graph invariant twin-width, 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 2O(k)n-time algorithms for k-Independent Set, r-Scattered Set, k-Clique, and k-Dominating Set when an O(1)-sequence is provided. We further show how to solve weighted k-Independent Set, Subgraph Isomorphism, and Induced Subgraph Isomorphism, in time 2O(klogk)n. These 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 this reverse scheme, we present a polynomial-time algorithm that properly colors the vertices of a graph with relatively few colors, 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. 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. Given that biclique edge-partition, we show how to solve the unweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths in sublinear time O(nlogn) and time O(n2logn), respectively.
Subjects / KeywordsTwin-width; Max Independent Set; Min Dominating Set; Coloring; Parameterized Algorithms; Approximation Algorithms; Exact Algorithms
Showing items related by title and author.
Bonamy, Marthe; Bonnet, Edouard; Bousquet, Nicolas; Charbit, Pierre; Giannopoulos, Panos; Kim, Eun Jung; Rzążewski, P.; Sikora, Florian; Thomassé, S. (2021) Article accepté pour publication ou publié