A faster algorithm to recognize even-hole-free graphs

We study the problem of determining whether an n-node graph G contains an even hole  , i.e., an induced simple cycle consisting of an even number of nodes. Conforti, Cornuéjols, Kapoor, and Vušković gave the first polynomial-time algorithm for the problem, which runs in O(n40)O(n40) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O(n31)O(n31). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O(n19)O(n19) time. In this paper, we solve the problem in O(n11)O(n11) time via a decomposition-based algorithm that relies on the decomposition theorem of da Silva and Vušković. Moreover, if G contains even holes, then our algorithm also outputs an even hole of G   in O(n11)O(n11) time.