Shortest even hole detection

Open Problem: Finding a Shortest Even Hole · arXiv:2009.05691

arXiv Problem medium confidence— first stated 2020-09-12

Authors: Linda Cook, Paul Seymour

Status solved high confidence

The problem of finding a shortest even hole in polynomial time was resolved by Cheong and Lu in a paper posted to arXiv on August 15, 2020 — roughly one month before Cook and Seymour posed it as an open problem — giving an O(n^31) algorithm; Chiu, Lai, and Lu subsequently improved this to O(n^23) in July 2022.

Cited literature (2)

proof Finding a Shortest Even Hole in Polynomial Time (2020)

Hou-Teng Cheong, Hsueh-I Lu · Journal of Graph Theory · arXiv:2008.06740

Gives the first polynomial-time algorithm (O(n^31)) for finding a shortest even hole in an n-vertex graph; this preprint was posted on August 15, 2020, about one month before Cook–Seymour's paper posed the problem.
partial Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd and Even Holes (2022)

Yung-Chung Chiu, Kai-Yuan Lai, Hsueh-I Lu · arXiv preprint · arXiv:2207.07613

Improves the running time for finding a shortest even hole from O(n^31) (Cheong–Lu) to O(n^23), along with improvements for odd holes and perfect graph recognition.

Reviewer notes. The Cheong–Lu solution (arXiv:2008.06740, submitted August 15, 2020) predates the Cook–Seymour open problem posting (arXiv:2009.05691, submitted September 12, 2020) by approximately one month; Cook and Seymour were likely unaware of this concurrent work when writing. The problem is therefore fully solved. Cheong–Lu's journal version appeared in Journal of Graph Theory in 2022.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. Finding a shortest even hole in a graph (if one exists).

Context

After surveying polynomial-time algorithms for detecting even holes, the authors note that finding a shortest even hole remains open: "Another is finding a shortest even hole if there is one; this we have not yet been able to solve." This is posed as an analogue of the result of Chudnovsky, Scott and Seymour [8] that finds a shortest odd hole in $O(|G|^{14})$ time.

Notes. Stated informally in the introduction without a labelled environment.

Source paper

Detecting a long even hole
Linda Cook, Paul Seymour · 2020-09-12
https://arxiv.org/abs/2009.05691 PDF source