research-article

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs

Authors:

Édouard Bonnet,

Nicolas Bousquet,

Pierre Charbit,

Panos Giannopoulos,

Paweł Rzążewski,

Florian Sikora,

Stéphan ThomasséAuthors Info & Claims

Journal of the ACM (JACM), Volume 68, Issue 2

Article No.: 9, Pages 1 - 38

https://doi.org/10.1145/3433160

Published: 06 January 2021 Publication History

Abstract

A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time algorithm was found for MAXIMUM CLIQUE on unit disk graphs [Clark, Colbourn, Johnson; Discrete Mathematics ’90]. Since then, it has been an intriguing open question whether or not tractability can be extended to general disk graphs. We show that the disjoint union of two odd cycles is never the complement of a disk graph nor of a unit (3-dimensional) ball graph. From that fact and existing results, we derive a simple QPTAS and a subexponential algorithm running in time 2^{Õ(n^2/3)} for MAXIMUM CLIQUE on disk and unit ball graphs. We then obtain a randomized EPTAS for computing the independence number on graphs having no disjoint union of two odd cycles as an induced subgraph, bounded VC-dimension, and linear independence number. This, in combination with our structural results, yields a randomized EPTAS for MAX CLIQUE on disk and unit ball graphs. MAX CLIQUE on unit ball graphs is equivalent to finding, given a collection of points in R³, a maximum subset of points with diameter at most some fixed value.

In stark contrast, MAXIMUM CLIQUE on ball graphs and unit 4-dimensional ball graphs, as well as intersection graphs of filled ellipses (even close to unit disks) or filled triangles is unlikely to have such algorithms. Indeed, we show that, for all those problems, there is a constant ratio of approximation that cannot be attained even in time 2ⁿ^1−ɛ, unless the Exponential Time Hypothesis fails.

References

[1]

Peyman Afshani and Timothy M. Chan. 2005. Approximation algorithms for maximum cliques in 3D unit-disk graphs. In Proceedings of the 17th Canadian Conference on Computational Geometry (CCCG’05). 19--22. Retrieved from http://www.cccg.ca/proceedings/2005/69.pdf.

[2]

Peyman Afshani and Hamed Hatami. 2008. Approximation and inapproximability results for maximum clique of disc graphs in high dimensions. Inf. Proc. Lett. 105, 3 (2008), 83--87.

Digital Library

[3]

Pankaj K. Agarwal and Nabil H. Mustafa. 2006. Independent set of intersection graphs of convex objects in 2D. Comput. Geom. 34, 2 (2006), 83--95.

Digital Library

[4]

Pankaj K. Agarwal, János Pach, and Micha Sharir. 2008. State of the union (of geometric objects). In Surveys in Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics, Vol. 453. American Mathematical Society, 9--48.

[5]

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

Digital Library

[6]

Noga Alon, Raphael Yuster, and Uri Zwick. 1997. Finding and counting given length cycles. Algorithmica 17, 3 (1997), 209--223.

[7]

Christoph Ambühl and Uli Wagner. 2005. The clique problem in intersection graphs of ellipses and triangles. Theor. Comput. Syst. 38, 3 (2005), 279--292.

Digital Library

[8]

Boris Aronov, Anirudh Donakonda, Esther Ezra, and Rom Pinchasi. 2018. On pseudo-disk hypergraphs. CoRR abs/1802.08799 (2018).

[9]

Stephan Artmann, Robert Weismantel, and Rico Zenklusen. 2017. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th ACM SIGACT Symposium on Theory of Computing (STOC’17). 1206--1219.

Digital Library

[10]

Aistis Atminas and Viktor Zamaraev. 2018. On forbidden induced subgraphs for unit disk graphs. Disc. Comput. Geom. 60, 1 (2018), 57--97.

Digital Library

[11]

Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, and Uli Wagner. 2006. On six problems posed by Jarik Nešetřil. Top. Disc. Math. 26 (2006), 613--627.

