Approximation conjecture for the ordered clique number of tournaments
Let be a tournament, and let be the graph associated with an ordering of by retaining the backward arcs. Define the ordered clique number by
Approximation conjecture. There is a function such that for every integer , there is a polynomial-time algorithm which, given a tournament , correctly concludes that , or finds an ordering of such that . 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
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.