On the Communication Complexity of Finding a King in a Tournament

Mande, Nikhil S ORCID: 0000-0002-9520-7340, Paraashar, Manaswi, Sanyal, Swagato and Saurabh, Nitin (2024) On the Communication Complexity of Finding a King in a Tournament In: RANDOM 2024, 2024-8-28 - 2024-8-30, London.

Text REF_MPSS_RANDOM24.pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (719kB) | Preview

Abstract

A tournament is a complete directed graph. A source in a tournament is a vertex that has no in-neighbours (every other vertex is reachable from it via a path of length 1), and a king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known that every tournament has at least one king. In particular, a maximum out-degree vertex is a king. The tasks of finding a king and a maximum out-degree vertex in a tournament has been relatively well studied in the context of query complexity. We study the communication complexity of finding a king, of finding a maximum out-degree vertex, and of finding a source (if it exists) in a tournament, where the edges are partitioned between two players. The following are our main results for n-vertex tournaments: We show that the communication task of finding a source in a tournament is equivalent to the well-studied Clique vs. Independent Set (CIS) problem on undirected graphs. As a result, known bounds on the communication complexity of CIS [Yannakakis, JCSS’91, Göös, Pitassi, Watson, SICOMP’18] imply a bound of Θ(log ^{e 2} n) for finding a source (if it exists, or outputting that there is no source) in a tournament. The deterministic and randomized communication complexities of finding a king are Θ(n). The quantum communication complexity of finding a king is Θ(^{e √}n). The deterministic, randomized, and quantum communication complexities of finding a maximum out-degree vertex are Θ(n log n), Θ(^e n) and Θ(^{e √}n), respectively. Our upper bounds above hold for all partitions of edges, and the lower bounds for a specific partition of the edges. One of our lower bounds uses a fooling-set based argument, and all our other lower bounds follow from carefully-constructed reductions from Set-Disjointness. An interesting point to note here is that while the deterministic query complexity of finding a king has been open for over two decades [Shen, Sheng, Wu, SICOMP’03], we are able to essentially resolve the complexity of this problem in a model (communication complexity) that is usually harder to analyze than query complexity.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Communication complexity, tournaments, query complexity
Depositing User:	Symplectic Admin
Date Deposited:	06 Sep 2024 07:46
Last Modified:	23 May 2026 08:58
DOI:	10.4230/LIPIcs.APPROX/RANDOM.2024.64
Related Websites:	Author
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3183005
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.