pith. sign in

arxiv: 2606.31369 · v1 · pith:IGNVCDSUnew · submitted 2026-06-30 · 💻 cs.DS · cs.DM

Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width

Ma\"el Dumas This is my paper

Pith reviewed 2026-07-01 03:02 UTC · model grok-4.3

classification 💻 cs.DS cs.DM
keywords distance-2 independent setmerge-widthapproximation algorithmslinear programmingdominating setgraph width parametersintegrality gap
0
0 comments X

The pith

Graphs of bounded radius-2 merge-width admit constant-factor LP-based approximations for maximum distance-2 independent set.

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

The paper shows that the natural linear programming relaxation for the maximum distance-2 independent set problem has bounded integrality gap on graphs whose radius-2 merge-width is bounded by any fixed constant. This yields a constant-factor approximation algorithm for the problem. The same LP approach gives a constant-factor approximation for the minimum dominating set problem. As a consequence, the ratio between the size of a minimum dominating set and a maximum distance-2 independent set remains bounded in this graph class. The bound on the ratio is tight because it can become arbitrarily large already when only radius-1 merge-width is bounded.

Core claim

In graphs of bounded radius-2 merge-width the linear-programming relaxation for maximum distance-2 independent set has integrality gap bounded by a constant depending only on the width parameter, which immediately supplies a constant-factor approximation algorithm; the identical argument works for minimum dominating set and therefore shows that the domination number and the distance-2 independence number differ by at most a constant factor.

What carries the argument

The linear-programming relaxation of the distance-2 independent set problem, whose integrality gap is controlled by the radius-2 merge-width of the input graph.

If this is right

  • There exists a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width.
  • The same constant-factor approximation holds for Min Dominating Set.
  • The ratio of the domination number to the distance-2 independence number is bounded by a constant in these graphs.
  • This bounded-ratio property fails already for graphs of bounded radius-1 merge-width.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The radius-2 merge-width parameter appears to be the precise threshold separating bounded and unbounded ratios for these two quantities.
  • Similar LP-based techniques might apply to other distance-constrained packing and covering problems once the appropriate width measure is identified.
  • Explicit constructions of graphs with small radius-2 merge-width but large integrality gap would help quantify the dependence on the width parameter.

Load-bearing premise

The integrality gap of the distance-2 independent set linear program is bounded by a function that depends only on the radius-2 merge-width of the graph.

What would settle it

A sequence of graphs with radius-2 merge-width at most k for fixed k, yet whose distance-2 independent set LP integrality gap tends to infinity.

read the original abstract

We give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA '12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-1 merge-width.

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 / 1 minor

Summary. The manuscript claims to give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-1 merge-width.

Significance. If the claims hold, the result is significant for parameterized approximation algorithms. It supplies LP-based constant-factor approximations for these two problems under a structural width parameter and establishes a bounded ratio between domination and distance-2 independence numbers (with the constant permitted to depend on the fixed merge-width bound k). The explicit contrast with the radius-1 case supplies a clean tightness statement.

minor comments (1)
  1. [Abstract] Abstract: a single sentence indicating the dependence of the approximation factor on the merge-width bound k would help the reader immediately understand the nature of the constant.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The report accurately captures our main contributions on the LP-based constant-factor approximations and the bounded ratio result (with the tightness contrast to radius-1 merge-width). No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents LP-based constant-factor approximation algorithms for Max Dist-2 Independent Set and Min Dominating Set on graphs of bounded radius-2 merge-width, along with a bounded ratio result. These are algorithmic constructions relying on structural parameterization, with no equations or reductions that equate outputs to inputs by definition or self-citation. External citations to Bonamy/Geniet and Chan et al. are load-bearing but independent. The central claims do not reduce to self-referential identities or fitted parameters renamed as predictions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes standard LP duality and integrality-gap arguments for set-cover-type problems together with the definition of radius-2 merge-width; no free parameters, invented entities, or ad-hoc axioms are visible.

