On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
Files
Publication date
2017
Authors
Kisfaludi-Bak, Sándor
van der Zanden, Tom C.
Editors
Fotakis, Dimitris
Pagourtzis, Aris
Paschos, Vangelis
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
taverne
Abstract
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.
Keywords
Taverne, Theoretical Computer Science, General Computer Science
Citation
Kisfaludi-Bak, S & Van Der Zanden, T C 2017, On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. in D Fotakis, A Pagourtzis & V Paschos (eds), Algorithms and Complexity : 10th International Conference, CIAC 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10236 LNCS, Springer, pp. 369-380, 10th International Conference on Algorithms and Complexity, CIAC 2017, Athens, Greece, 24/05/17. https://doi.org/10.1007/978-3-319-57586-5_31, conference