TY - JOUR

T1 - Framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

AU - de Berg, Mark

AU - Bodlaender, Hans L.

AU - Kisfaludi-Bak, Sándor

AU - Marx, Dániel

AU - Zanden, Tom C. van der

N1 - 37 pages, full version of STOC 2018 paper

PY - 2018/3/28

Y1 - 2018/3/28

N2 - 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 a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d \geq 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 work on the graph itself, i.e., do not require any geometric information. 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^{\Omega(n^{1-1/d})}$ lower bounds under the Exponential Time Hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.

AB - 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 a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time $2^{O(n^{1-1/d})}$ for any fixed dimension $d \geq 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 work on the graph itself, i.e., do not require any geometric information. 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^{\Omega(n^{1-1/d})}$ lower bounds under the Exponential Time Hypothesis even in the much more restricted class of $d$-dimensional induced grid graphs.

KW - cs.CG

KW - cs.DS

M3 - Article

SP - 1

EP - 38

JO - arXiv

JF - arXiv

M1 - 1803.10633v

ER -