Hardness of Finding Kings and Strong Kings

Ziad Ismaili Alaoui, Nikhil S. Mande · 2025

Read Hardness of Finding Kings and Strong Kings by Ziad Ismaili Alaoui, Nikhil S. Mande (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19386.txt.

Introduction

Ziad Ismaili Alaoui and Nikhil S. Mande study a puzzle about winners in directed graphs in a 2025 theory paper. A king is a point that can reach every other point in at most two steps. It is well known that round-robin contests, where each pair has one directed edge, always hold at least one king. The pair ask how many edge checks are needed to find one in wider graph classes.

For general directed graphs, they show the check count must grow with the square of the size, so no fast shortcut exists. They prove the same hard limit for a stricter winner type, the strong king, even inside round-robin contests. That result settles an open question from earlier work in the negative. Their graph designs may help future work on contest winners.

Catalog record

CREATORZiad Ismaili Alaoui, Nikhil S. Mande
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-19386

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Hardness of Finding Kings and Strong Kings Ziad Ismaili Alaoui, Nikhil S. Mande Abstract A king in a directed graph is a vertex v v such that every other vertex is reachable from v v via a path of length at most 2 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 n -vertex digraphs is Θ ⁡ ( n 2 ) \Theta(n^{2}) . 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 ) 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 k such that, for every v v that dominates k k , the number of length- 2 2 paths from k k to v v is strictly larger than the number of length- 2 2 paths from v v to k k . We show that the query complexity of finding a strong king in a tournament is Θ ⁡ ( n 2 ) \Theta(n^{2}) . 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. 1 Introduction A tournament is a complete directed graph. Motivated to find a reasonable notion of a “most-dominant chicken” in a flock of chickens (where the “pecking order” is represented as a tournament), Landau [ Lan53 ] introduced the notion of a king in a tournament. A king in a tournament is a vertex k such that for every other vertex v , either there is an edge from k to v , or there exists a u such that there are edges from k to u and from u to v . That is, a king is a vertex such that every other vertex is reachable from it via a path of length at most 2. The notion of a king is a natural generalisation of that of a source: a vertex is a source if every other vertex is reachable from it via a path of length 1. While it is easy to see that a tournament need not have a source, it is also not hard to show that every tournament has at least one king [ Lan53 , Mau80 ] . Soon after Maurer’s popular science article about kings in tournaments [ Mau80 ] , Reid [ Rei82 ] showed existence of tournaments in which every vertex is a king. Tournament solutions/winners are also a natural object of study in social choice theory. See, for instance, [ Dey17 ] and the references therein. The monograph by Moon [ Moo15 ] sparked a line of research on tournaments, their solutions, and their structural properties. A natural computational model to study the complexity of finding tournament solutions and related problems is that of query complexity . In this setting, an algorithm has access to the input in the form of queries : in one step an algorithm may query the direction of the edge between a pair of vertices of its choosing (in case of an undirected graph problem, the algorithm may query the presence/absence of an edge between a pair of vertices of its choosing). The algorithm’s goal is to minimise the number of queries made in the worst case, and all other operations are treated as free. There is a rich literature on the study of graph problems in the setting of query complexity, see, for example, [ Ros73 , RV76 , Yao87 , Haj91 , CK01 , Dey17 , MPS23 ] and the references therein. The focus of this paper is on finding a king in a digraph. Given that every tournament has a king as mentioned earlier, it is natural to ask: how efficiently can a king in an n -vertex tournament be found? The study of this question was initiated by Shen, Sheng, and Wu [ SSW03 ] , who exhibited an algorithm with query complexity O(n^{3/2}) , and they also showed a non-matching lower bound of \Omega(n^{4/3}) . To date, these are the best known bounds on the complexity of finding a king in a tournament, and closing the gap remains an intriguing open problem. There have been some very recent works showing better query bounds for variants of the task of finding a king, or studying the complexity of finding kings in models other than deterministic query complexity [ BJRS22 , LRT22 , MPS23 , MPSS24 , AGNS24 ] . Our first main contribution in this paper to show that if we allow for non-tournament inputs, then the query complexity of even determining existence of a king shoots up. Theorem 1.1 . The randomized query complexity of determining existence of a king in an n -vertex digraph is \Theta(n^{2}) . Relevant to our work is the notion of a strong king in a tournament. This notion was defined by Ho and Chang [ HC03 ] in an attempt to increase the “fairness” of the notion of a winner in a tournament. Let \delta(u,v) denote the number of length-2 paths from u to v . A king k is said to be strong if for all w with w\rightarrow k , we have \delta(k,w)>\delta(w,k) . To see why this notion increases the fairness of the definition of a winner, consider the following scenario: say we have a tournament in which a vertex k has a single out-neighbour u , and all other vertices are in-neighbours of k . Further suppose every vertex other than k and u is an out-neighbour of u . The vertex k is a king in this tournament, but not necessarily a “fair” one, since it “defeats” only one vertex. However, it is not hard to see that k is not a strong king. The study of strong kings in tournaments has also gained some attention [ CCCW08 , MDR20 ] . Biswas et al. [ BJRS22 , Section 7] asked if one could devise an algorithm to find a strong king in an n -vertex tournament with cost o(n^{2}) . Our second main contribution in this paper is to answer this in the negative. Theorem 1.2 . The randomized query complexity of finding a strong king in an n -vertex tournament is \Theta(n^{2}) . 1.1 Organization of the Paper In Section 2 , we review basic preliminaries and formalize the computational questions and models of interest. In Section 3 , we recall two known constructions of tournaments where every vertex is a king. In Section 4 , we show certain properties of these constructions and use these properties to conclude our main results, Theorem 1.1 and Theorem 1.2

Read the complete text