Deterministic query complexity of finding kings in tournaments
Given oracle access to an unknown tournament on vertices, where one query reveals the orientation of a selected edge, determine the deterministic query complexity of finding a vertex such that, for every vertex , there is a directed path from to of length at most . Equivalently, determine the asymptotic complexity of finding a -king. The known bounds are ; in particular, it remains open whether .
References
- A King for Almost Everyone — arXiv — Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
Source: arXiv
Progress summary
A new paper claims that, with the same query budget, one can find a king controlling almost any prescribed fraction of a tournament, but finding one controlling everyone remains open.
The problem asks for the deterministic query complexity of finding a full king in an -vertex tournament. The established gap is between and .
Known results
- Shen, Sheng, and Wu (2003): full-king bounds and .
- Biswas, Jayapaul, Raman, and Satti: an -query algorithm finds a vertex controlling at least half the tournament.
- Lachish, Reidl, and Trehan (2022): this fraction improves to with queries.
November 2026 claimed improvement
Ismaili Alaoui, Lachish, and Mande report an -query algorithm finding a king controlling every fixed fraction below . This advances the partial-result frontier but does not determine the complexity of finding a full king; the claim is unverified in the retrieved material.
Current status (as of November 2026): the full deterministic problem remains open between and , while the reported improvement to every fixed fraction below is an unverified claim.
Solutions 0
No solutions have been posted yet.