← All problems

Deterministic query complexity of finding kings in tournaments

Given oracle access to an unknown tournament TT on nn vertices, where one query reveals the orientation of a selected edge, determine the deterministic query complexity Q(n)Q(n) of finding a vertex vv such that, for every vertex u≠vu\neq v, there is a directed path from vv to uu of length at most 22. Equivalently, determine the asymptotic complexity of finding a 11-king. The known bounds are Ω(n4/3)≤Q(n)≤O(n3/2)\Omega(n^{4/3})\le Q(n)\le O(n^{3/2}); in particular, it remains open whether Q(n)=O(n4/3)Q(n)=O(n^{4/3}).

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 nn-vertex tournament. The established gap is between Ω(n4/3)\Omega(n^{4/3}) and O(n3/2)O(n^{3/2}).

Known results

  • Shen, Sheng, and Wu (2003): full-king bounds Ω(n4/3)\Omega(n^{4/3}) and O(n3/2)O(n^{3/2}).
  • Biswas, Jayapaul, Raman, and Satti: an O(n4/3)O(n^{4/3})-query algorithm finds a vertex controlling at least half the tournament.
  • Lachish, Reidl, and Trehan (2022): this fraction improves to 12+217\frac{1}{2}+\frac{2}{17} with O(n4/3polylog⁡n)O(n^{4/3}\operatorname{polylog} n) queries.

November 2026 claimed improvement

Ismaili Alaoui, Lachish, and Mande report an O(n4/3)O(n^{4/3})-query algorithm finding a king controlling every fixed fraction below 11. 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 Ω(n4/3)\Omega(n^{4/3}) and O(n3/2)O(n^{3/2}), while the reported improvement to every fixed fraction below 11 is an unverified claim.

Sources

Solutions 0

No solutions have been posted yet.