Detecting even holes
Maria Chudnovsky, Ken‐ichi Kawarabayashi, Paul D. Seymour · Journal of Graph Theory · 2004
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(n31) for an n-vertex graph (and we sketch another more complicated algorithm that runs in time O(n15)) while the earlier algorithm appears to take about O(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.”. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 85–111, 2005