  An even (respectively, odd) hole in a graph is an induced cycle with even
(respectively, odd) length that is at least four. Bienstock [DM 1991 and 1992]
proved that detecting an even (respectively, odd) hole containing a given
vertex is NP-complete. Conforti, Chornu\'ejols, Kappor, and Vu\v{s}kovi\'{c}
[FOCS 1997] gave the first known polynomial-time algorithm to determine whether
a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour [JGT 2005]
estimated that Conforti et al.'s algorithm runs in $O(n^{40})$ time on an
$n$-vertex graph and reduced the required time to $O(n^{31})$. Subsequently,
da~Silva and Vu\v{s}kovi\'{c}~[JCTB 2013], Chang and Lu [JCTB 2017], and Lai,
Lu, and Thorup [STOC 2020] improved the time to $O(n^{19})$, $O(n^{11})$, and
$O(n^9)$, 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 [JACM 2020] that runs in $O(n^9)$ time, which Lai et
al. also reduced to $O(n^8)$. By extending Chudnovsky et al.'s techniques for
detecting odd holes, Chudnovsky, Scott, and Seymour [Combinatorica 2020 to
appear] (respectively, [arXiv 2020]) 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 at least 15 years by, e.g., Chudnovsky et al. [JGT
2005] and Johnson [TALG 2005]. We resolve this long-standing open problem by
giving the first known polynomial-time algorithm, running in $O(n^{31})$ time,
for finding a shortest even hole in an $n$-vertex graph that contains even
holes.
