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

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, Tom C. van der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)

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 a wide range of geometric intersection graphs (intersections of similarly sized fat objects), yielding algorithms with running time 2O(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 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Ω(n1−1/d) lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.

Original languageEnglish
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
PublisherAssociation for Computing Machinery, Inc
Pages574-586
Number of pages14
ISBN (Electronic)978-1-4503-5559-9
DOIs
Publication statusPublished - 20 Jun 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: 25 Jun 201829 Jun 2018

Conference

Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period25/06/1829/06/18

Keywords

  • Geometric intersection graphs
  • Geometric separator
  • Graph minors
  • Subexponential algorithms
  • Treewidth

Fingerprint Dive into the research topics of 'A framework for ETH-Tight algorithms and lower bounds in geometric intersection graphs'. Together they form a unique fingerprint.

Cite this