2026-07-20T12:07:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21074 2024-09-23T09:13:15Z ddc:004 open_access

From Donkeys to Kings in Tournaments Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer Tournament Graphs Kings Query Complexity Fine Grained Complexity A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a king. We study the complexity of finding k kings in a tournament graph. We show that the randomized query complexity of finding k ≤ 3 kings is O(n), and for the deterministic case it takes the same amount of queries (up to a constant) as finding a single king (the best known deterministic algorithm makes O(n^{3/2}) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n²) queries, even in the randomized case. We consider the RAM model for k ≥ 4. We show an algorithm that finds k kings in time O(kn²), which is optimal for constant values of k. Alternatively, one can also find k ≥ 4 kings in time n^{ω} (the time for matrix multiplication). We provide evidence that this is optimal for large k by suggesting a fine-grained reduction from a variant of the triangle detection problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and Tomer Grossman and Moni Naor and Tomer Solomon 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.3 urn:nbn:de:0030-drops-210740 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode