Finding a shortest even hole in polynomial time

An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Cornu?jols, Kapoor, and Vu?kovi? gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour estimated that Conforti et al.'s algorithm runs in (Formula presented.) time on an (Formula presented.) -vertex graph and reduced the required time to (Formula presented.). Subsequently, da Silva and Vu?kovi?, Chang and Lu, and Lai, Lu, and Thorup?improved the time to (Formula presented.), (Formula presented.), and (Formula presented.), respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl that runs in (Formula presented.) time, which Lai et al. also reduced to (Formula presented.). By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour?(respectively) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP-hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for 16 years by, for example, Chudnovsky et al. and Johnson. We resolve this open problem by augmenting Chudnovsky et al.'s even-hole detection algorithm into the first known polynomial-time algorithm, running in (Formula presented.) time, for finding a shortest even hole in an (Formula presented.) -vertex graph that contains even holes. ? 2021 Wiley Periodicals LLC