Induced packing of odd cycles in planar graphs

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

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