FPT approximation for tournament forest-ordering

Conjecture 4.2 · arXiv:2402.10782

arXiv Conjecture high confidence— first stated 2026-01-23

Authors: Pierre Aboulker, Guillaume Aubian, Raul Lopes

Status open high confidence

Conjecture 4.2 asks for a function f and polynomial-time approximation scheme that, given a tournament T and integer k, either certifies the tournament clique number satisfies $\overrightarrow{\omega}(T)\geq k$ or finds an ordering $\prec$ with $\omega(T^{\prec})\leq f(k)$. The k=3 case was settled (with a constant bound) by Aboulker, Aubian, Charbit, and Thomassé (personal communication cited as [2] in the source paper), but the general case for all k remains open. No follow-up papers resolving or partially resolving the general conjecture were found in a broad web search conducted in May 2026, consistent with the conjecture being only ~4 months old.

Reviewer notes. The conjecture was posed in the concluding section (Section 4) of arXiv:2402.10782 (last revised 2026-01-23). The k=3 base case is established by an unpublished personal communication (Aboulker, Aubian, Charbit, Thomassé), not a public paper. No published or arXiv follow-up addressing the general case was found within the 5-call web search budget. The closely related paper arXiv:2310.04265 ('Clique number of tournaments') introduces the $\overrightarrow{\omega}$ notation and its relation to dichromatic number, and arXiv:2401.07776 ('Computing the clique number of tournaments') addresses computational aspects, but neither appears to resolve Conjecture 4.2.

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

Conjecture. There is a function $f$ such that for every integer $k$, there is a polynomial-time algorithm that, given a tournament $T$, correctly concludes that $\operatorname{\overrightarrow{\omega}}(T)\geq k$, or finds an order $\prec$ of $V(T)$ such that $\omega(T^{\prec})\leq f(k)$

Context

Aboulker et al. [2] proved an approximation version for $k=3$: there is a constant $c$ and a polynomial-time algorithm that either certifies $\operatorname{\overrightarrow{\omega}}(T)\geq 3$ or finds an ordering $\prec$ with $\omega(T^{\prec})\leq c$. The conjecture asks whether such an approximation scheme extends to all $k$.

Source paper

Finding forest-orderings of tournaments is NP-complete
Pierre Aboulker, Guillaume Aubian, Raul Lopes · 2026-01-23
https://arxiv.org/abs/2402.10782