TY - GEN

T1 - On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs

AU - Kisfaludi-Bak, Sándor

AU - Van Der Zanden, Tom C.

PY - 2017

Y1 - 2017

N2 - We study the exact complexity of the Hamiltonian Cycle and the q-Colouring problem in disk graphs. We show that the Hamiltonian Cycle problem can be solved in (formula presented) on n-vertex disk graphs where the ratio of the largest and smallest disk radius is O(1). We also show that this is optimal: assuming the Exponential Time Hypothesis, there is no (formula presented)-time algorithm for Hamiltonian Cycle, even on unit disk graphs. We give analogous results for graph colouring: under the Expo-nential Time Hypothesis, for any fixed q, q-Colouring does not admit a (formula presented)-time algorithm, even when restricted to unit disk graphs, and it is solvable in (formula presented)-time on disk graphs.

AB - We study the exact complexity of the Hamiltonian Cycle and the q-Colouring problem in disk graphs. We show that the Hamiltonian Cycle problem can be solved in (formula presented) on n-vertex disk graphs where the ratio of the largest and smallest disk radius is O(1). We also show that this is optimal: assuming the Exponential Time Hypothesis, there is no (formula presented)-time algorithm for Hamiltonian Cycle, even on unit disk graphs. We give analogous results for graph colouring: under the Expo-nential Time Hypothesis, for any fixed q, q-Colouring does not admit a (formula presented)-time algorithm, even when restricted to unit disk graphs, and it is solvable in (formula presented)-time on disk graphs.

UR - http://www.scopus.com/inward/record.url?scp=85018438981&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-57586-5_31

DO - 10.1007/978-3-319-57586-5_31

M3 - Conference contribution

AN - SCOPUS:85018438981

SN - 9783319575858

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 369

EP - 380

BT - Algorithms and Complexity

A2 - Fotakis, Dimitris

A2 - Pagourtzis, Aris

A2 - Paschos, Vangelis

PB - Springer

T2 - 10th International Conference on Algorithms and Complexity, CIAC 2017

Y2 - 24 May 2017 through 26 May 2017

ER -