Fixed-ℓ long odd hole detection complexity

Status open medium confidence

No paper has substantially improved the $|G|^{O(\ell)}$ exponent for detecting long holes or long odd holes for fixed $\ell$. The closely related problem of detecting long even holes was addressed by Cook and Seymour (arXiv:2009.05691), who gave an $O(|G|^{9\ell+3})$ algorithm — still $|G|^{O(\ell)}$. Hardness results show W[1]-hardness when $\ell$ is part of the input, suggesting that eliminating the $\ell$-dependence from the exponent entirely is likely impossible under standard complexity assumptions, but the question of a substantially smaller polynomial degree for fixed $\ell$ remains open.

Cited literature (1)

• partial Detecting a long even hole (2020)
  Linda Cook, Paul Seymour · European Journal of Combinatorics (2022) · arXiv:2009.05691

  Provides an $O(|G|^{9\ell+3})$ algorithm for detecting long even holes for fixed $\ell \geq 4$; a closely related variant that still runs in $|G|^{O(\ell)}$ time and does not resolve the running-time question for long holes or long odd holes.

Reviewer notes. The open question asks whether the $|G|^{O(\ell)}$ dependence can be substantially improved for fixed $\ell$. Cook and Seymour 2020 (arXiv:2009.05691) provides adjacent progress for even holes at $O(|G|^{9\ell+3})$, still polynomial in the same sense. W[1]-hardness when $\ell$ is part of the input (established in the FPT literature) implies that a uniform algorithm simultaneously polynomial in both $|G|$ and $\ell$ is unlikely, but does not rule out a smaller polynomial degree for each fixed $\ell$. No direct improvement to the $O(|G|^{\ell+1})$ or $O(|G|^{20\ell+40})$ bounds was found in the indexed literature.

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