2026-07-22T11:19:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17417 2024-03-06T10:59:42Z ddc:004 open_access

When You Come at the King You Best Not Miss Lachish, Oded Reidl, Felix Trehan, Chhaya Digraphs tournaments kings query complexity A tournament is an orientation of a complete graph. We say that a vertex x in a tournament T controls another vertex y if there exists a directed path of length at most two from x to y. A vertex is called a king if it controls every vertex of the tournament. It is well known that every tournament has a king. We follow Shen, Sheng, and Wu [Jian Shen et al., 2003] in investigating the query complexity of finding a king, that is, the number of arcs in T one has to know in order to surely identify at least one vertex as a king. The aforementioned authors showed that one always has to query at least Ω(n^{4/3}) arcs and provided a strategy that queries at most O(n^{3/2}). While this upper bound has not yet been improved for the original problem, [Biswas et al., 2017] proved that with O(n^{4/3}) queries one can identify a semi-king, meaning a vertex which controls at least half of all vertices. Our contribution is a novel strategy which improves upon the number of controlled vertices: using O(n^{4/3} polylog n) queries, we can identify a (1/2+2/17)-king. To achieve this goal we use a novel structural result for tournaments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Oded Lachish and Felix Reidl and Chhaya Trehan 2022 Is Part Of LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2022.25 urn:nbn:de:0030-drops-174177 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode