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 now study 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, and Independent Set on the proximity graph classes relative neighborhood graphs, Gabriel graphs, and relatively closest graphs. We prove that all of the 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 ETH fails, where n denotes the number of vertices.
翻译:近距离图已经研究了几十年,其动机是计算几何、地理、数据挖掘和许多其他领域的应用。然而,近距离图上经典图表问题的计算复杂性大部分仍未解决。我们现在对近距离图上的3-可分性、支配性Set、反馈VertexSet、汉密尔顿周期和独立Set进行了研究,对近距离图类相对相邻图、加布里埃尔图和相对最近的图表进行了独立Set。我们证明,在这些图表上,所有问题仍然很难解决,除了3-可分性和汉密尔顿周期在相对最近的图表上,前者微不足道,而后者则没有打开。此外,对于每个NP-硬案例,我们额外表明,除非ET失败,否则没有$(n ⁇ 1/4}}时间算法,这里没有说明脊椎的数目。