[12]

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Paweł Rzążewski. 2018. Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. 9, 2 (2018), 47--80. Retrieved from http://jocg.org/index.php/jocg/article/view/414.

[13]

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. 1989. Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36, 4 (1989), 929--965.

Digital Library

[14]

Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres J. Ruiz-Vargas. 2014. Solving the stable set problem in terms of the odd cycle packing number. In Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS’14). 187--198.

[15]

Marthe Bonamy, Edouard Bonnet, Nicolas Bousquet, Pierre Charbit, and Stéphan Thomassé. 2018. EPTAS for max clique on disks and unit balls. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science (FOCS’18). 568--579.

[16]

Édouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. 2015. On subexponential and FPT-time inapproximability. Algorithmica 71, 3 (2015), 541--565.

Digital Library

[17]

Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, and Florian Sikora. 2018. QPTAS and subexponential algorithm for maximum clique on disk graphs. In Proceedings of the 34th International Symposium on Computational Geometry (SoCG’18). 12:1--12:15.

[18]

Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes: A Survey. SIAM.

[19]

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

[20]

Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochvíl, Martin Pergel, Paweł Rzążewski, Matthew Szczepankiewicz, and Joshua Terhaar. 2018. Homothetic polygons and beyond: Maximal cliques in intersection graphs. Disc. Appl. Math. 247 (2018), 263--277.

[21]

Sergio Cabello. 2015. Maximum clique for disks of two sizes. Open problems fromGeometric Intersection Graphs: Problems and Directions CG Week Workshop. Retrieved from http://cgweek15.tcs.uj.edu.pl/problems.pdf.

[22]

Sergio Cabello. 2015. Open problems presented at theAlgorithmic Graph Theory on the Adriatic Coast Workshop. Retrieved from https://conferences.matheo.si/event/6/picture/35.pdf.

[23]

Sergio Cabello, Jean Cardinal, and Stefan Langerman. 2013. The clique problem in ray intersection graphs. Disc. Comput. Geom. 50, 3 (2013), 771--783.

Digital Library

[24]

Paz Carmi, Matthew J. Katz, and Pat Morin. 2018. Stabbing pairwise intersecting disks by four points. CoRR abs/1812.06907 (2018).

[25]

Stephan Ceroi. 2002. The Clique Number of Unit Quasi-disk Graphs. Technical Report RR-4419. INRIA. Retrieved from https://hal.inria.fr/inria-00072169.

[26]

Timothy M. Chan. 2003. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algor. 46, 2 (2003), 178--189.

Digital Library

[27]

Timothy M. Chan and Sariel Har-Peled. 2012. Approximation algorithms for maximum independent set of pseudo-disks. Disc. Comput. Geom. 48, 2 (2012), 373--392.

Digital Library

[28]

Miroslav Chlebík and Janka Chlebíková. 2006. Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354, 3 (2006), 320--338.

Digital Library

[29]

Brent N. Clark, Charles J. Colbourn, and David S. Johnson. 1990. Unit disk graphs. Disc. Math. 86, 1–3 (1990), 165--177.

Digital Library

[30]

L. Danzer. 1986. Zur lösung des Gallaischen problems über Kreisscheiben in der Euklidischen Ebene. Studia Sci. Math. Hungar 21, 1–2 (1986), 111--134.

[31]

Ran Duan and Seth Pettie. 2014. Linear-time approximation for maximum weight matching. J. ACM 61, 1 (2014), 1:1--1:23.

Digital Library

[32]

Zdenek Dvořák and Jakub Pekárek. 2020. Induced odd cycle packing number, independent sets, and chromatic number. CoRR abs/2001.02411 (2020).

[33]

Thomas Erlebach, Klaus Jansen, and Eike Seidel. 2005. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 6 (2005), 1302--1323.

Digital Library

[34]

Aleksei V. Fishkin. 2003. Disk graphs: A short survey. In Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16--18, 2003, Revised Papers (Lecture Notes in Computer Science), Klaus Jansen and Roberto Solis-Oba (Eds.), Vol. 2909. Springer, 260--264.

