License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.25
URN: urn:nbn:de:0030-drops-174177
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17417/
Lachish, Oded ;
Reidl, Felix ;
Trehan, Chhaya
When You Come at the King You Best Not Miss
Abstract
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.
BibTeX - Entry
@InProceedings{lachish_et_al:LIPIcs.FSTTCS.2022.25,
author = {Lachish, Oded and Reidl, Felix and Trehan, Chhaya},
title = {{When You Come at the King You Best Not Miss}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {25:1--25:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-261-7},
ISSN = {1868-8969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17417},
URN = {urn:nbn:de:0030-drops-174177},
doi = {10.4230/LIPIcs.FSTTCS.2022.25},
annote = {Keywords: Digraphs, tournaments, kings, query complexity}
}
|
Keywords: |
|
Digraphs, tournaments, kings, query complexity |
|
Collection: |
|
42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
