pith. sign in

arxiv: 2606.04572 · v1 · pith:K5EQRBSNnew · submitted 2026-06-03 · 💻 cs.DS · cs.CC

Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances

Tim A. Hartmann , D\'aniel Marx This is my paper

Pith reviewed 2026-06-28 04:18 UTC · model grok-4.3

classification 💻 cs.DS cs.CC
keywords bounded treewidthdispersioncoveringcontinuous distancesindependent setdominating setdynamic programmingSETH lower bounds
0
0 comments X

The pith

The continuous δ-Dispersion and δ-Covering problems admit algorithms on bounded-treewidth graphs whose running times depend on δ in the same way as the discrete versions.

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

The paper examines the continuous analogs of distance-d independent set and dominating set, where selected points may lie anywhere on the edges rather than only at vertices. Edges are treated as continuous unit-length intervals, allowing placements at arbitrary real positions. It establishes that these problems remain solvable in single-exponential time in the treewidth t, with the exponential base depending on δ, and that the bases cannot be improved under the Strong Exponential-Time Hypothesis. A reader cares because the continuous model captures geometric placements more accurately while preserving tractability on tree-like graphs.

Core claim

Given a tree decomposition of width t, the continuous δ-Dispersion problem can be solved in time d^t · n^O(1) and the continuous δ-Covering problem in time (2d + 1)^t · n^O(1); these bases are optimal under SETH, and the results hold uniformly for integer, rational, and irrational values of δ.

What carries the argument

Dynamic programming on a tree decomposition that accounts for all possible real positions of points along the unit-length edges, with states depending on the distance parameter δ.

If this is right

  • The problems remain fixed-parameter tractable when parameterized by treewidth for any fixed δ.
  • The same SETH-based lower bounds on the exponential bases carry over from the discrete setting to the continuous one.
  • The distinction between integer, rational, and irrational δ does not change the asymptotic running-time form on bounded-treewidth graphs.

Where Pith is reading between the lines

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

  • The continuous model may extend tractability results to other distance-based covering or packing problems on the same graph classes without increasing the dependence on treewidth.
  • Practical implementations could discretize the edge positions at a fine enough grid without losing the FPT guarantee when treewidth is small.
  • The results suggest that many real-world network problems with continuous distances remain tractable precisely when the underlying graph is tree-like.

Load-bearing premise

Modeling every edge as a continuous unit-length interval of points allows placements at any real coordinate along the edge.

What would settle it

An algorithm running in time (2d + 1 - ε)^t · n^O(1) for some ε > 0 on a family of bounded-treewidth graphs with fixed δ would contradict the SETH lower bound.

read the original abstract

The distance-d variants of Independent Set and Dominating Set problems have been extensively studied from different algorithmic viewpoints. In particular, the complexity of these problems are well understood on bounded-treewidth graphs [Katsikarelis, Lampis, and Paschos, Discret. Appl. Math 2022][Borradaile and Le, IPEC 2016]: given a tree decomposition of width t, the two problems can be solved in time $d^t \cdot n^{O(1)}$ and $(2d + 1)t \cdot n^{O(1)}$, respectively. Furthermore, assuming the Strong Exponential-Time Hypothesis (SETH), the base constants are best possible in these running times: they cannot be improved to $d-{\epsilon}$ and $2d+1-{\epsilon}$, respectively, for any ${\epsilon} > 0$. We investigate continuous versions of these problems in a setting introduced by Megiddo and Tamir [SICOMP 1983], where every edge is modeled by a unit-length interval of points. In the {\delta}-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least {\delta} from each other. Similarly, in the {\delta}-Covering problem, the task is to find a minimum number of points (possibly inside edges) such that every point of the graph (including those inside edges) is at distance at most {\delta} from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs.

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

2 major / 1 minor

