Document Open Access Logo

QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs

Authors Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, Florian Sikora

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.12.pdf
  • Filesize: 496 kB
  • 15 pages

Document Identifiers

Author Details

Édouard Bonnet
Panos Giannopoulos
Eun Jung Kim
Pawel Rzazewski
Florian Sikora

Cite As Get BibTex

Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Pawel Rzazewski, and Florian Sikora. QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.12

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 the rather surprising structural result that a disjoint union of cycles is the complement of a disk graph if and only if at most one of those cycles is of odd length. From that, we derive the first QPTAS and subexponential algorithm running in time 2^{O~(n^{2/3})} for Maximum Clique on disk graphs. In stark contrast, Maximum Clique on intersection graphs of filled ellipses or filled triangles is unlikely to have such algorithms, even when the ellipses are close to unit disks. Indeed, we show that there is a constant ratio of approximation which cannot be attained even in time 2^{n^{1-epsilon}}, unless the Exponential Time Hypothesis fails.

Subject Classification

Keywords
  • disk graph
  • maximum clique
  • computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K Agarwal, János Pach, and Micha Sharir. State of the Union (of Geometric Objects). Surveys in Discrete and Computational Geometry: Twenty Years Later. Contemporary Mathematics, 453:9-48, 2008. Google Scholar
  2. Jochen Alber and Jirí Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms, 52(2):134-151, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.10.001.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: http://dx.doi.org/10.1007/BF02523189.
  4. Christoph Ambühl and Uli Wagner. The Clique Problem in Intersection Graphs of Ellipses and Triangles. Theory Comput. Syst., 38(3):279-292, 2005. URL: http://dx.doi.org/10.1007/s00224-005-1141-6.
  5. Aistis Atminas and Viktor Zamaraev. On forbidden induced subgraphs for unit disk graphs. arXiv preprint arXiv:1602.08148, 2016. Google Scholar
  6. Jørgen Bang-Jensen, Bruce Reed, Mathias Schacht, Robert Šámal, Bjarne Toft, and Uli Wagner. On six problems posed by Jarik Nešetřil. Topics in Discrete Mathematics, pages 613-627, 2006. Google Scholar
  7. Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres J. Ruiz-Vargas. Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15-17, 2014, New Delhi, India, pages 187-198, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2014.187.
  8. Édouard Bonnet, Bruno Escoffier, Eun Jung Kim, and Vangelis Th. Paschos. On Subexponential and FPT-Time Inapproximability. Algorithmica, 71(3):541-565, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9889-1.
  9. Édouard Bonnet, Panos Giannopoulos, Eun Jung Kim, Paweł Rzążewski, and Florian Sikora. QPTAS and subexponential algorithm for maximum clique on disk graphs. CoRR, abs/1712.05010, 2017. URL: http://arxiv.org/abs/1712.05010.
  10. Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad. Graph classes: a survey. SIAM, 1999. Google Scholar
  11. Heinz Breu and David G. Kirkpatrick. Unit disk graph recognition is NP-hard. Comput. Geom., 9(1-2):3-24, 1998. URL: http://dx.doi.org/10.1016/S0925-7721(97)00014-X.
  12. Valentin E. Brimkov, Konstanty Junosza-Szaniawski, Sean Kafer, Jan Kratochvíl, Martin Pergel, Paweł Rzążewski, Matthew Szczepankiewicz, and Joshua Terhaar. Homothetic polygons and beyond: Intersection graphs, recognition, and maximum clique. CoRR, abs/1411.2928, 2014. URL: http://arxiv.org/abs/1411.2928.
  13. Sergio Cabello. Maximum clique for disks of two sizes. Open problems from Geometric Intersection Graphs: Problems and Directions CG Week Workshop, Eindhoven, June 25, 2015 (http://cgweek15.tcs.uj.edu.pl/problems.pdf), 2015. [Online; accessed 07-December-2017].
  14. Sergio Cabello. Open problems presented at the Algorithmic Graph Theory on the Adriatic Coast workshop, Koper, Slovenia (https://conferences.matheo.si/event/6/picture/35.pdf), June 16-19 2015.
  15. Sergio Cabello, Jean Cardinal, and Stefan Langerman. The clique problem in ray intersection graphs. Discrete & Computational Geometry, 50(3):771-783, 2013. URL: http://dx.doi.org/10.1007/s00454-013-9538-5.
  16. Stephan Ceroi. The clique number of unit quasi-disk graphs. Technical Report RR-4419, INRIA, 2002. URL: https://hal.inria.fr/inria-00072169.
  17. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(02)00294-8.
  18. Miroslav Chlebík and Janka Chlebíková. Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci., 354(3):320-338, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2005.11.029.
  19. Brent N. Clark, Charles J. Colbourn, and David S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165-177, 1990. URL: http://dx.doi.org/10.1016/0012-365X(90)90358-O.
  20. Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput., 34(6):1302-1323, 2005. URL: http://dx.doi.org/10.1137/S0097539702402676.
  21. Aleksei V. Fishkin. Disk graphs: A short survey. In Klaus Jansen and Roberto Solis-Oba, editors, Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, volume 2909 of Lecture Notes in Computer Science, pages 260-264. Springer, 2003. URL: http://dx.doi.org/10.1007/978-3-540-24592-6_23.
  22. Zoltán Füredi. The number of maximal independent sets in connected graphs. Journal of Graph Theory, 11(4):463-470, 1987. URL: http://dx.doi.org/10.1002/jgt.3190110403.
  23. Ervin Györi, Alexandr V Kostochka, and Tomasz Łuczak. Graphs without short odd cycles are nearly bipartite. Discrete Mathematics, 163(1):279-284, 1997. URL: http://dx.doi.org/10.1016/0012-365X(95)00321-M.
  24. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  25. Ross J. Kang and Tobias Müller. Sphere and Dot Product Representations of Graphs. Discrete & Computational Geometry, 47(3):548-568, 2012. URL: http://dx.doi.org/10.1007/s00454-012-9394-8.
  26. Ken-ichi Kawarabayashi and Bruce A. Reed. Odd cycle packing. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 695-704, 2010. URL: http://dx.doi.org/10.1145/1806689.1806785.
  27. Chaya Keller, Shakhar Smorodinsky, and Gábor Tardos. On Max-Clique for intersection graphs of sets and the Hadwiger-Debrunner numbers. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2254-2263, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.148.
  28. Jan Kratochvíl. Intersection graphs of noncrossing arc-connected sets in the plane. In Graph Drawing, Symposium on Graph Drawing, GD '96, Berkeley, California, USA, September 18-20, Proceedings, pages 257-270, 1996. URL: http://dx.doi.org/10.1007/3-540-62495-3_53.
  29. J. Kratochvíl. Precoloring extension with fixed color bound. Acta Mathematica Universitatis Comenianae. New Series, 62(2):139-153, 1993. URL: http://eudml.org/doc/118661.
  30. Dániel Marx. Parameterized Complexity and Approximation Algorithms. Comput. J., 51(1):60-78, 2008. URL: http://dx.doi.org/10.1093/comjnl/bxm048.
  31. Terry A McKee and Fred R McMorris. Topics in intersection graph theory. SIAM, 1999. Google Scholar
  32. Matthias Middendorf and Frank Pfeiffer. The max clique problem in classes of string-graphs. Discrete Mathematics, 108(1-3):365-372, 1992. URL: http://dx.doi.org/10.1016/0012-365X(92)90688-C.
  33. Dana Moshkovitz and Ran Raz. Two-query PCP with subconstant error. J. ACM, 57(5):29:1-29:29, 2010. URL: http://dx.doi.org/10.1145/1754399.1754402.
  34. Vijay Raghavan and Jeremy P. Spinrad. Robust algorithms for restricted domains. J. Algorithms, 48(1):160-172, 2003. URL: http://dx.doi.org/10.1016/S0196-6774(03)00048-8.
  35. Peter Guthrie Tait. Some elementary properties of closed plane curves. Messenger of Mathematics, New Series, 69:270-272, 1877. Google Scholar
  36. Erik Jan van Leeuwen. Optimization and Approximation on Systems of Geometric Objects. PhD thesis, Utrecht University, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact