Detecting even holes

Maria Chudnovsky, Ken Ichi Kawarabayashi, Paul Seymour

Research output: Contribution to journalArticle

28 Scopus citations

Abstract

Conforti, Cornuéjols, Kapoor, and Vušković (Even-hole-free graphs. Part II: Recognition algorithm, J Graph Theory 40 (2002), 238-266) gave a 73-page polynomial time algorithm to test whether a graph has an induced subgraph that is a cycle of even length. Here, we provide, another algorithm to solve the same problem. The differences are: (1) our algorithm is simpler - we are able to search directly for even holes, while the algorithm of Conforti et al. made use of a structure theorem for even-hole-free graphs, proved in an earlier paper (Conforti, Cornuéjols, Kapoor, and Vušković, Even-hole-free graphs: Part I: Decomposition theorem, J Graph Theory 39 (2002), 6-49); (2) our algorithm is marginally faster - O(n 31) for an n-vertex graph (and we sketch another more complicated algorithm that runs in time 0(n15)) while the earlier algorithm appears to take about 0(n40); and (3) we can permit 0/1 weights on the edges and look for an induced cycle of even weight. Consequently, we can test whether a graph is "odd Signable."

Original languageEnglish (US)
Pages (from-to)85-111
Number of pages27
JournalJournal of Graph Theory
Volume48
Issue number2
DOIs
StatePublished - Feb 2005

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Keywords

  • Even hole
  • Recognition algorithm
  • Signed graph

Fingerprint Dive into the research topics of 'Detecting even holes'. Together they form a unique fingerprint.

  • Cite this