Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
By: Mark de Berg, Sándor Kisfaludi-Bak
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.
Similar Papers
Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
Data Structures and Algorithms
Finds hidden paths in geometric shapes quickly.
Weighted $k$-Path and Other Problems in Almost $O^*(2^k)$ Deterministic Time via Dynamic Representative Sets
Data Structures and Algorithms
Finds shortest paths with many stops faster.
On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
Computational Geometry
Finds shortest paths connecting shapes faster.