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

Sándor Kisfaludi-Bak; Tom C. Van Der Zanden

doi:10.1007/978-3-319-57586-5_31

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

Sándor Kisfaludi-Bak, Tom C. Van Der Zanden

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	10th International Conference, CIAC 2017, Proceedings
Editors	Dimitris Fotakis, Aris Pagourtzis, Vangelis Paschos
Publisher	Springer
Pages	369-380
Number of pages	12
ISBN (Electronic)	978-3-319-57586-5
ISBN (Print)	9783319575858
DOIs	https://doi.org/10.1007/978-3-319-57586-5_31
Publication status	Published - 2017
Event	10th International Conference on Algorithms and Complexity, CIAC 2017 - Athens, Greece Duration: 24 May 2017 → 26 May 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10236 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	10th International Conference on Algorithms and Complexity, CIAC 2017
Country/Territory	Greece
City	Athens
Period	24/05/17 → 26/05/17

Access to Document

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

ExactFinal published version, 417 KBLicence: Taverne

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. Paschos (Eds.), Algorithms and Complexity: 10th International Conference, CIAC 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

Kisfaludi-Bak, Sándor ; Van Der Zanden, Tom C. / On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. Algorithms and Complexity: 10th International Conference, CIAC 2017, Proceedings. editor / Dimitris Fotakis ; Aris Pagourtzis ; Vangelis Paschos. Springer, 2017. pp. 369-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c0f8edc92f5b4b7aacb9cf9bbd5ced87,

title = "On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs",

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.",

author = "S{\'a}ndor Kisfaludi-Bak and \{Van Der Zanden\}, \{Tom C.\}",

year = "2017",

doi = "10.1007/978-3-319-57586-5\_31",

language = "English",

isbn = "9783319575858",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "369--380",

editor = "Dimitris Fotakis and Aris Pagourtzis and Vangelis Paschos",

booktitle = "Algorithms and Complexity",

note = "10th International Conference on Algorithms and Complexity, CIAC 2017 ; Conference date: 24-05-2017 Through 26-05-2017",

}

Kisfaludi-Bak, S & Van Der Zanden, TC 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

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. / Kisfaludi-Bak, Sándor; Van Der Zanden, Tom C.
Algorithms and Complexity: 10th International Conference, CIAC 2017, Proceedings. ed. / Dimitris Fotakis; Aris Pagourtzis; Vangelis Paschos. Springer, 2017. p. 369-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10236 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 - https://www.scopus.com/pages/publications/85018438981

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 -

Kisfaludi-Bak S, Van Der Zanden TC. On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs. In Fotakis D, Pagourtzis A, Paschos V, editors, Algorithms and Complexity: 10th International Conference, CIAC 2017, Proceedings. Springer. 2017. p. 369-380. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-57586-5_31

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this