{
  "annotation_id": "ce3c2817-2e1b-43d9-b451-f9cb13d41213",
  "date_created": "2026-02-17T05:53:16.199000Z",
  "date_modified": "2026-02-17T05:53:16.199000Z",
  "file_hash": "3d39d7659cc0b88d1118ac1406f993f56ecd5307c6ec4fa56aa077611c31379e",
  "private": false,
  "record": {
    "abstract": "Recently it was shown that many classic graph problems -- Independent Set, Dominating Set, Hamiltonian Cycle, and more -- can be solved in subexponential time on unit-ball graphs. More precisely, these problems can be solved in $2^{O(n^{1-1/d})}$ time on unit-ball graphs in $\\mathbb R^d$, which is tight under ETH. The result can be generalized to intersection graphs of similarly-sized fat objects. For Independent Set the same running time can be achieved for non-similarly-sized fat objects, and for the weighted version of the problem. We show that such generalizations most likely are not possible for Dominating Set: assuming ETH, we prove that - there is no algorithm with running time $2^{o(n)}$ for Dominating Set on (non-unit) ball graphs in $\\mathbb R^3$; - there is no algorithm with running time $2^{o(n)}$ for Weighted Dominating Set on unit-ball graphs in $\\mathbb R^3$; - there is no algorithm with running time $2^{o(n)}$ for Dominating Set, Connected Dominating Set, or Steiner Tree on intersections graphs of arbitrary convex (but non-constant-complexity) objects in the plane.",
    "arxiv_id": "2601.08425",
    "authors": [
      "Mark de Berg",
      "S\u00e1ndor Kisfaludi-Bak"
    ],
    "categories": [
      "cs.CG",
      "cs.DS"
    ],
    "doi": "10.1007/978-3-030-42071-0_5",
    "journal_ref": "In: Fomin, F.V., Kratsch, S., van Leeuwen, E.J. (eds) Treewidth, Kernels, and Algorithms (2020). Lecture Notes in Computer Science, vol 12160. Springer, Cham",
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "title": "Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs",
    "url": "https://arxiv.org/abs/2601.08425",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "dd594bf3-45ac-45cd-abda-5286a7edc99c",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}