English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We recently introduced the graph invariant twin-width, and showed thatfirst-order model checking can be solved in time $f(d,k)n$ for $n$-vertexgraphs 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 etal., 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 showthat 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 is provided. Wefurther show how to solve weighted $k$-Independent Set, Subgraph Isomorphism,and Induced Subgraph Isomorphism, in time $2^{O(k \log k)}n$. These algorithmsare based on a dynamic programming scheme following the sequence ofcontractions forward. We then show a second algorithmic use of the contractionsequence, by starting at its end and rewinding it. As an example, we establishthat bounded twin-width classes are $\chi$-bounded. This significantly extendsthe $\chi$-boundedness of bounded rank-width classes, and does so with a veryconcise proof. The third algorithmic use of twin-width builds on the secondone. Playing the contraction sequence backward, we show that bounded twin-widthgraphs can be edge-partitioned into a linear number of bicliques, such thatboth sides of the bicliques are on consecutive vertices, in a fixed vertexordering. Given that biclique edge-partition, we show how to solve theunweighted Single-Source Shortest Paths and hence All-Pairs Shortest Paths insublinear time $O(n \log n)$ and time $O(n^2 \log n)$, respectively. Finally weshow that Min Dominating Set and related problems have constant integralitygaps on bounded twin-width classes, thereby getting constant approximations onthese classes.

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