2018/03/28 by de Berg, Mark, Bodlaender, Hans L., Kisfaludi-Bak, Sándor +2
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1803.10633
We give an algorithmic and lower-bound framework that facilitates the construction of subexponential algorithms and matching conditional complexity bounds. It can be applied to intersection graphs of similarly-sized fat objects, yielding algorithms with running time 2^O(n1-1/d) for any fixed dimension d ≥ 2 for many well known graph problems, including Independent Set, r-Dominating Set for constant r, and Steiner Tree. For most problems, we get improved running times compared to prior work; in some cases, we give the first known subexponential algorithm in geometric intersection graphs. Additionally, most of the obtained algorithms are representation-agnostic, i.e., they work on the graph itself and do not require the geometric representation. Our algorithmic framework is based on a weighted separator theorem and various treewidth techniques. The lower bound framework is based on a constructive embedding of graphs into d-dimensional grids, and it allows us to derive matching 2^Ω(n1-1/d) lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.