{"ID":3050186,"CreatedAt":"2026-06-04T02:13:16.786527022Z","UpdatedAt":"2026-06-06T07:53:07.675991959Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.04572","arxiv_id":"2606.04572","title":"Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances","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-ε$ and $2d+1-ε$, respectively, for any $ε \u003e 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 δ-Dispersion problem, the task is to find a maximum number of points (possibly inside edges) that are pairwise at distance at least δ from each other. Similarly, in the δ-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 δ from the selected point set. We provide a comprehensive understanding of these two problems on bounded-treewidth graphs.","short_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, IPE...","url_abs":"https://arxiv.org/abs/2606.04572","url_pdf":"https://arxiv.org/pdf/2606.04572v1","authors":"[\"Tim A. Hartmann\",\"Dániel Marx\"]","published":"2026-06-03T08:04:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}