Summary. The paper studies the continuous δ-Dispersion (maximum points with pairwise distance ≥δ) and δ-Covering (minimum points covering the graph within distance δ) problems on bounded-treewidth graphs, where edges are unit-length intervals allowing points to be placed continuously (following Megiddo-Tamir). It builds on known discrete distance-d Independent Set and Dominating Set results with d^t n^{O(1)} and (2d+1)^t n^{O(1)} FPT algorithms (SETH-tight) and claims a comprehensive understanding for the continuous variants across integer, rational, and irrational distances.

Significance. If the algorithmic results and hardness claims for the continuous cases hold, the work would meaningfully extend FPT techniques to geometric continuous settings on treewidth-bounded graphs, addressing potential breakdowns in standard DP due to irrational distances as signaled by the title. This could impact approximation and exact algorithms for dispersion and covering problems in networks.

major comments (2)
  1. [Abstract] Abstract and introduction: the central claim of 'comprehensive understanding' for the continuous Megiddo-Tamir variants is stated without any mention of specific running times, DP states, or hardness results for δ-Dispersion and δ-Covering (unlike the explicit discrete bounds given); this makes it impossible to assess whether the continuous cases receive algorithms of comparable form or require new techniques for rational/irrational δ.
  2. No section or theorem is referenced in the provided material that establishes FPT membership or SETH-tightness for the continuous problems; if such results exist later in the manuscript they must be explicitly contrasted with the discrete d^t and (2d+1)^t bases to support the 'comprehensive' claim.
minor comments (1)
  1. [Abstract] The abstract cites Katsikarelis et al. and Borradaile-Le but does not clarify whether the continuous results reuse the same tree-decomposition DP framework or require modifications for point placement on edges.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for highlighting issues with the abstract and introduction. We agree the presentation of continuous results needs improvement and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract and introduction: the central claim of 'comprehensive understanding' for the continuous Megiddo-Tamir variants is stated without any mention of specific running times, DP states, or hardness results for δ-Dispersion and δ-Covering (unlike the explicit discrete bounds given); this makes it impossible to assess whether the continuous cases receive algorithms of comparable form or require new techniques for rational/irrational δ.

    Authors: We agree the abstract should briefly indicate the form of results for the continuous cases (including distinctions by distance type) to allow assessment of the claim. The full manuscript contains the specific algorithms and hardness results for integer, rational, and irrational δ; we will revise the abstract and introduction to include high-level statements of these. revision: yes

  2. Referee: [—] No section or theorem is referenced in the provided material that establishes FPT membership or SETH-tightness for the continuous problems; if such results exist later in the manuscript they must be explicitly contrasted with the discrete d^t and (2d+1)^t bases to support the 'comprehensive' claim.

    Authors: The FPT algorithms and hardness results for the continuous problems (with explicit bases depending on whether δ is integer, rational, or irrational) appear in later sections. We will add forward references in the introduction, along with direct comparisons to the discrete running times, to support the claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper cites independent prior work (Katsikarelis et al. 2022 and Borradaile & Le 2016) for the discrete-case running times and SETH lower bounds, then states that it investigates the continuous Megiddo-Tamir variants and provides a comprehensive understanding on bounded-treewidth graphs. No self-definitional equations, no parameters fitted to a subset and then relabeled as predictions, and no load-bearing self-citations appear in the abstract or title. The claimed algorithms for integer, rational, and irrational distances are presented as new results rather than reductions to the paper's own inputs, rendering the derivation chain self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no information on free parameters, axioms, or invented entities.

pith-pipeline@v0.9.1-grok · 5830 in / 1009 out tokens · 57450 ms · 2026-06-28T04:18:29.537973+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

