Document Open Access Logo

Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives

Authors Pascal Kunz , Till Fluschnik , Rolf Niedermeier , Malte Renken

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.29.pdf
  • Filesize: 1.44 MB
  • 19 pages

Document Identifiers

Author Details

Pascal Kunz
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Till Fluschnik
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Rolf Niedermeier
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany
Malte Renken
  • Algorithmics and Computational Complexity, Technische Universität Berlin, Germany

Funding

  • Kunz, Pascal: Supported by DFG Research Training Group 2434 "Facets of Complexity".
  • Fluschnik, Till: Supported by DFG, projects TORE, NI 369/18, and MATE, NI 369/17.
  • Renken, Malte: Supported by DFG, project MATE, NI 369/17.

Acknowledgements

This work is based on the first author’s master’s thesis. In memory of Rolf Niedermeier, our colleague, friend, and mentor, who sadly passed away before this paper was published.

Cite AsGet BibTex

Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken. Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SWAT.2022.29

Abstract

Proximity graphs have been studied for several decades, motivated by applications in computational geometry, geography, data mining, and many other fields. However, the computational complexity of classic graph problems on proximity graphs mostly remained open. We study 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the following classes of proximity graphs: relative neighborhood graphs, Gabriel graphs, and relatively closest graphs. We prove that all of the aforementioned problems remain NP-hard on these graphs, except for 3-Colorability and Hamiltonian Cycle on relatively closest graphs, where the former is trivial and the latter is left open. Moreover, for every NP-hard case we additionally show that no 2^{o(n^{1/4})}-time algorithm exists unless the Exponential-Time Hypothesis (ETH) fails, where n denotes the number of vertices.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Proximity Graphs
  • Relatively Closest Graphs
  • Gabriel Graphs
  • 3-Colorability
  • Dominating Set
  • Feedback Vertex Set
  • Hamiltonian Cycle
  • Independent Set
  • Exponential-Time Hypothesis

Metrics

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

Related Versions

