Induced packing of odd cycles in planar graphs

Petr A. Golovach, Marcin Kamiski, Danil Paulusma, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)28-35
Number of pages8
JournalTheoretical Computer Science
Volume420
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Induced packing of odd cycles in planar graphs'. Together they form a unique fingerprint.

Cite this