axioms (2)
  • domain assumption Linear-programming relaxation of distance-2 independent set has integrality gap bounded by a function of radius-2 merge-width
    Central to the constant-factor claim; invoked implicitly by the statement that the LP yields a constant approximation.
  • domain assumption Standard properties of merge-width decompositions (radius-2 version) allow rounding or dual fitting
    Required for the LP-based algorithm to work; not proved in the abstract.

pith-pipeline@v0.9.1-grok · 5610 in / 1500 out tokens · 47316 ms · 2026-07-01T03:02:49.094232+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

22 extracted references · 19 canonical work pages · 1 internal anchor

  1. [1]

    Tight approximation bounds for dom- inating set on graphs of bounded arboricity

    Nikhil Bansal and Seeun William Umboh. “Tight approximation bounds for dom- inating set on graphs of bounded arboricity”. In:Information Processing Letters 122 (2017), pp. 21–24.doi: 10.1016/J.IPL.2017.01.011

    work page doi:10.1016/j.ipl.2017.01.011 2017

  2. [2]

    χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs

    Marthe Bonamy and Colin Geniet. χ-Boundedness and Neighbourhood Complexity of Bounded Merge-Width Graphs. 2025. arXiv:2504.08266

    work page arXiv 2025

  3. [3]

    On graph classes with constant domination-packing ratio

    Marthe Bonamy et al. “On graph classes with constant domination-packing ratio”. In: CoRR abs/2503.05562 (2025). arXiv:2503.05562

    work page arXiv 2025

  4. [4]

    Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring

    Édouard Bonnet et al. “Twin-Width III: Max Independent Set, Min Dominating Set, and Coloring”. In:SIAM Journal on Computing53.5 (2024), pp. 1602–1640. doi: 10.1137/21M142188X. 1This theorem states that graph classes of bounded merge-width are closed under first-order inter- pretation. The graph Gr can be interpreted fromG by a first-order formulaφ(u, v) t...

    work page doi:10.1137/21m142188x 2024

  5. [5]

    Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling

    Timothy M. Chan et al. “Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling”. In:23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 2012, pp. 1576–1585.doi: 10 . 1137 / 1 . 9781611973099.125

    2012

  6. [6]

    Analytical approach to parallel repetition

    Irit Dinur and David Steurer. “Analytical approach to parallel repetition”. In:46th Symposium on Theory of Computing, STOC. ACM, 2014, pp. 624–633.doi: 10. 1145/2591796.2591884

    work page arXiv 2014

  7. [7]

    Merge-width and First-Order Model Checking

    Jan Dreier and Szymon Toruńczyk. “Merge-Width and First-Order Model Check- ing”. In:57th Annual ACM Symposium on Theory of Computing (STOC). Full version available athttps://arxiv.org/abs/2502.18065. ACM, 2025, pp. 1944–

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  8. [8]

    doi: 10.1145/3717823.3718259

    work page doi:10.1145/3717823.3718259

  9. [9]

    Constant-factorapproximationofthedominationnumberinsparse graphs

    ZdenekDvorák.“Constant-factorapproximationofthedominationnumberinsparse graphs”. In:European Journal of Combinatorics 34.5 (2013), pp. 833–840.doi: 10.1016/J.EJC.2012.12.004

    work page doi:10.1016/j.ejc.2012.12.004 2013

  10. [10]

    Ondistancer-dominatingand2r-independentsetsinsparsegraphs

    ZdenekDvorák.“Ondistancer-dominatingand2r-independentsetsinsparsegraphs”. In: Journal of Graph Theory91.2 (2019), pp. 162–173.doi: 10.1002/JGT.22426

    work page doi:10.1002/jgt.22426 2019

  11. [11]

    Distance-d independent set problems for bipartite and chordal graphs

    Hiroshi Eto, Fengrui Guo and Eiji Miyano. “Distance-d independent set problems for bipartite and chordal graphs”. In:Journal of Combinatorial Optimization27.1 (2014), pp. 88–99.doi: 10.1007/S10878-012-9594-4

    work page doi:10.1007/s10878-012-9594-4 2014

  12. [12]

    Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

    Hiroshi Eto et al. “Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs”. In:IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences105-A.9 (2022), pp. 1211–

    2022

  13. [13]

    doi: 10.1587/TRANSFUN.2021DMP0017

    work page doi:10.1587/transfun.2021dmp0017

  14. [14]

    Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs

    Hiroshi Eto et al. “Approximation Algorithm for the Distance-3 Independent Set Problem on Cubic Graphs”. In:11th International Conference and Workshops on Algorithms and Computation, WALCOM. Vol. 10167. Lecture Notes in Computer Science. Springer, 2017, pp. 228–240.doi: 10.1007/978-3-319-53925-6\_18

    work page doi:10.1007/978-3-319-53925-6 2017

  15. [15]

    Approximation Algorithms for Combinatorial Problems

    David S. Johnson. “Approximation Algorithms for Combinatorial Problems”. In: Journal of Computer and System Sciences9.3 (1974), pp. 256–278.doi: 10.1016/ S0022-0000(74)80044-9

    1974

  16. [16]

    Scott Armstrong, ed.Expert Opinions in Forecasting: The Role of the Delphi Technique

    Richard M. Karp. “Reducibility Among Combinatorial Problems”. In:Proceedings of a symposium on the Complexity of Computer Computations. The IBM Research Symposia Series. Plenum Press, New York, 1972, pp. 85–103.doi: 10.1007/978- 1-4684-2001-2\_9

    work page doi:10.1007/978- 1972

  17. [17]

    New Lower Bounds for epsilon-Nets

    Andrey Kupavskii, Nabil H. Mustafa and János Pach. “New Lower Bounds for epsilon-Nets”.In:32nd International Symposium on Computational Geometry, SoCG. Vol. 51. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, 54:1– 54:16. doi: 10.4230/LIPICS.SOCG.2016.54. 10

    work page doi:10.4230/lipics.socg.2016.54 2016

  18. [18]

    Minimum Dominating Set Approxim- ation in Graphs of Bounded Arboricity

    Christoph Lenzen and Roger Wattenhofer. “Minimum Dominating Set Approxim- ation in Graphs of Bounded Arboricity”. In:24th International Symposium on Dis- tributed Computing, DISC.Vol.6343.LectureNotesinComputerScience.Springer, 2010, pp. 510–524.doi: 10.1007/978-3-642-15763-9\_48

    work page doi:10.1007/978-3-642-15763-9 2010

  19. [19]

    On the ratio of optimal integral and fractional covers

    László Lovász. “On the ratio of optimal integral and fractional covers”. In:Discrete Mathematics 13.4 (1975), pp. 383–390.doi: 10.1016/0012-365X(75)90058-8

    work page doi:10.1016/0012-365x(75)90058-8 1975

  20. [20]

    On the density of families of sets

    Norbert Sauer. “On the density of families of sets”. In:Journal of Combinatorial Theory, Series A13.1 (1972), pp. 145–147.doi: 10.1016/0097-3165(72)90019-2

    work page doi:10.1016/0097-3165(72)90019-2 1972

  21. [21]

    A combinatorial problem; stability and order for models and theories in infinitary languages

    Saharon Shelah. “A combinatorial problem; stability and order for models and theories in infinitary languages”. In:Pacific Journal of Mathematics41.1 (1972), pp. 247–261.doi: 10.2140/pjm.1972.41.247

    work page doi:10.2140/pjm.1972.41.247 1972

  22. [22]

    Flip-Width: Cops and Robber on Dense Graphs

    Szymon Toruńczyk. “Flip-Width: Cops and Robber on Dense Graphs”. In:64th Symposium on Foundations of Computer Science (FOCS). 2023, pp. 663–700.doi: 10.1109/FOCS57990.2023.00045. 11

    work page doi:10.1109/focs57990.2023.00045 2023