Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
| Autor: | Bergé, Pierre, Bonnet, Édouard, Déprés, Hugues, Watrigant, Rémi |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Theory of computation → Design and analysis of algorithms Computational Complexity (cs.CC) 68W25 Approximation algorithms bounded twin-width Computer Science - Computational Complexity Theory of computation → Graph algorithms analysis Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics - Combinatorics Data Structures and Algorithms (cs.DS) Combinatorics (math.CO) F.2.2 Computer Science - Discrete Mathematics |
| DOI: | 10.4230/lipics.stacs.2023.10 |
| Popis: | For any $\varepsilon > 0$, we give a polynomial-time $n^\varepsilon$-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 $q \geqslant 0$. 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^\varepsilon$ 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]. 32 pages, 3 figures, 1 table |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|