The parameterized complexity of graph cyclability

Petr A. Golovach; Marcin Kamiński; Spyridon Maniatis; Dimitrios M. Thilikos

doi:10.1007/978-3-662-44777-2_41

The parameterized complexity of graph cyclability

Petr A. Golovach, Marcin Kamiński, Spyridon Maniatis, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 ^{2O(k2 log k)} · n². Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs.

Original language	English (US)
Title of host publication	Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
Publisher	Springer Verlag
Pages	492-504
Number of pages	13
ISBN (Print)	9783662447765
DOIs	https://doi.org/10.1007/978-3-662-44777-2_41
State	Published - 2014
Event	22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland Duration: Sep 8 2014 → Sep 10 2014

Publication series

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

Other

Other	22nd Annual European Symposium on Algorithms, ESA 2014
Country/Territory	Poland
City	Wroclaw
Period	9/8/14 → 9/10/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-44777-2_41

Cite this

Golovach, P. A., Kamiński, M., Maniatis, S., & Thilikos, D. M. (2014). The parameterized complexity of graph cyclability. In Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings (pp. 492-504). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8737 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-44777-2_41

The parameterized complexity of graph cyclability. / Golovach, Petr A.; Kamiński, Marcin; Maniatis, Spyridon et al.
Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Springer Verlag, 2014. p. 492-504 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8737 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Golovach, PA, Kamiński, M, Maniatis, S & Thilikos, DM 2014, The parameterized complexity of graph cyclability. in Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8737 LNCS, Springer Verlag, pp. 492-504, 22nd Annual European Symposium on Algorithms, ESA 2014, Wroclaw, Poland, 9/8/14. https://doi.org/10.1007/978-3-662-44777-2_41

Golovach PA, Kamiński M, Maniatis S, Thilikos DM. The parameterized complexity of graph cyclability. In Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings. Springer Verlag. 2014. p. 492-504. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-44777-2_41

@inproceedings{571cf819f0b04c83baefdbbc89f65562,

title = "The parameterized complexity of graph cyclability",

abstract = "The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 2O(k2 log k) · n2. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs.",

author = "Golovach, {Petr A.} and Marcin Kami{\'n}ski and Spyridon Maniatis and Thilikos, {Dimitrios M.}",

year = "2014",

doi = "10.1007/978-3-662-44777-2_41",

language = "English (US)",

isbn = "9783662447765",

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

publisher = "Springer Verlag",

pages = "492--504",

booktitle = "Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings",

note = "22nd Annual European Symposium on Algorithms, ESA 2014 ; Conference date: 08-09-2014 Through 10-09-2014",

}

TY - GEN

T1 - The parameterized complexity of graph cyclability

AU - Golovach, Petr A.

AU - Kamiński, Marcin

AU - Maniatis, Spyridon

AU - Thilikos, Dimitrios M.

PY - 2014

Y1 - 2014

N2 - The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 2O(k2 log k) · n2. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs.

AB - The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 2O(k2 log k) · n2. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs.

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

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

U2 - 10.1007/978-3-662-44777-2_41

DO - 10.1007/978-3-662-44777-2_41

M3 - Conference contribution

AN - SCOPUS:84958526994

SN - 9783662447765

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

SP - 492

EP - 504

BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings

PB - Springer Verlag

T2 - 22nd Annual European Symposium on Algorithms, ESA 2014

Y2 - 8 September 2014 through 10 September 2014

ER -

The parameterized complexity of graph cyclability

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this