[35]

Zoltán Füredi. 1987. The number of maximal independent sets in connected graphs. J. Graph Theor. 11, 4 (1987), 463--470.

[36]

Matt Gibson and Imran A. Pirwani. 2010. Algorithms for dominating set in disk graphs: Breaking the log n barrier—(Extended abstract). In Proceedings of the 18th European Symposium on Algorithms (ESA’10). 243--254.

[37]

Ervin Györi, Alexandr V. Kostochka, and Tomasz Łuczak. 1997. Graphs without short odd cycles are nearly bipartite. Disc. Math. 163, 1 (1997), 279--284.

Digital Library

[38]

Sariel Har-Peled, Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir, and Max Willert. 2018. Stabbing pairwise intersecting disks by five points. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC’18). 50:1--50:12.

[39]

D. Haussler and E. Welzl. 1987. Epsilon-nets and simplex range queries. Disc. Comput. Geom. 2 (1987), 127--151.

Digital Library

[40]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 4 (Dec. 2001), 512--530.

Digital Library

[41]

Ross J. Kang and Tobias Müller. 2012. Sphere and dot product representations of graphs. Disc. Comput. Geom. 47, 3 (2012), 548--568.

Digital Library

[42]

Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. Odd cycle packing. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). 695--704.

[43]

Chaya Keller, Shakhar Smorodinsky, and Gábor Tardos. 2017. On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 2254--2263.

[44]

Paul Koebe. 1936. Kontaktprobleme der konformen Abbildung. Berichte über die Verhandlungen der Sächsischen Akademie der Wissenschaften zu Leipzig, Mathematisch-Physikalische Klasse 88 (1936), 141--164.

[45]

Jan Kratochvil. 1993. Precoloring extension with fixed color bound. Acta Math. Univ. Comen 62 (1993), 139--153.

[46]

Jan Kratochvíl. 1996. Intersection graphs of noncrossing arc-connected sets in the plane. In Proceedings of the Symposium on Graph Drawing (GD’96). 257--270.

[47]

Jan Kratochvíl and Jiří Matoušek. 1994. Intersection graphs of segments. J. Comb. Theor., Ser. B 62, 2 (1994), 289--315.

Digital Library

[48]

Ewa Malesinska, Steffen Piskorz, and Gerhard Weißenfels. 1998. On the chromatic number of disk graphs. Networks 32, 1 (1998), 13--22.

[49]

Dániel Marx and Michal Pilipczuk. 2015. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In Proceedings of the 23rd European Symposium on Algorithms (ESA’15). 865--877.

[50]

Terry A. McKee and Fred R. McMorris. 1999. Topics in Intersection Graph Theory. SIAM.

[51]

Matthias Middendorf and Frank Pfeiffer. 1992. The max clique problem in classes of string-graphs. Disc. Math. 108, 1–3 (1992), 365--372.

Digital Library

[52]

Dana Moshkovitz and Ran Raz. 2010. Two-query PCP with subconstant error. J. ACM 57, 5 (2010), 29:1--29:29.

Digital Library

[53]

Tim Nieberg and Johann Hurink. 2005. A PTAS for the minimum dominating set problem in unit disk graphs. In Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA’15). 296--306.

[54]

Tim Nieberg, Johann Hurink, and Walter Kern. 2004. A robust PTAS for maximum weight independent sets in unit disk graphs. In Proceedings of the 30th International Workshop on Graph-theoretic Concepts in Computer Science (WG’04). 214--221.

Digital Library

[55]

Vijay Raghavan and Jeremy P. Spinrad. 2003. Robust algorithms for restricted domains. J. Algor. 48, 1 (2003), 160--172.

Digital Library

[56]

Warren D. Smith and Nicholas C. Wormald. 1998. Geometric separator theorems 8 applications. In Proceedings of the 39th Symposium on Foundations of Computer Science (FOCS’98). 232--243.

[57]

