Induced packing of odd cycles in planar graphs

Golovach, P.A.; Kamiński, M.; Paulusma, D.; Thilikos, D.M.

doi:10.1016/j.tcs.2011.11.004

Induced packing of odd cycles in planar graphs

Golovach, P.A.; Kamiński, M.; Paulusma, D.; Thilikos, D.M.

Authors

P.A. Golovach

M. Kamiński

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

D.M. Thilikos

Abstract

An induced packing of odd cycles in a graph is a packing such that there is no edge in the graph between any two odd cycles in the packing. We prove that an induced packing of k odd cycles in an n-vertex graph can be found (if it exists) in time 2O(k3/2)⋅n2+ϵ (for any constant ϵ>0) when the input graph is planar. We also show that deciding if a graph has an induced packing of two odd induced cycles is NP-complete.

Citation

Golovach, P., Kamiński, M., Paulusma, D., & Thilikos, D. (2012). Induced packing of odd cycles in planar graphs. Theoretical Computer Science, 420, 28-35. https://doi.org/10.1016/j.tcs.2011.11.004

Journal Article Type	Article
Publication Date	Feb 24, 2012
Deposit Date	Dec 6, 2011
Journal	Theoretical Computer Science
Print ISSN	0304-3975
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	420
Pages	28-35
DOI	https://doi.org/10.1016/j.tcs.2011.11.004
Keywords	Planar graphs, Induced packing, Odd cycles, Irrelevant vertex technique, Fixed parameter tractability.
Public URL	https://durham-repository.worktribe.com/output/1524782