Approximation conjecture for the ordered clique number of tournaments

About 27 years old · traced to

Let TT be a tournament, and let T≺T^{\prec} be the graph associated with an ordering ≺\prec of V(T)V(T) by retaining the backward arcs. Define the ordered clique number by

ω→(T)=min⁡{ω(T≺):≺ is a total order of V(T)}.\overrightarrow{\omega}(T)=\min\{\omega(T^{\prec}):\prec\text{ is a total order of }V(T)\}.

Approximation conjecture. There is a function ff such that for every integer kk, there is a polynomial-time algorithm which, given a tournament TT, correctly concludes that ω→(T)≥k\overrightarrow{\omega}(T)\geq k, or finds an ordering ≺\prec of V(T)V(T) such that ω(T≺)≤f(k)\omega(T^{\prec})\leq f(k). This conjecture proposes a polynomial-time gap approximation for the ordered clique number; the source states preceding approximation results but gives no resolution of the conjecture.

References

Primary source

Pierre Aboulker, Guillaume Aubian and Raul Lopes, “Finding forest-orderings of tournaments is NP-complete”, arXiv:2402.10782 (2026).

Additional references

2 papers in this index state this conjecture (1999–2024). The statement above is taken from the most recent of them; the others are arXiv:math/9911202.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.