26 extracted references · 24 canonical work pages

  1. [1]

    2 Yousef Alavi, Jiuqiang Liu, Jianfang Wang, and Zhongfu Zhang

    URL: http: //dx.doi.org/10.1002/jgt.3190010209,doi:10.1002/jgt.3190010209. 2 Yousef Alavi, Jiuqiang Liu, Jianfang Wang, and Zhongfu Zhang. On total covers of graphs. Discret. Math., 100(1-3):229–233, 1992.doi:10.1016/0012-365X(92)90643-T. 3 José D. Alvarado, Simone Dantas, and Dieter Rautenbach. Distance k-domination, distance k-guarding, and distance k-v...

    work page doi:10.1002/jgt.3190010209 1992

  2. [2]

    DAM.2015.05.010

    URL:https://doi.org/10.1016/j.dam.2015.05.010, doi:10.1016/J. DAM.2015.05.010. 4 Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, and Erik Jan Van Leeuwen. Subexponential-time algorithms for maximum independent set inPt-free and broom-free graphs.Algorithmica, 81:421–438,

    work page doi:10.1016/j.dam.2015.05.010 2015

  3. [3]

    6 Glencora Borradaile and Hung Le

    URL:https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3417. 6 Glencora Borradaile and Hung Le. Optimal dynamic program for r-domination problems over tree decompositions. In Jiong Guo and Danny Hermelin, editors,11th International Symposium on Parameterized and Exact Computation, IPEC 2016, August 24-26, 2016, Aarhus, Denmark, volume 63 ofLI...

    2016

  4. [4]

    7 Marek Cygan, Fedor V

    doi:10.4230/LIPIcs.IPEC.2016.8. 7 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.4230/lipics.ipec.2016.8 2016

  5. [5]

    9 Rod G Downey and Michael R Fellows

    doi:10.1007/978-3-319-21275-3. 8 Clément Dallard, Mirza Krbezlija, and Martin Milanic. Vertex cover at distance on H-free graphs. In Paola Flocchini and Lucia Moura, editors,Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 ofLecture Notes in Computer Science, pages 237–251. Springer,

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

  6. [6]

    9 Perino M

    doi: 10.1007/978-3-030-79987-8\_17. 9 Perino M. Dearing and Richard L. Francis. A minimax location problem on a network. Transportation Science, 8(4):333–343,

    work page doi:10.1007/978-3-030-79987-8

  7. [7]

    Downey and Michael R

    10 Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness I: basic results.SIAM J. Comput., 24(4):873–921, 1995.doi:10.1137/S0097539792228228. 11 Rodney G. Downey and Michael R. Fellows. Fixed-parameter tractability and completeness II: on completeness for W[1].Theor. Comput. Sci., 141(1&2):109–131, 1995.doi:10.1016/ 0304-3...

    work page doi:10.1137/s0097539792228228 1995

  8. [8]

    13 Paul Erdős and Amram Meir

    URL: https://doi.org/10.46298/ dmtcs.6824,doi:10.46298/DMTCS.6824. 13 Paul Erdős and Amram Meir. On total matching numbers and total covering numbers of complementary graphs.Discret. Math., 19(3):229–233,

    work page doi:10.46298/dmtcs.6824

  9. [9]

    14 Hiroshi Eto, Fengrui Guo, and Eiji Miyano

    doi:10.1016/0012-365X(77) 90102-9. 14 Hiroshi Eto, Fengrui Guo, and Eiji Miyano. Distance-d independent set problems for bipartite and chordal graphs.J. Comb. Optim., 27(1):88–99, 2014.doi:10.1007/s10878-012-9594-4. 15 Hiroshi Eto, Takehiro Ito, Zhilong Liu, and Eiji Miyano. Approximation algorithm for the distance-3 independent set problem on cubic graph...

    work page doi:10.1016/0012-365x(77 2014

  10. [10]

    1007/s00453-020-00683-w,doi:10.1007/S00453-020-00683-W

    URL:https://doi.org/10. 1007/s00453-020-00683-w,doi:10.1007/S00453-020-00683-W. 56 Independence and Domination on Bounded-Treewidth Graphs 17 Fabian Frei, Ahmed Ghazy, Tim A. Hartmann, Florian Hörsch, and Dániel Marx. From chinese postman to salesman and beyond: Shortest tourδ-covering all points on all edges. In Julián Mestre and Anthony Wirth, editors,3...

    work page doi:10.1007/s00453-020-00683-w 2024

  11. [11]

    18 Michael R

    URL:https://doi.org/10.4230/ LIPIcs.ISAAC.2024.31,doi:10.4230/LIPICS.ISAAC.2024.31. 18 Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman,

    work page doi:10.4230/lipics.isaac.2024.31 2024

  12. [12]

    Hartmann, Stefan Lendl, and Gerhard J

    19 Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Dis- persing obnoxious facilities on a graph.Algorithmica, 83(6):1734–1749, 2021.doi:10.1007/ s00453-021-00800-3. 20 Tim A. Hartmann.Facility location on graphs. Dissertation, RWTH Aachen Univer- sity, Aachen,

    2021

  13. [13]

    21 Tim A

    URL: https://publications.rwth-aachen.de/record/951030, doi: 10.18154/RWTH-2023-01837. 21 Tim A. Hartmann and Tom Janßen. Approximatingδ-covering. In Marcin Bienkowski and Matthias Englert, editors,Approximation and Online Algorithms - 22nd International Workshop, W AOA 2024, Egham, UK, September 5-6, 2024, Proceedings, Lecture Notes in Computer Science, ...

    work page doi:10.18154/rwth-2023-01837 2023

  14. [14]

    23 Tim A

    URL:https://doi.org/10.4230/LIPIcs.MFCS.2022.55, doi: 10.4230/LIPICS.MFCS.2022.55. 23 Tim A. Hartmann, Stefan Lendl, and Gerhard J. Woeginger. Continuous facility location on graphs.Math. Program., 192(1):207–227, 2022.doi:10.1007/s10107-021-01646-x. 24 Pallavi Jain, Jayakrishnan Madathil, Fahad Panolan, and Abhishek Sahu. Mixed domi- nating set: A parame...

    work page doi:10.4230/lipics.mfcs.2022.55 2022

  15. [15]

    25 Ioannis Katsikarelis, Michael Lampis, and Vangelis T

    doi:10.1007/978-3-319-68705-6\_25. 25 Ioannis Katsikarelis, Michael Lampis, and Vangelis T. Paschos. Improved (in-)approximability bounds for d-scattered set.J. Graph Algorithms Appl., 27(3):219–238,

    work page doi:10.1007/978-3-319-68705-6

  16. [16]

    26Ioannis Katsikarelis, Michael Lampis, and Vangelis Th

    URL: https: //doi.org/10.7155/jgaa.00621,doi:10.7155/JGAA.00621. 26Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set.Discret. Appl. Math., 308:168–186, 2022.doi:10.1016/j.dam.2020.03.052. 27 Tuukka Korhonen and Daniel Lokshtanov. An improved parameterized algorithm for treewidth. In Barna Saha and R...

    work page doi:10.7155/jgaa.00621 2022

  17. [17]

    29 Jason Lewis, Stephen T

    doi:10.1137/1.9781611978322.47. 29 Jason Lewis, Stephen T. Hedetniemi, Teresa W. Haynes, and Gerd H. Fricke. Vertex-edge domination.Utilitas mathematica, 81:193–213,

    work page doi:10.1137/1.9781611978322.47

  18. [18]

    31 Jayakrishnan Madathil, Fahad Panolan, Abhishek Sahu, and Saket Saurabh

    doi:10.1145/3170442. 31 Jayakrishnan Madathil, Fahad Panolan, Abhishek Sahu, and Saket Saurabh. On the complexity of mixed dominating set. In René van Bevern and Gregory Kucherov, editors,Computer Tim A. Hartmann and Dániel Marx 57 Science - Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, J...

    work page doi:10.1145/3170442 2019

  19. [19]

    New results on the complexity ofp-center problems.SIAM J

    33 Nimrod Megiddo and Arie Tamir. New results on the complexity ofp-center problems.SIAM J. Comput., 12(4):751–758, 1983.doi:10.1137/0212051. 34 Amram Meir. On total covering and matching of graphs.J. Comb. Theory B, 24(2):164–168, 1978.doi:10.1016/0095-8956(78)90017-5. 35 Pedro Montealegre and Ioan Todinca. On distance-d independent set and other problem...

    work page doi:10.1137/0212051 1983

  20. [20]

    Representation in

    doi:10.1093/ACPROF:OSO/9780198566076.001.0001. 37 Uri N. Peled and Feng Sun. Total matchings and total coverings of threshold graphs.Discret. Appl. Math., 49(1-3):325–330, 1994.doi:10.1016/0166-218X(94)90216-X. 38 Michal Pilipczuk and Sebastian Siebertz. Kernelization and approximation of distance-r independent sets on nowhere dense graphs.Eur. J. Comb., ...

    work page doi:10.1093/acprof:oso/9780198566076.001.0001 1994

  21. [21]

    39 Douglas R

    URL: https: //doi.org/10.1016/j.ejc.2021.103309,doi:10.1016/J.EJC.2021.103309. 39 Douglas R. Shier. A min-max theorem forp-center problems on a tree.Transportation Science, 11(3):243–252,

    work page doi:10.1016/j.ejc.2021.103309 2021

  22. [22]

    40 Arie Tamir

    URL:http://www.jstor.org/stable/25767877. 40 Arie Tamir. On the solution value of the continuousp-center location problem on a graph. Math. Oper. Res., 12(2):340–349, 1987.doi:10.1287/moor.12.2.340. 41 Arie Tamir. Obnoxious facility location on graphs.SIAM J. Discret. Math., 4(4):550–567, 1991.doi:10.1137/0404048. 42 Johan M. M. van Rooij, Hans L. Bodlaen...

    work page doi:10.1287/moor.12.2.340 1987

  23. [23]

    Springer, 2009.doi:10.1007/978-3-642-04128-0\_51

    Proceedings, volume 5757 ofLecture Notes in Computer Science, pages 566–577. Springer, 2009.doi:10.1007/978-3-642-04128-0\_51. 43 Mingyu Xiao and Zimo Sheng. Improved parameterized algorithms and kernels for mixed domination.Theor. Comput. Sci., 815:109–120,

    work page doi:10.1007/978-3-642-04128-0 2009

  24. [24]

    Hedging strategies in academic discourse: A compara- tive analysis of turkish writers and native writers of english.Procedia - Social and Be- havioral Sciences, 158:260–268, 2014

    URL: https://doi.org/10.1016/j. tcs.2020.02.014,doi:10.1016/J.TCS.2020.02.014. 44 Yancai Zhao, Liying Kang, and Moo Young Sohn. The algorithmic complexity of mixed domination in graphs.Theor. Comput. Sci., 412(22):2387–2392,

    work page doi:10.1016/j 2020

  25. [25]

    org/10.1016/j.tcs.2011.01.029,doi:10.1016/J.TCS.2011.01.029

    URL:https://doi. org/10.1016/j.tcs.2011.01.029,doi:10.1016/J.TCS.2011.01.029. 45 Radosław Ziemann and Paweł Żyliński. Vertex-edge domination in cubic graphs.Discret. Math., 343(11):112075,

    work page doi:10.1016/j.tcs.2011.01.029 2011

  26. [26]

    46 Paweł Żyliński

    URL: https://doi.org/10.1016/j.disc.2020.112075, doi: 10.1016/J.DISC.2020.112075. 46 Paweł Żyliński. Vertex-edge domination in graphs.Aequationes mathematicae, 93(4):735–742, 2019

    work page doi:10.1016/j.disc.2020.112075 2020