Abstract
For any ε > 0, we give a polynomialtime n^εapproximation algorithm for Max Independent Set in graphs of bounded twinwidth given with an O(1)sequence. This result is derived from the following timeapproximation tradeoff: We establish an O(1)^{2^q1}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 polynomialtime 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 twinwidth 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 indepth study of the approximability of problems in graphs of bounded twinwidth. Prior to this paper, essentially the only such result was a polynomialtime 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 TwinWidth}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {10:110:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17662},
URN = {urn:nbn:de:0030drops176629},
doi = {10.4230/LIPIcs.STACS.2023.10},
annote = {Keywords: Approximation algorithms, bounded twinwidth}
}
Keywords: 

Approximation algorithms, bounded twinwidth 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 