Approximation conjecture for the ordered clique number of tournaments

From papers

Let TT be a tournament, and let TT^{\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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.