Search Results

A king in a directed graph is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament (a complete graph where each edge has a direction) has at least one king. Our contributions in this work are: - We show that the query complexity of determining existence of a king in arbitrary n-vertex digraphs is Θ(n²). This is in stark contrast to the case where the input is a tournament, where Shen, Sheng, and Wu [SICOMP'03] showed that a king can be found in O(n^{3/2}) queries. - In an attempt to increase the "fairness" in the definition of tournament winners, Ho and Chang [IPL'03] defined a strong king to be a king k such that, for every v that dominates k, the number of length-2 paths from k to v is strictly larger than the number of length-2 paths from v to k. We show that the query complexity of finding a strong king in a tournament is Θ(n²). This answers a question of Biswas, Jayapaul, Raman, and Satti [DAM'22] in the negative. A key component in our proofs is the design of specific tournaments where every vertex is a king, and analyzing certain properties of these tournaments. We feel these constructions and properties are independently interesting and may lead to more interesting results about tournament solutions.