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

For any $\varepsilon > 0$, we give a polynomial-time$n^\varepsilon$-approximation algorithm for Max Independent Set in graphs ofbounded twin-width given with an $O(1)$-sequence. This result is derived fromthe following time-approximation trade-off: We establish an$O(1)^{2^q-1}$-approximation algorithm running in time $\exp(O_q(n^{2^{-q}}))$,for every integer $q \geqslant 0$. Guided by the same framework, we obtainsimilar approximation algorithms for Min Coloring and Max Induced Matching. Ingeneral graphs, all these problems are known to be highly inapproximable: forany $\varepsilon > 0$, a polynomial-time $n^{1-\varepsilon}$-approximation forany of them would imply that P$=$NP [Hastad, FOCS '96; Zuckerman, ToC '07;Chalermsook et al., SODA '13]. We generalize the algorithms for Max IndependentSet and Max Induced Matching to the independent (induced) packing of any fixedconnected graph $H$. In contrast, we show that such approximation guarantees ongraphs of bounded twin-width given with an $O(1)$-sequence are very unlikelyfor Min Independent Dominating Set, and somewhat unlikely for Longest Path andLongest Induced Path. Regarding the existence of better approximationalgorithms, there is a (very) light evidence that the obtained approximationfactor of $n^\varepsilon$ for Max Independent Set may be best possible. This isthe first in-depth study of the approximability of problems in graphs ofbounded twin-width. Prior to this paper, essentially the only such result wasa~polynomial-time $O(1)$-approximation algorithm for Min Dominating Set [Bonnetet al., ICALP '21].

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width