A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

DOI10.1145/3188745.3188854zbMATH Open1427.68353DBLPconf/stoc/BergBKMZ18arXiv1803.10633OpenAlexW2964067126WikidataQ59567342 ScholiaQ59567342MaRDI QIDQ5230321

Author name not available (Why is that?)

Publication date: 22 August 2019

Published in: (Search for Journal in Brave)

Abstract: 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(n^{1-1/d})}$ for any fixed dimension $dgeq2$ 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^{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.

Full work available at URL: https://arxiv.org/abs/1803.10633

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230321)