pith. sign in

arxiv: 2607.00244 · v1 · pith:3DQXPH5Tnew · submitted 2026-06-30 · 💻 cs.CC · cs.DM· cs.DS

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

\'Edouard Bonnet , Ma\"el Dumas , Julien Duron This is my paper

Pith reviewed 2026-07-02 16:41 UTC · model grok-4.3

classification 💻 cs.CC cs.DMcs.DS
keywords twin-widthindependent setapproximation hardnessexponential time hypothesismerge-widthW[1]-hardnesscoloring
0
0 comments X

The pith

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.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors prove an inapproximability result for Max Independent Set on graphs with twin-width at most 4. Specifically, no polynomial-time algorithm can achieve an approximation factor of n raised to γ over (log log n) squared for some positive constant γ, unless the Exponential-Time Hypothesis is false. This result holds even when a merge sequence of width 4 is provided with the input. A similar inapproximability result is shown for Min Coloring. The paper also proves that k-Independent Set is W[1]-hard when the input graphs are given with merge sequences of bounded width but radius o(k).

Core claim

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 n^{O(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 by showing that k-Independent Set is W[1]-hard on graphs given with radius-o

What carries the argument

Gap-preserving reduction from an ETH-hard problem to Max Independent Set that produces instances of twin-width at most 4 (or supplied with width-4 merge sequences).

Load-bearing premise

The reduction from an ETH-hard problem produces graphs of twin-width at most 4 while preserving the approximation gap up to the factor n^{γ/(log log n)^2}.

What would settle it

A polynomial-time algorithm achieving an n^{γ/(log log n)^2}-approximation for Max Independent Set on the twin-width-4 graphs constructed by the reduction would yield a subexponential-time algorithm for the source ETH-hard problem.

read the original abstract

For every $\varepsilon > 0$, Max Independent Set admits a polynomial-time $n^\varepsilon$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Berg\'e et al., STACS '23]. The approximation factor actually obtained is more precisely $n^{O(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 $\gamma > 0$ such that a polynomial-time $n^{\gamma/ (\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 $n^{O(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-$2^{O(k^2)}$ merge sequences of bounded width [Dreier and Toru\'nczyk, 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes that, under the Exponential Time Hypothesis, there is a constant γ > 0 such that no polynomial-time n^{γ/(log log n)^2}-approximation algorithm exists for Max Independent Set (or Min Coloring) on n-vertex graphs of twin-width at most 4, even when a 4-sequence is provided as input. It further shows W[1]-hardness of k-Independent Set and k-Dominating Set on graphs supplied with bounded-width merge sequences of radius o(k), complementing recent FPT results that require radius 2^{O(k^2)}.

Significance. If correct, the results supply nearly tight conditional hardness that matches the known n^{O(1/log log n)}-approximation algorithms on effectively bounded twin-width graphs, thereby resolving repeated open questions about the existence of a PTAS. The parameterized-complexity statements provide a clean separation on the radius parameter. The paper derives its main claims from an ETH-based reduction that preserves the stated twin-width bound and approximation gap; this is a substantive technical contribution.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'effectively bounded twin-width' is used when describing prior approximation algorithms, while the new hardness applies to twin-width exactly 4; a parenthetical clarification of the relationship between these notions would aid readers.
  2. The citations to Bergé et al. (STACS '23) and Dreier and Toruńczyk (STOC '25) should appear with full bibliographic details in the references section.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation to accept the manuscript. The report accurately captures the main contributions regarding ETH-based hardness of approximation for Max Independent Set and Min Coloring on twin-width-4 graphs, as well as the parameterized hardness results for bounded-radius merge-width.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes conditional hardness for approximation and parameterized problems via explicit reductions from the external Exponential-Time Hypothesis (ETH). The load-bearing steps are the construction of graphs with twin-width at most 4 (or bounded-width merge sequences) that preserve the approximation/parameter gap; these are presented as direct outputs of the reduction rather than fitted parameters, self-definitions, or renamings. Cited approximation and FPT results (Bergé et al., Dreier-Toruńczyk) are from independent prior work by non-overlapping authors and serve as external benchmarks, not load-bearing self-citations. No equation or claim reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Exponential Time Hypothesis as the source of hardness and on the existence of a reduction that keeps twin-width at most 4 while transferring the approximation gap.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    The entire hardness result is conditional on ETH; without it the claim does not hold.

pith-pipeline@v0.9.1-grok · 5876 in / 1243 out tokens · 26067 ms · 2026-07-02T16:41:36.858508+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages · 1 internal anchor

  1. [1]

    Approximation schemes for independ- ent set and sparse subsets of polygons.J

    1 Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for independ- ent set and sparse subsets of polygons.J. ACM, 66(4):29:1–29:40, 2019.doi:10.1145/3326122. 2 Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs.J. ACM, 41(1):153–180, 1994.doi:10.1145/174644.174650. 3 Pierre Bergé, Édouard Bonnet, an...

    work page doi:10.1145/3326122 2019

  2. [2]

    5 Andrej Bogdanov, Kenji Obata, and Luca Trevisan

    URL: https://doi.org/10.4230/LIPIcs.STACS.2023.10, doi:10.4230/ LIPICS.STACS.2023.10. 5 Andrej Bogdanov, Kenji Obata, and Luca Trevisan. A lower bound for testing 3-colorability in bounded-degree graphs. In43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, Proceedings, pages 93–102. IEEE Computer Soc...

    work page doi:10.4230/lipics.stacs.2023.10 2023

  3. [3]

    Metamorphictestingoflarge languagemodelsfornaturallanguageprocessing.doi:10.48550/arXiv

    URL: https://doi.org/10.48550/arXiv. 2504.08266,arXiv:2504.08266,doi:10.48550/ARXIV.2504.08266. 7 Édouard Bonnet.Twin-Width and Contraction Sequences

    work page internal anchor Pith review doi:10.48550/arxiv

  4. [4]

    9 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

    URL: https://www.sciencedirect.com/science/article/pii/ S002001902600027X,doi:https://doi.org/10.1016/j.ipl.2026.106646. 9 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width II: small classes.Comb. Theory, 2(2),

    work page doi:10.1016/j.ipl.2026.106646 2026

  5. [5]

    10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrig- ant

    URL: https://doi.org/10.5070/ c62257876,doi:10.5070/C62257876. 10 Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrig- ant. Twin-width III: max independent set, min dominating set, and coloring.SIAM J. Comput., 53(5):1602–1640,

    work page doi:10.5070/c62257876

  6. [6]

    11 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant

    URL: https://doi.org/10.1137/21m142188x, doi: 10.1137/21M142188X. 11 Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant. Twin-width I: tractable FO model checking.J. ACM, 69(1):3:1–3:46, 2022.doi:10.1145/3486655. 12 Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks.Discret. Comput. G...

    work page doi:10.1137/21m142188x 2022

  7. [7]

    13 Marek Cygan, Fedor V

    URL:https://doi.org/ 10.1007/s00454-012-9417-5,doi:10.1007/S00454-012-9417-5. 13 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    work page doi:10.1007/s00454-012-9417-5

  8. [8]

    7 Andrea D’Ascenzo, Giuseppe F

    doi:10.1007/978-3-319-21275-3. 18 Independent Set Hardness in Graphs of Bounded Twin-Width and Merge-Width 14 Hugues Déprés.Twin-width: lower bounds and approximation algorithms. (Twin-width: bornes inférieures et algorithmes d’approximation). PhD thesis, École normale supérieure de Lyon, France,

    work page doi:10.1007/978-3-319-21275-3

  9. [9]

    15 Irit Dinur

    URL:https://tel.archives-ouvertes.fr/tel-04648829. 15 Irit Dinur. The PCP theorem by gap amplification.J. ACM, 54(3):12, 2007.doi:10.1145/ 1236457.1236459. 16 Jan Dreier, Nikolas Mählmann, and Sebastian Siebertz. The parameterized complexity of independent set and more when excluding a half-graph, co-matching, or matching.CoRR, abs/2602.07606,

    work page arXiv 2007

  10. [10]

    07606,doi:10.48550/ARXIV.2602.07606

    URL: https://doi.org/10.48550/arXiv.2602.07606, arXiv:2602. 07606,doi:10.48550/ARXIV.2602.07606. 17 Jan Dreier and Szymon Toruńczyk. Merge-width and first-order model checking. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1944–1955. ACM,

    work page doi:10.48550/arxiv.2602.07606 2025

  11. [11]

    18 Uriel Feige

    doi:10.1145/3717823.3718259. 18 Uriel Feige. Approximating maximum clique by removing subgraphs.SIAM J. Discret. Math., 18(2):219–225, 2004.doi:10.1137/S089548010240415X. 19 Jacob Fox and János Pach. Computing the independence number of intersection graphs. In Dana Randall, editor,Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algo...

    work page doi:10.1145/3717823.3718259 2004

  12. [12]

    22 Johan Håstad

    URL:https://doi.org/10.1007/s00493-003-0037-9, doi:10.1007/ S00493-003-0037-9. 22 Johan Håstad. Clique is hard to approximate withinn1−ϵ. In37th Annual Symposium on Foundations of Computer Science, FOCS ’96, Burlington, Vermont, USA, 14-16 October, 1996, pages 627–636, 1996.doi:10.1109/SFCS.1996.548522. 23 Pasin Manurangsi. Almost-polynomial ratio eth-har...

    work page doi:10.1007/s00493-003-0037-9 1996

  13. [13]

    Linear degree extractors and the inapproximability of max clique and chromatic number.Theory of Computing, 3(1):103–128, 2007

    26 David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number.Theory of Computing, 3(1):103–128, 2007

    2007