Detecting even holes

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 ³¹) for an n-vertex graph (and we sketch another more complicated algorithm that runs in time 0(n¹⁵)) while the earlier algorithm appears to take about 0(n⁴⁰); 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."