寻找“国王”的有向割查询复杂度
Directed Cut-Query Complexity of Finding a King
Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
AI 速览：作者在割查询模型下证明，确定性寻找锦标赛中“国王”的查询复杂度为 Θ(n)。
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.