License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.10
URN: urn:nbn:de:0030-drops-176629
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17662/
Bergé, Pierre ;
Bonnet, Édouard ;
Déprés, Hugues ;
Watrigant, Rémi
Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
Abstract
For any ε > 0, we give a polynomial-time n^ε-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 ⩾ 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 ε > 0, a polynomial-time n^{1-ε}-approximation for any of them would imply that P=NP [Håstad, 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^ε 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].
BibTeX - Entry
@InProceedings{berge_et_al:LIPIcs.STACS.2023.10,
author = {Berg\'{e}, Pierre and Bonnet, \'{E}douard and D\'{e}pr\'{e}s, Hugues and Watrigant, R\'{e}mi},
title = {{Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {10:1--10:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17662},
URN = {urn:nbn:de:0030-drops-176629},
doi = {10.4230/LIPIcs.STACS.2023.10},
annote = {Keywords: Approximation algorithms, bounded twin-width}
}
|
Keywords: |
|
Approximation algorithms, bounded twin-width |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
