{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiclgm2nnkfozlsck6hsps2k5qaan4zwgcnl42fpfohrz5iea2csya",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mnjnnjkbqu22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.04572v1",
  "publishedAt": "2026-06-04T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Tim A. Hartmann",
    "Dániel Marx"
  ],
  "textContent": "**Authors:** Tim A. Hartmann, Dániel Marx\n\nThe 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 $ε > 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.",
  "title": "Independence and Domination on Bounded-Treewidth Graphs: Integer, Rational, and Irrational Distances"
}