research-article

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

Authors:

Hans L. Bodlaender,

Sándor Kisfaludi-Bak,

Tom C. van der ZandenAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 574 - 586

https://doi.org/10.1145/3188745.3188854

Published: 20 June 2018 Publication History

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 2^{O(n^1−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^{Ω(n^1−1/d)} lower bounds under the Exponential Time Hypothesis even in the much more restricted class of d-dimensional induced grid graphs.

Supplementary Material

MP4 File (4c-4.mp4)

Download
28.30 MB

References

[1]

Jochen Alber and Jirí Fiala. 2004. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. Journal of Algorithms 52, 2 (2004), 134–151.

Digital Library

[2]

Boris Aronov, Mark de Berg, Esther Ezra, and Micha Sharir. 2014. Improved Bounds for the Union of Locally Fat Objects in the Plane. SIAM J. Comput. 43, 2 (2014), 543–572.

[3]

Julien Baste and Dimitrios M. Thilikos. 2018. Contraction-Bidimensionality of Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 5:1–5:13.

[4]

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski. 2017. Fine-Grained Complexity of Coloring Unit Disks and Balls. In Proceedings of the 33rd International Symposium on Computational Geometry, SoCG 2017 (LIPCS), Vol. 77. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 18:1–18:16.

[5]

Hans L Bodlaender, Marek Cygan, Stefan Kratsch, and Jesper Nederlof. 2015. Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Information and Computation 243 (2015), 86–111.

Digital Library

[6]

Heinz Breu and David G. Kirkpatrick. 1998. Unit disk graph recognition is NPhard. Comput. Geom. 9, 1-2 (1998), 3–24. 00014-X

Digital Library

[7]

Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. 2000. Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width. Theory of Computing Systems 33, 2 (2000), 125–150.

[8]

Marek Cygan, Fedor V Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer.

[9]

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. 2018. Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs. CoRR abs/1803.10633 (2018). arXiv: 1803.10633 http://arxiv.org/abs/1803.10633

Digital Library

[10]

Mark de Berg, Sándor Kisfaludi-Bak, and Gerhard Woeginger. 2018. The Dominating Set Problem in Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017) (Leibniz International Proceedings in Informatics (LIPIcs)), Daniel Lokshtanov and Naomi Nishimura (Eds.), Vol. 89. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 14:1–14:12.

[11]

Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. 2017. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 (LIPICS), Vol. 80. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 65:1–65:15. LIPIcs.ICALP.2017.65

[12]

Fedor V. Fomin, Daniel Lokshtanov, and Saket Saurabh. 2012. Bidimensionality and geometric graphs. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. SIAM, 1563–1575. http://portal. acm.org/citation.cfm?id=2095240&CFID=63838676&CFTOKEN=79617016

Digital Library

[13]

Bin Fu. 2011. Theory and application of width bounded geometric separators. J. Comput. System Sci. 77, 2 (2011), 379 – 392. 003

Digital Library

[14]

Martin Charles Golumbic and Udi Rotics. 2000. On the Clique-Width of Some Perfect Graph Classes. International Journal of Foundations of Computer Science 11, 3 (2000), 423–443.

[15]

Sariel Har-Peled and Kent Quanrud. 2015. Approximation algorithms for polynomial-expansion and low-density graphs. In Proceedings of the 23rd Annual European Symposium on Algorithms, ESA 2015 (Lecture Notes in Computer Science), Vol. 9294. Springer, 717–728.

[16]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT. J. Comput. System Sci. 62, 2 (2001), 367–375.

Digital Library

[17]

Ross J. Kang and Tobias Müller. 2012. Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry 47, 3 (2012), 548–568.

[18]

Sándor Kisfaludi-Bak and Tom C van der Zanden. 2017. On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. In Proceedings 10th International Conference on Algorithms and Complexity, CIAC 2017 (Lecture Notes in Computer Science), Vol. 10236. Springer, 369–380.

[19]

Richard J. Lipton and Robert Endre Tarjan. 1979. A separator theorem for planar graphs. SIAM J. Appl. Math. 36, 2 (1979), 177–189.

Digital Library

[20]

Richard J. Lipton and Robert Endre Tarjan. 1980. Applications of a planar separator theorem. SIAM J. Comput. 9, 3 (1980), 615–627.

Digital Library

[21]

Dániel Marx. 2013. The Square Root Phenomenon in Planar Graphs. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part II. 28. 978-3-642-39212-2_4

Digital Library

[22]

Dániel Marx and Michal Pilipczuk. 2015. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In Proceedings of the 23rd Annual European Symposium on Algorithms, ESA 2015 (Lecture Notes in Computer Science), Vol. 9294. Springer, 865–877. 978-3-662-48350-3_72

[23]

Dániel Marx and Anastasios Sidiropoulos. 2014. The limited blessing of low dimensionality: when 1 − 1/d is the best possible exponent for d-dimensional geometric problems. In Proceedings of the 30th Annual Symposium on Computational Geometry, SOCG 2014. ACM, 67–76.

Digital Library

[24]

Sang-il Oum. 2017. Rank-width: Algorithmic and structural results. Discrete Applied Mathematics 231 (2017), 15–24.

[25]

Warren D. Smith and Nicholas C. Wormald. 1998. Geometric Separator Theorems & Applications. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS 1998. IEEE Computer Society, 232–243.

Digital Library

Cited By

Bandyapadhyay SLochet WLokshtanov DSaurabh SXue J(2024)True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk GraphsACM Transactions on Algorithms10.1145/365604220:3(1-26)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656042
Bandyapadhyay SFriggstad ZMousavi R(2024)Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and VariantsAlgorithmica10.1007/s00453-024-01236-186:8(2557-2574)Online publication date: 13-May-2024
https://doi.org/10.1007/s00453-024-01236-1
Gupta SSa'ar GZehavi M(2023)Grid recognition: Classical and parameterized computational perspectivesJournal of Computer and System Sciences10.1016/j.jcss.2023.02.008136(17-62)Online publication date: Sep-2023
https://doi.org/10.1016/j.jcss.2023.02.008
Show More Cited By

Index Terms

A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs
1. Theory of computation
  1. Design and analysis of algorithms
    1. Parameterized complexity and exact algorithms
  2. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Hitting minors on bounded treewidth graphs. III. Lower bounds
Abstract
For a finite fixed collection of graphs F, the F -M-Deletion problem consists in, given a graph G and an integer k, decide whether there exists S ⊆ V ( G ) with | S | ≤ k such that G ∖ S does not contain any of the graphs ...
Faster approximation schemes and parameterized algorithms on (odd-)H-minor-free graphs

We improve the running time of the general algorithmic technique known as Baker's approach (1994) [1] on H-minor-free graphs from O(n^f^(^|^H^|^)) to O(f(|H|)n^O^(^1^)). The numerous applications include, e.g. a 2-approximation for coloring and PTASes ...
Bidimensionality and geometric graphs
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Bidimensionality theory was introduced by Demaine et al. [JACM 2005] as a framework to obtain algorithmic results for hard problems on minor closed graph classes. The theory has been successfully applied to yield subex-ponential time parameterized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)1

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bandyapadhyay SLochet WLokshtanov DSaurabh SXue J(2024)True Contraction Decomposition and Almost ETH-Tight Bipartization for Unit-Disk GraphsACM Transactions on Algorithms10.1145/365604220:3(1-26)Online publication date: 8-Apr-2024
https://dl.acm.org/doi/10.1145/3656042
Bandyapadhyay SFriggstad ZMousavi R(2024)Parameterized Approximation Algorithms and Lower Bounds for k-Center Clustering and VariantsAlgorithmica10.1007/s00453-024-01236-186:8(2557-2574)Online publication date: 13-May-2024
https://doi.org/10.1007/s00453-024-01236-1
Gupta SSa'ar GZehavi M(2023)Grid recognition: Classical and parameterized computational perspectivesJournal of Computer and System Sciences10.1016/j.jcss.2023.02.008136(17-62)Online publication date: Sep-2023
https://doi.org/10.1016/j.jcss.2023.02.008
Bhore SCarmi PKolay SZehavi M(2022)Parameterized Study of Steiner Tree on Unit Disk GraphsAlgorithmica10.1007/s00453-022-01020-z85:1(133-152)Online publication date: 5-Aug-2022
https://doi.org/10.1007/s00453-022-01020-z
An HGurumukhani MImpagliazzo RJaber MKünnemann MParga Nina M(2022)The Fine-Grained Complexity of Multi-Dimensional Ordering PropertiesAlgorithmica10.1007/s00453-022-01014-x84:11(3156-3191)Online publication date: 22-Aug-2022
https://doi.org/10.1007/s00453-022-01014-x
Cohen-Addad Vde Verdière ÉMarx Dde Mesmay A(2021)Almost Tight Lower Bounds for Hard Cutting Problems in Embedded GraphsJournal of the ACM10.1145/345070468:4(1-26)Online publication date: 14-Jul-2021
https://dl.acm.org/doi/10.1145/3450704
Wang HZhao Y(2021)Reverse Shortest Path Problem for Unit-Disk GraphsAlgorithms and Data Structures10.1007/978-3-030-83508-8_47(655-668)Online publication date: 31-Jul-2021
https://doi.org/10.1007/978-3-030-83508-8_47
de Berg MBodlaender HKisfaludi-Bak SMarx Dvan der Zanden T(2020)A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection GraphsSIAM Journal on Computing10.1137/20M132087049:6(1291-1331)Online publication date: 15-Dec-2020
https://doi.org/10.1137/20M1320870
Wang HXue J(2020)Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk GraphsDiscrete & Computational Geometry10.1007/s00454-020-00219-7Online publication date: 24-Jun-2020
https://doi.org/10.1007/s00454-020-00219-7
de Berg MKisfaludi-Bak S(2020)Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball GraphsTreewidth, Kernels, and Algorithms10.1007/978-3-030-42071-0_5(31-48)Online publication date: 20-Apr-2020
https://doi.org/10.1007/978-3-030-42071-0_5
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents