2026-07-23T07:31:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17662 2024-03-06T11:00:15Z ddc:004 open_access

Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width Bergé, Pierre Bonnet, Édouard Déprés, Hugues Watrigant, Rémi Approximation algorithms bounded twin-width 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Bergé and Édouard Bonnet and Hugues Déprés and Rémi Watrigant 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.10 urn:nbn:de:0030-drops-176629 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.10 eng https://creativecommons.org/licenses/by/4.0/legalcode