From Donkeys to Kings in Tournaments

Amir Abboud; Tomer Grossman; Moni Naor; Tomer Solomon

doi:10.4230/LIPIcs.ESA.2024.3

From Donkeys to Kings in Tournaments

Amir Abboud^*, Tomer Grossman^*, Moni Naor^*, Tomer Solomon^*

^*Corresponding author for this work

Department of Computer Science and Applied Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

10 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	32nd Annual European Symposium on Algorithms, ESA 2024
Editors	Timothy Chan, Johannes Fischer, John Iacono, Grzegorz Herman
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages	14
ISBN (Electronic)	9783959773386
DOIs	https://doi.org/10.4230/LIPIcs.ESA.2024.3
Publication status	Published - 23 Sept 2024
Event	32nd Annual European Symposium on Algorithms, ESA 2024 - London, United Kingdom Duration: 2 Sept 2024 → 4 Sept 2024

Publication series

Series	Leibniz International Proceedings in Informatics, LIPIcs
Volume	308
ISSN	1868-8969

Conference

Conference	32nd Annual European Symposium on Algorithms, ESA 2024
Country/Territory	United Kingdom
City	London
Period	2/9/24 → 4/9/24

Funding

Amir Abboud: This work is part of the project CONJEXITY, which has received funding from the European Research Council (ERC) under the European Union’s Horizon Europe research and innovation program (grant agreement No. 101078482). Supported by an Alon scholarship and a research grant from the Center for New Scientists at the Weizmann Institute of Science. Moni Naor: Incumbent of the Judith Kleeman Professorial Chair. Supported in part by grants from the Israel Science Foundation (no.2686/20), by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and by the Israeli Council for Higher Education (CHE) via the Weizmann Data Science Research Center. Tomer Solomon: This material is based upon work supported by DARPA under Agreement No. HR00110C0086. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.4230/LIPIcs.ESA.2024.3Licence: CC BY

aa_ESA2024_FromDonkeystoKings_PV2024Final published version, 868 KBLicence: CC BY

Cite this

Abboud, Amir ; Grossman, Tomer ; Naor, Moni et al. / From Donkeys to Kings in Tournaments. 32nd Annual European Symposium on Algorithms, ESA 2024. editor / Timothy Chan ; Johannes Fischer ; John Iacono ; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 308).

@inproceedings{a6077ac559c74aa884fd2713556fce85,

title = "From Donkeys to Kings in Tournaments",

abstract = "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(n3/2) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n2) 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(kn2), 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.",

author = "Amir Abboud and Tomer Grossman and Moni Naor and Tomer Solomon",

note = "Publisher Copyright: {\textcopyright} Amir Abboud, Tomer Grossman, Moni Naor, and Tomer Solomon; licensed under Creative Commons License CC-BY 4.0.; 32nd Annual European Symposium on Algorithms, ESA 2024 ; Conference date: 02-09-2024 Through 04-09-2024",

year = "2024",

month = sep,

day = "23",

doi = "10.4230/LIPIcs.ESA.2024.3",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Timothy Chan and Johannes Fischer and John Iacono and Grzegorz Herman",

booktitle = "32nd Annual European Symposium on Algorithms, ESA 2024",

address = "Germany",

}

Abboud, A , Grossman, T , Naor, M & Solomon, T 2024, From Donkeys to Kings in Tournaments. in T Chan, J Fischer, J Iacono & G Herman (eds), 32nd Annual European Symposium on Algorithms, ESA 2024., 3, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 308, 32nd Annual European Symposium on Algorithms, ESA 2024, London, United Kingdom, 2/9/24. https://doi.org/10.4230/LIPIcs.ESA.2024.3

From Donkeys to Kings in Tournaments. / Abboud, Amir ; Grossman, Tomer ; Naor, Moni et al.
32nd Annual European Symposium on Algorithms, ESA 2024. ed. / Timothy Chan; Johannes Fischer; John Iacono; Grzegorz Herman. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. 3 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 308).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - From Donkeys to Kings in Tournaments

AU - Abboud, Amir

AU - Grossman, Tomer

AU - Naor, Moni

AU - Solomon, Tomer

N1 - Publisher Copyright: © Amir Abboud, Tomer Grossman, Moni Naor, and Tomer Solomon; licensed under Creative Commons License CC-BY 4.0.

PY - 2024/9/23

Y1 - 2024/9/23

N2 - 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(n3/2) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n2) 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(kn2), 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.

AB - 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(n3/2) queries). On the other hand, we show that finding k ≥ 4 kings requires Ω(n2) 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(kn2), 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.

UR - http://www.scopus.com/inward/record.url?scp=85205662813&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ESA.2024.3

DO - 10.4230/LIPIcs.ESA.2024.3

M3 - Conference contribution

AN - SCOPUS:85205662813

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 32nd Annual European Symposium on Algorithms, ESA 2024

A2 - Chan, Timothy

A2 - Fischer, Johannes

A2 - Iacono, John

A2 - Herman, Grzegorz

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 32nd Annual European Symposium on Algorithms, ESA 2024

Y2 - 2 September 2024 through 4 September 2024

ER -

Abboud A , Grossman T , Naor M, Solomon T. From Donkeys to Kings in Tournaments. In Chan T, Fischer J, Iacono J, Herman G, editors, 32nd Annual European Symposium on Algorithms, ESA 2024. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2024. 3. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 308). doi: 10.4230/LIPIcs.ESA.2024.3

From Donkeys to Kings in Tournaments

Abstract

Publication series

Conference

Funding

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this