Bonnet, Édouard ;
Geniet, Colin ;
Kim, Eun Jung ;
Thomassé, Stéphan ;
Watrigant, Rémi
Twinwidth III: Max Independent Set, Min Dominating Set, and Coloring
Abstract
We recently introduced the notion of twinwidth, a novel graph invariant, and showed that firstorder model checking can be solved in time f(d,k)n for nvertex graphs given with a witness that the twinwidth is at most d, called dcontraction sequence or dsequence, 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 twinwidth need not be impractical. We present 2^{O(k)}ntime algorithms for kIndependent Set, rScattered Set, kClique, and kDominating Set when an O(1)sequence of the graph is given in input. We further show how to solve the weighted version of kIndependent 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 polynomialtime algorithm that properly colors the vertices of a graph with relatively few colors, thereby establishing that bounded twinwidth classes are χbounded. This significantly extends the χboundedness of bounded rankwidth classes, and does so with a very concise proof. It readily yields a constant approximation for Max Independent Set on K_tfree graphs of bounded twinwidth, and a 2^{O(OPT)}approximation for Min Coloring on bounded twinwidth graphs. We further observe that a constant approximation for Max Independent Set on bounded twinwidth graphs (but arbitrarily large clique number) would actually imply a PTAS.
The third algorithmic use of twinwidth builds on the second one. Playing the contraction sequence backward, we show that bounded twinwidth graphs can be edgepartitioned 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 edgepartition, we show how to solve the unweighted SingleSource Shortest Paths and hence AllPairs 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 twinwidth graphs, unless the Strong Exponential Time Hypothesis fails.
The fourth algorithmic use of twinwidth builds on the socalled versatile tree of contractions [Bonnet et al., SODA '21], a branching and more robust witness of low twinwidth. We present constantapproximation algorithms for Min Dominating Set and related problems, on bounded twinwidth graphs, by showing that the integrality gap is constant. This is done by going down the versatile tree and stopping accordingly to a problemdependent criterion. At the reached node, a greedy approach yields the desired approximation.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs.ICALP.2021.35,
author = {Bonnet, \'{E}douard and Geniet, Colin and Kim, Eun Jung and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
title = {{Twinwidth III: Max Independent Set, Min Dominating Set, and Coloring}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {35:135:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14104},
URN = {urn:nbn:de:0030drops141044},
doi = {10.4230/LIPIcs.ICALP.2021.35},
annote = {Keywords: Twinwidth, Max Independent Set, Min Dominating Set, Coloring, Parameterized Algorithms, Approximation Algorithms, Exact Algorithms}
}
02.07.2021
Keywords: 

Twinwidth, Max Independent Set, Min Dominating Set, Coloring, Parameterized Algorithms, Approximation Algorithms, Exact Algorithms 
Seminar: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Issue date: 

2021 
Date of publication: 

02.07.2021 