Approximation conjecture for the ordered clique number of tournaments
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.
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
Sign in to submit a solution.
No solutions have been posted yet.