From Donkeys to Kings in Tournaments
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914971633319936 |
|---|---|
| author | Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer |
| author_facet | Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer |
| contents | A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a \emph{king}. We study the complexity of finding $k$ kings in a tournament graph.
We show that the randomized query complexity of finding $k \le 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 \ge 4$ kings requires $Ω(n^2)$ queries, even in the randomized case.
We consider the RAM model for $k \geq 4$. We show an algorithm that finds $k$ kings in time $O(kn^2)$, which is optimal for constant values of $k$. Alternatively, one can also find $k \ge 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_10475 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | From Donkeys to Kings in Tournaments Abboud, Amir Grossman, Tomer Naor, Moni Solomon, Tomer Data Structures and Algorithms Computational Complexity A tournament is an orientation of a complete graph. A vertex that can reach every other vertex within two steps is called a \emph{king}. We study the complexity of finding $k$ kings in a tournament graph. We show that the randomized query complexity of finding $k \le 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 \ge 4$ kings requires $Ω(n^2)$ queries, even in the randomized case. We consider the RAM model for $k \geq 4$. We show an algorithm that finds $k$ kings in time $O(kn^2)$, which is optimal for constant values of $k$. Alternatively, one can also find $k \ge 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. |
| title | From Donkeys to Kings in Tournaments |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2410.10475 |