2026-07-26T17:23:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25085 2026-02-09T08:06:23Z ddc:004 open_access

Hardness of Finding Kings and Strong Kings Ismaili Alaoui, Ziad Mande, Nikhil Tournaments kings query complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ziad Ismaili Alaoui and Nikhil Mande 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.36 urn:nbn:de:0030-drops-250856 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode