Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

MaRDI QIDQ6405123zbMATH OpenFDO

Authors Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant

Publication date 15 July 2022

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Abstract: For any $varepsilon>0$, we give a polynomial-time $n^{v}arepsilon$-approximation algorithm for Max Independent Set in graphs of bounded twin-width given with an $O(1)$-sequence. This result is derived from the 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 $qgeqslant0$. Guided by the same framework, we obtain similar approximation algorithms for Min Coloring and Max Induced Matching. In general graphs, all these problems are known to be highly inapproximable: for any $varepsilon>0$, a polynomial-time $n^{1-varepsilon}$-approximation for any of them would imply that P$=$NP [Hastad, FOCS '96; Zuckerman, ToC '07; Chalermsook et al., SODA '13]. We generalize the algorithms for Max Independent Set and Max Induced Matching to the independent (induced) packing of any fixed connected graph $H$. In contrast, we show that such approximation guarantees on graphs of bounded twin-width given with an $O(1)$-sequence are very unlikely for Min Independent Dominating Set, and somewhat unlikely for Longest Path and Longest Induced Path. Regarding the existence of better approximation algorithms, there is a (very) light evidence that the obtained approximation factor of $n^{v}arepsilon$ for Max Independent Set may be best possible. This is the first in-depth study of the approximability of problems in graphs of bounded twin-width. Prior to this paper, essentially the only such result was a~polynomial-time $O(1)$-approximation algorithm for Min Dominating Set [Bonnet et al., ICALP '21].

This page was built for publication: Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405123)