2026-07-22T11:07:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16189 2024-03-06T10:57:07Z ddc:004 open_access

Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives Kunz, Pascal Fluschnik, Till Niedermeier, Rolf Renken, Malte Proximity Graphs Relatively Closest Graphs Gabriel Graphs 3-Colorability Dominating Set Feedback Vertex Set Hamiltonian Cycle Independent Set Exponential-Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pascal Kunz and Till Fluschnik and Rolf Niedermeier and Malte Renken 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.29 urn:nbn:de:0030-drops-161891 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.29 eng https://creativecommons.org/licenses/by/4.0/legalcode