| Abstrakt: |
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., 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 2O(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 2O(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 x-bounded. This significantly extends the x-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 Kt-free graphs of bounded twin-width and a 2O(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² 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. [ABSTRACT FROM AUTHOR] |
