A faster algorithm to recognize even-hole-free graphs

We study the problem of determining whether an n -node m -edge graph has 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 ( n 40 ) time. Later, Chudnovsky, Kawarabayashi, and Seymour reduced the running time to O ( n 31 ). The best previously known algorithm for the problem, due to da Silva and Vušković, runs in O ( n 19 ) time. In this paper, we solve the problem in time O ( n 11 ).

Authors

• Hsien-Chih Chang
• Hsueh-I Lu

Keywords

No keywords are indexed for this paper.