2026-07-20T11:56:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19403 2024-03-06T11:03:57Z ddc:004 open_access

Randomized and Quantum Query Complexities of Finding a King in a Tournament Mande, Nikhil S. Paraashar, Manaswi Saurabh, Nitin Query complexity quantum computing randomized query complexity tournament solutions search problems A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of length at most 2. All such vertices v are called kings of the underlying tournament. Despite active recent research in the area, the best-known upper and lower bounds on the deterministic query complexity (with query access to directions of edges) of finding a king in a tournament on n vertices are from over 20 years ago, and the bounds do not match: the best-known lower bound is Ω(n^{4/3}) and the best-known upper bound is O(n^{3/2}) [Shen, Sheng, Wu, SICOMP'03]. Our contribution is to show tight bounds (up to logarithmic factors) of Θ̃(n) and Θ̃(√n) in the randomized and quantum query models, respectively. We also study the randomized and quantum query complexities of finding a maximum out-degree vertex in a tournament. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil S. Mande and Manaswi Paraashar and Nitin Saurabh 2023 Is Part Of LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2023.30 urn:nbn:de:0030-drops-194039 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.30 eng https://creativecommons.org/licenses/by/4.0/legalcode