Lajos Stachó. 1981. A solution of Gallai’s problem on pinning down circles. Mat. Lapok 32, 1–3 (1981), 19--47.

[58]

Peter Guthrie Tait. 1877. Some elementary properties of closed plane curves. Mess. Math., New Series 69 (1877), 270--272.

[59]

Erik Jan van Leeuwen. 2006. Better approximation schemes for disk graphs. In Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT’06). 316--327.

Digital Library

[60]

Erik Jan van Leeuwen. 2009. Optimization and Approximation on Systems of Geometric Objects. Ph.D. Dissertation. Utrecht University.

[61]

Vladimir N. Vapnik and A. Ya Chervonenkis. 2015. On the uniform convergence of relative frequencies of events to their probabilities. In Meas. Complex. Springer, 11--30.

Cited By

Bonamy MBonnet ÉDéprés HEsperet LGeniet CHilaire CThomassé SWesolek A(2024)Sparse graphs with bounded induced cycle packing number have logarithmic treewidthJournal of Combinatorial Theory, Series B10.1016/j.jctb.2024.03.003167(215-249)Online publication date: Jul-2024
https://doi.org/10.1016/j.jctb.2024.03.003
An SCho KOh E(2023)Faster Algorithms for Cycle Hitting Problems on Disk GraphsAlgorithms and Data Structures10.1007/978-3-031-38906-1_3(29-42)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-38906-1_3
Dvořák ZPekárek J(2023)Induced odd cycle packing number, independent sets, and chromatic numberJournal of Graph Theory10.1002/jgt.22932103:3(502-516)Online publication date: 17-Feb-2023
https://doi.org/10.1002/jgt.22932
Show More Cited By

Index Terms

EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Approximation algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

The Maximum Clique Problem in Multiple Interval Graphs

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval ...
On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcon, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition ...
Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs
Abstract
We study algorithmic properties of the graph class $C H O R D A L - k e$ , that is, graphs that can be turned into a chordal graph by adding at most k edges or, equivalently, the class of graphs of fill-in at most k. It appears that a number of fundamental ... $^{\sqrt{}}^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 68, Issue 2

April 2021

226 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/3446831

Editor:
Éva Tardos
Cornell University

Issue’s Table of Contents

Copyright © 2021 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 January 2021

Accepted: 01 November 2020

Revised: 01 March 2020

Received: 01 March 2019

Published in JACM Volume 68, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

French National Research Agency (ANR)
EPSRC grant FptGeom
ANR grant ESIGMA
“Investissements d’Avenir”
LABEX MILYON
European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
ANR Project DISTANCIA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
311
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)9

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bonamy MBonnet ÉDéprés HEsperet LGeniet CHilaire CThomassé SWesolek A(2024)Sparse graphs with bounded induced cycle packing number have logarithmic treewidthJournal of Combinatorial Theory, Series B10.1016/j.jctb.2024.03.003167(215-249)Online publication date: Jul-2024
https://doi.org/10.1016/j.jctb.2024.03.003
An SCho KOh E(2023)Faster Algorithms for Cycle Hitting Problems on Disk GraphsAlgorithms and Data Structures10.1007/978-3-031-38906-1_3(29-42)Online publication date: 31-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-38906-1_3
Dvořák ZPekárek J(2023)Induced odd cycle packing number, independent sets, and chromatic numberJournal of Graph Theory10.1002/jgt.22932103:3(502-516)Online publication date: 17-Feb-2023
https://doi.org/10.1002/jgt.22932
Dȩbsk MPiecyk MRza̧żewski P(2022)Faster 3-Coloring of Small-Diameter GraphsSIAM Journal on Discrete Mathematics10.1137/21M144771436:3(2205-2224)Online publication date: 6-Sep-2022
https://doi.org/10.1137/21M1447714
Kisfaludi-Bak SOkrasa KRzążewski P(2022)Computing List Homomorphisms in Geometric Intersection GraphsGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_23(313-327)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-15914-5_23

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents