A King for Almost Everyone
Abstract
A tournament is an orientation of a complete graph. A vertex v controls a vertex u≠ v if there is a directed path of length at most two from v to u, and a δ-king is one that controls at least δ(n−1) vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an Ω(n4/3) lower bound on the deterministic query complexity of finding a $1$-king, and a non-matching upper bound of O(n3/2). Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For δ-kings with δ< 1, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that O(n4/3) queries suffice to find a 1/2-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to 1/2+2/17 using Õ(n4/3) queries, and asked whether a larger fraction could be achieved within the same query bound. We answer this question affirmatively for every fixed fraction below one: for every fixed ε∈(0,1), we give a deterministic algorithm that finds a (1−ε)-king using O(n4/3) queries. The design of our algorithm is informed by a structural analysis combining a sparse regularity lemma due to Allen, Kohayakawa, Mota and Parente [Electronic Journal of Combinatorics'14] with a new sampling argument based on a reachability theorem of Afek, Gafni and Linial [arXiv'19].
Related
- Laplace--King representations: density and spectral theory
- Directed Cut-Query Complexity of Finding a King
- A Study of King-Type Operators Connecting Wavelet and Quantum Calculus: Numerical and Graphical Analysis
- On a conjecture of King-Tollu-Toumazet for rectangular Kostka coefficients
- Almost Homogeneity Characterizes Almost Bi-Lipschitz Euclidean Embeddability
BibTeX
@misc{alaoui2026king,
title = {{A King for Almost Everyone}},
author = {Ziad Ismaili Alaoui and Oded Lachish and Nikhil S. Mande},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03838},
eprint = {2611.03838},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03838},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A King for Almost Everyone
AU - Ziad Ismaili Alaoui
AU - Oded Lachish
AU - Nikhil S. Mande
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03838
UR - https://arxiv.org/abs/2611.03838
AB - A tournament is an orientation of a complete graph. A vertex v controls a vertex u≠ v if there is a directed path of length at most two from v to u, and a δ-king is one that controls at least δ(n−1) vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an Ω(n^4/3) lower bound on the deterministic query complexity of finding a $1$-king, and a non-matching upper bound of O(n^3/2). Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For δ-kings with δ< 1, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that O(n^4/3) queries suffice to find a 1/2-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to 1/2+2/17 using Õ(n^4/3) queries, and asked whether a larger fraction could be achieved within the same query bound. We answer this question affirmatively for every fixed fraction below one: for every fixed ε∈(0,1), we give a deterministic algorithm that finds a (1−ε)-king using O(n^4/3) queries. The design of our algorithm is informed by a structural analysis combining a sparse regularity lemma due to Allen, Kohayakawa, Mota and Parente [Electronic Journal of Combinatorics'14] with a new sampling argument based on a reachability theorem of Afek, Gafni and Linial [arXiv'19].
ER -