Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 50 min ago
PreprintCC BY 4.0arXiv

Directed Cut-Query Complexity of Finding a King

  • Ziad Ismaili Alaoui
  • Oded Lachish
  • Nikhil S. Mande
Open at sourcePDFDOICite

Abstract

A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is Θ(n) for n-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.

Related

  1. Exponential Deterministic Query Complexity of Goldstein Stationarity
    Yixi Ding, Ya-xiang Yuan
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  2. Entropy hypocoercivity and query complexity for the bouncy particle sampler
    Jianfeng Lu, Yinchen Luo
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  3. Windowed thinning and query complexity for the bouncy particle and Zigzag samplers
    Jianfeng Lu, Yinchen Luo
    arXivPreprintCC BY 4.0Full textNumerical analysis & scientific computingProbabilityarXiv
  4. On the Complexity of Finding Fixed Points for Set-Valued Contractions
    Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  5. Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
    Huanjian Zhou, Taiji Suzuki
    arXivPreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{alaoui2026directed,
  title = {{Directed Cut-Query Complexity of Finding a King}},
  author = {Ziad Ismaili Alaoui and Oded Lachish and Nikhil S. Mande},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.40521},
  eprint = {2610.40521},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.40521},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Directed Cut-Query Complexity of Finding a King
AU  - Ziad Ismaili Alaoui
AU  - Oded Lachish
AU  - Nikhil S. Mande
PY  - 2026
DA  - 2026/10/29
PB  - arXiv
DO  - 10.48550/arxiv.2610.40521
UR  - https://arxiv.org/abs/2610.40521
AB  - A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is Θ(n) for n-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.
ER  -