References

  1. Jochen Alber, Hans L. Bodlaender, Henning Fernau, Ton Kloks, and Rolf Niedermeier. Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461-493, 2002. URL: https://doi.org/10.1007/s00453-001-0116-5.
  2. Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, January 1994. URL: https://doi.org/10.1145/174644.174650.
  3. Michael A. Bekos, Martin Gronemann, and Chrysanthi N. Raftopoulou. Two-page book embeddings of 4-planar graphs. Algorithmica, 75(1):158-185, 2016. URL: https://doi.org/10.1007/s00453-015-0016-8.
  4. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-77974-2.
  5. Hans L. Bodlaender. On disjoint cycles. International Journal of Foundations of Computer Science, 5(1):59-68, 1994. URL: https://doi.org/10.1142/S0129054194000049.
  6. Prosenjit Bose, Vida Dujmović, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Vera Sacristán, Maria Saumell, and David R Wood. Proximity graphs: E, δ, Δ, χ and ω. International Journal of Computational Geometry & Applications, 22(05):439-469, 2012. URL: https://doi.org/10.1142/S0218195912500112.
  7. Prosenjit Bose, William Lenhart, and Giuseppe Liotta. Characterizing proximity trees. Algorithmica, 16(1):83-110, 1996. URL: https://doi.org/10.1007/BF02086609.
  8. Franz Brandenburg, David Eppstein, Michael T. Goodrich, Stephen Kobourov, Giuseppe Liotta, and Petra Mutzel. Selected open problems in graph drawing. In Proceedings of the 11th International Symposium on Graph Drawing (GD), pages 515-539, 2004. URL: https://doi.org/10.1007/978-3-540-24595-7_55.
  9. Rowland Leonard Brooks. On colouring the nodes of a network. Mathematical Proceedings of the Cambridge Philosophical Society, 37(2):194-197, 1941. URL: https://doi.org/10.1017/S030500410002168X.
  10. Jean Cardinal, Sébastien Collette, and Stefan Langerman. Empty region graphs. Computational Geometry, 42(3):183-195, 2009. URL: https://doi.org/10.1016/J.COMGEO.2008.09.003.
  11. Robert Cimikowski. Coloring proximity graphs. In Memoranda in Computer and Cognitive Science: Proceedings of the First Workshop on Proximity Graphs, pages 141-156, 1989. URL: https://doi.org/10.21236/ada237250.
  12. Robert Cimikowski. Coloring certain proximity graphs. Computers & Mathematics with Applications, 20(3):69-82, 1990. URL: https://doi.org/10.1016/0898-1221(90)90032-F.
  13. Robert J Cimikowski. Properties of some Euclidean proximity graphs. Pattern Recognition Letters, 13(6):417-423, 1992. URL: https://doi.org/10.1016/0167-8655(92)90048-5.
  14. Reinhard Diestel. Graph Theory. Springer, 5th edition, 2016. URL: https://doi.org/10.1007/978-3-662-53622-3.
  15. Michael B. Dillencourt. Finding Hamiltonian cycles in Delaunay triangulations is NP-complete. Discrete Applied Mathematics, 64(3):207-217, 1996. URL: https://doi.org/10.1016/0166-218X(94)00125-W.
  16. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  17. Peter Eades and Sue Whitesides. Nearest neighbour graph realizability is NP-hard. In Proceedings of the 2nd Latin American Symposium on Theoretical Informatics (LATIN), pages 245-256, 1995. URL: https://doi.org/10.1007/3-540-59175-3_93.
  18. K. Ruben Gabriel and Robert R. Sokal. A new statistical approach to geographic variation analysis. Systematic Biology, 18(3):259-278, 1969. URL: https://doi.org/10.2307/2412323.
  19. M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976. URL: https://doi.org/10.1016/0304-3975(76)90059-1.
  20. M. R. Garey, D. S. Johnson, and R. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4):704-714, 1976. URL: https://doi.org/10.1137/0205049.
  21. Branko Grünbaum. Grötzsch’s theorem on 3-colorings. Michigan Mathematical Journal, 10(3):303-310, 1963. URL: https://doi.org/10.1307/mmj/1028998916.
  22. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  23. J. W. Jaromczyk and M. Kowaluk. A note on relative neighborhood graphs. In Proceedings of the 3rd Annual Symposium on Computational Geometry (SoCG), pages 233-241, 1987. URL: https://doi.org/10.1145/41958.41983.
  24. J. W. Jaromczyk and G. T. Toussaint. Relative neighborhood graphs and their relatives. Proceedings of the IEEE, 80(9):1502-1517, 1992. URL: https://doi.org/10.1109/5.163414.
  25. Jon Kleinberg and Amit Kumar. Wavelength conversion in optical networks. Journal of Algorithms, 38(1):25-50, 2001. URL: https://doi.org/10.1006/jagm.2000.1137.
  26. Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken. Most classic problems remain NP-hard on relative neighborhood graphs and their relatives, 2021. URL: https://doi.org/10.48550/ARXIV.2107.04321.
  27. Philip M Lankford. Regionalization: Theory and alternative algorithms. Geographical Analysis, 1(2):196-212, 1969. URL: https://doi.org/10.1111/j.1538-4632.1969.tb00615.x.
  28. Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin of EATCS, 105:41-71, 2011. URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/92.
  29. László Lovász. Three short proofs in graph theory. Journal of Combinatorial Theory Series B, 19(3):269-271, 1975. URL: https://doi.org/10.1016/0095-8956(75)90089-1.
  30. David W. Matula and Robert R. Sokal. Properties of Gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical Analysis, 12(3):205-222, 1980. URL: https://doi.org/10.1111/j.1538-4632.1980.tb00031.x.
  31. Joseph SB Mitchell and Wolfgang Mulzer. Proximity algorithms. In Handbook of Discrete and Computational Geometry, chapter 32, pages 849-874. Chapman and Hall/CRC, 3rd edition, 2017. Google Scholar
  32. Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pages 571-575, 1996. URL: https://doi.org/10.1145/237814.238005.
  33. Ewald Speckenmeyer. Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen [Investigations into the Feedback Vertex Set problem in Undirected Graphs]. PhD thesis, Universität Paderborn, 1983. Google Scholar
  34. Godfried T. Toussaint. The relative neighbourhood graph of a finite planar set. Pattern Recognition, 12(4):261-268, 1980. URL: https://doi.org/10.1016/0031-3203(80)90066-7.
  35. Godfried T. Toussaint. Applications of the relative neighbourhood graph. International Journal of Advances in Computer Science and Its Applications, 4(3):77-85, 2014. URL: http://journals.theired.org/journals/paper/details/4323.html.
  36. Shuichi Ueno, Yoji Kajitani, and Shin'ya Gotoh. On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics, 72(1-3):355-360, 1988. URL: https://doi.org/10.1016/0012-365X(88)90226-9.
  37. Roderick B. Urquhart. Some properties of the planar Euclidean relative neighbourhood graph. Pattern Recognition Letters, 1(5):317-322, 1983. URL: https://doi.org/10.1016/0167-8655(83)90070-3.
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 Imprint Privacy Contact