# Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring

## Abstract.

*JACM*’22]. 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 first-order 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 \(\chi\)-bounded. This significantly extends the \(\chi\)-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(\text{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 polynomial-time approximation scheme. 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^2 \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.,

*Comb. Theory*’22], 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 according to a problem-dependent criterion. At the reached node, a greedy approach yields the desired approximation.

### Keywords

### MSC codes

## Get full access to this article

View all available purchase options and get full access to this article.

## References

*J. Combin. Theory Ser. A*, 111 (2005), pp. 310–326.

*J. ACM*, 41 (1994), pp. 153–180.

*STACS 2023*, P. Berenbrink, P. Bouyer, A. Dawar, and M. M. Kanté, eds., Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2023, 10.

*J. Comput. Syst. Sci.*, 75 (2009), pp. 423–434.

*Adv. Comb.*, (2020), https://doi.org/10.19086/aic.13668.

*Comb. Theory*, 2 (2022), https://doi.org/10.5070/C62257876.

*Algorithmica*, 84 (2022), pp. 3300–3337.

*J. ACM*, 69 (2022), pp. 1–46.

*Combinatorica*, 41 (2021), pp. 299–318.

*SIAM J. Comput.*, 15 (1986), pp. 703–724.

*Introduction to Algorithms*, 3rd ed., MIT Press, Cambridge, MA, 2009.

*ACM Trans. Algorithms*, 15 (2019), pp. 33:1–33:57.

*Inform. and Comput.*, 85 (1990), pp. 12–75.

*Theory Comput. Syst.*, 33 (2000), pp. 125–150.

*J. ACM*, 52 (2005), pp. 866–893.

*Combinatorica*, 14 (1994), pp. 23–34.

*STOC ’14: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing*, 2014, pp. 624–633, https://doi.org/10.1145/2591796.2591884.

*European J. Combin.*, 33 (2012), pp. 679–683.

*European J. Combin.*, 34 (2013), pp. 833–840.

*J. Graph Algorithms Appl.*, 3 (1999), pp. 1–27.

*Algorithmica*, 27 (2000), pp. 275–291.

*Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs*, preprint, https://arxiv.org/abs/1609.08403, 2016.

*Proceedings 32nd Annual Symposium of Foundations of Computer Science*1991, San Juan, PR, IEEE, 1991, pp. 2–12.

*SIAM J. Comput.*, 31 (2001), pp. 113–145.

*J. Comput. Syst. Sci.*, 77 (2011), pp. 91–106.

*Ann. Pure Appl. Log.*, 130 (2004), pp. 3–31.

*J. Comput. Syst. Sci.*, 30 (1985), pp. 209–221.

*Combinatorica*, 1 (1981), pp. 169–197.

*Discrete Comput. Geom.*, 2 (1987), pp. 127–151.

*J. Comput. Syst. Sci.*, 62 (2001), pp. 367–375.

*J. Comput. Syst. Sci.*, 63 (2001), pp. 512–530.

*J. Comput. Syst. Sci.*, 9 (1974), pp. 256–278.

*Discrete Math.*, 13 (1975), pp. 383–390.

*Comment. Math. Univ. Carolin.*, 15 (1974), pp. 307–309.

*Comput. J.*, 51 (2008), pp. 122–136.

*J. Comb. Optim.*, 37 (2019), pp. 1283–1311.

## Information & Authors

### Information

#### Published In

#### Copyright

#### History

**Submitted**: 24 May 2021

**Accepted**: 10 July 2024

**Published online**: 16 October 2024

#### Keywords

#### MSC codes

### Authors

#### Funding Information

**Funding:**This work was supported by the ANR projects TWIN-WIDTH (ANR-21-CE48-0014) and Digraphs (ANR-19-CE48-0013).

## Metrics & Citations

### Metrics

### Citations

If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.

#### Cited By

There are no citations for this item

## View Options

**Access via your Institution**- Questions about how to access this content? Contact SIAM at
**[email protected]**.