{"id":"arxiv/2610.40521","url":"https://arxiv.org/abs/2610.40521","tags":["cs.CC","math.CO"],"score":0,"title":"Directed Cut-Query Complexity of Finding a King","domain":"cs.CC","source":"arxiv","authors":["Ziad Ismaili Alaoui","Oded Lachish","Nikhil S. Mande"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}