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

S. Kisfaludi-Bak; T.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. Kisfaludi-Bak, T.C. van der Zanden

Algorithms

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

6 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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings
Editors	D. Fotakis, A. Pagourtzis, V.Th. Paschos
Place of Publication	Dordrecht
Publisher	Springer
Pages	369-380
Number of pages	12
ISBN (Electronic)	978-3-319-57586-5
ISBN (Print)	978-3-319-57585-8
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)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	10th International Conference on Algorithms and Complexity, CIAC 2017
Abbreviated title	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

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

Kisfaludi-Bak, S. ; van der Zanden, T.C. / On the exact complexity of hamiltonian cycle and q-colouring in disk graphs. Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings. editor / D. Fotakis ; A. Pagourtzis ; V.Th. Paschos. Dordrecht : Springer, 2017. pp. 369-380 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{7af60b2224b041bf93a8c7813ca836b2,

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. Kisfaludi-Bak and {van der Zanden}, T.C.",

year = "2017",

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

language = "English",

isbn = "978-3-319-57585-8",

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

publisher = "Springer",

pages = "369--380",

editor = "D. Fotakis and A. Pagourtzis and V.Th. Paschos",

booktitle = "Algorithms and Complexity",

note = "10th International Conference on Algorithms and Complexity, CIAC 2017, 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 & VT Paschos (eds), Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10236 LNCS, Springer, Dordrecht, 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.; van der Zanden, T.C.
Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings. ed. / D. Fotakis; A. Pagourtzis; V.Th. Paschos. Dordrecht: 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.

AU - van der Zanden, T.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 - 978-3-319-57585-8

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

A2 - Pagourtzis, A.

A2 - Paschos, V.Th.

PB - Springer

CY - Dordrecht

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 VT, editors, Algorithms and Complexity: 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017, Proceedings. Dordrecht: 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