On the exact complexity of hamiltonian cycle and q-colouring in disk graphs

S. Kisfaludi-Bak, T.C. van der Zanden

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
EditorsD. Fotakis, A. Pagourtzis, V.Th. Paschos
Place of PublicationDordrecht
PublisherSpringer
Pages369-380
Number of pages12
ISBN (Electronic)978-3-319-57586-5
ISBN (Print)978-3-319-57585-8
DOIs
Publication statusPublished - 2017
Event10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece
Duration: 24 May 201726 May 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10236 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Algorithms and Complexity, CIAC 2017
Abbreviated titleCIAC 2017
CountryGreece
CityAthens
Period24/05/1726/05/17

Fingerprint Dive into the research topics of 'On the exact complexity of hamiltonian cycle and q-colouring in disk graphs'. Together they form a unique fingerprint.

  • Cite this

    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. T. Paschos (Eds.), Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings (pp. 369-380). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS). Springer. https://doi.org/10.1007/978-3-319-57586-5_31