Approximating highly inapproximable problems on graphs of bounded twin-width
Pierre Bergé, Édouard Bonnet, Hugues Déprés, Rémi Watrigant · Journal of Computer and System Sciences · 2026
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].