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 2 O(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.
Original language | English (US) |
---|---|
Pages (from-to) | 28-35 |
Number of pages | 8 |
Journal | Theoretical Computer Science |
Volume | 420 |
DOIs | |
State | Published - Feb 24 2012 |
Keywords
- Fixed parameter tractability
- Induced packing
- Irrelevant vertex technique
- Odd cycles
- Planar graphs
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science