Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

Jul 16, 2026

Upload by Eliana

The work establishes strong hardness of approximation for Max Independent Set on graphs with bounded twin-width, showing that even on graphs of twin-width at most 4, no polynomial-time nγ/(log log n)^2-approximation exists unless the Exponential-Time Hypothesis (ETH) fails. The bound continues to hold when a 4-sequence is included in the input and closely matches known nO(1/log log n) algorithms. It also proves parallel results for Min Coloring, and studies parameterized complexity for k-Independent Set and k-Dominating Set under bounded-radius merge-width.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

Introduction

Independent Set Hardness in Graphs of Bounded Twin-Width and Merge-Width

arXiv :2607 .00244v1 [ cs .CC] 30 Jun 2026 Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width Édouard Bonnet \# Ñ Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France Maël Dumas \# Institute of Informatics, University of Warsaw, Poland Julien Duron \# Institute of Informatics, University of Warsaw, Poland ~~ Abstract ~~ For every ε > 0 , Max Independent Set admits a polynomial-time nε-approximation algorithm on n-vertex graphs of effectively bounded twin-width [Bergé et al., STACS ’23] . The approximation factor actually obtained is more precisely nO(1/ log log n) . Prior to the current paper, no approximation hardness was known for this problem, and the existence of a polynomial-time approximation scheme (PTAS) was repeatedly raised as an open question. We answer this question in a strong sense: We show that there is a constant γ > 0 such that a polynomial-time nγ/(log log n)2-approximation algorithm for Max Independent Set on graphs of twin-width at most 4 would refute the Exponential-Time Hypothesis (ETH) . This lower bound further holds if a 4-sequence is provided as part of the input. We show the same hardness of approximation for Min Coloring, which also has a nearly matching nO(1/ log log n)-approximation algorithm on graphs of effectively bounded twin-width. We also clarify the parameterized complexity of k-Independent Set on graphs of bounded radius-r merge-width when the range of r is limited. There is a fixed-parameter tractable algorithm for k-Independent Set on graphs given with radius-2O (k2 ) merge sequences of bounded width [Dreier and Toruńczyk, STOC’25] . We complement this result by showing that k-Independent Set is W[1]-hard on graphs given with radius-o(k) merge sequences of bounded width. We further show that this result also holds for k-Dominating Set. Funding JD received funding from ERC grant BUKA (No. 101126229) . MD and JD were supported by the project BOBR that has received funding from ERC under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 948057. Acknowledgements We want to thank Karolina Drabik, Jakub Nowakowski, Nikolas Mählmann, and Szymon Toruńczyk for fruitful discussions at an early stage of this project. 1 Introduction The problem of finding in a graph a largest subset of pairwise non-adjacent vertices, Max Independent Set (MIS for short), is NP-complete [20], and very hard to approximate: For any ε > 0 , an n 1−ε-approximation algorithm would imply that P = NP [22, 26] . The best known polynomial-time approximation factor is n(log~~ ~~lolog3gnn)2 [18] . In contrast, this central problem enjoys much better approximation algorithms on structured graph classes. A historical example is that of planar graphs where, due to Baker’s shifting technique, a polynomial-time approximation scheme (PTAS) exists [2] . MIS also has a PTAS on minor-free classes [21] and on disk graphs [12] . If a geometric representation is provided, there is, for every ε > 0 , an nε-approximation algorithm for the independence number of the intersection graph of n curves every two of which have at most a constant number of intersections [19], and a quasipolynomial-time approximation scheme (QPTAS) for general string graphs [1] . 2 Independent Set Hardness in Graphs of Bounded Twin-Width and Merge-Width In this paper, our focus is on classes of bounded twin-width [11] and of bounded mergewidth [17] . These graph parameters were introduced in 2020 and 2025, respectively. Classes of bounded twin-width include classes of bounded clique-width, classes excluding a fixed minor, unit interval graphs, and d-dimensional grids [11] . Classes of bounded merge-width are even more general and further include classes of bounded expansion [17] . The main algorithmic application of classes of bounded twin-width and of bounded merge-width, when bounded-width witnesses are given, is that first-order model c

FAQs

What approximation hardness does the paper prove for Max Independent Set on graphs of bounded twin-width?

It shows that, assuming ETH, Max Independent Set on n-vertex graphs of twin-width at most 4 admits no polynomial-time nγ/(log log n)^2-approximation algorithm.

Does the hardness result change when a 4-sequence is provided as input?

No. The same hardness-of-approximation bound holds even if a 4-sequence is part of the input.

What parameterized complexity results are given for k-Independent Set and k-Dominating Set with bounded radius-r merge-width?

The paper gives an FPT algorithm for k-Independent Set when merge sequences correspond to radius-2O(k^2) with bounded width, and proves W[1]-hardness for k-Independent Set (and for k-Dominating Set) when r is limited to radius-o(k).

Jul 16, 2026

Upload by Eliana