论文标题
当你来到国王时，最好不要错过
When you come at the kings you best not miss
论文作者
论文摘要
比赛是完整图的方向。 我们说，如果存在$ x $ y $的顶点$ x $，则如果存在有指向的长度途径，则最多有两条$ x $ y $，从$ x $到$ y $。 如果顶点控制比赛的每个顶点，则称为国王。众所周知，每个锦标赛都有国王。 我们遵循沉，Sheng和Wu（Siam J. Comput。，2003年），调查了寻找国王的查询复杂性，即$ \ vec t $中的弧线数，必须知道，以肯定至少将一个顶点识别为国王。 前面提到的作者表明，人们总是必须查询至少$ω（n^{4/3}）$ arcs，并提供了一种最多查询$ o（n^{3/2}）$的策略。尽管对于原始问题尚未改善此上限，但 Biswas等。 （算法中的前沿，2017年）证明，使用$ o（n^{4/3}）$查询一个人可以识别半键，这意味着一个顶点，它控制了所有顶点的至少一半。 我们的贡献是一种新的策略，可以改善受控顶点的数量：使用$ o（n^{4/3} \ operatorName {polylog} n）$ queries，我们可以识别$（\ frac {1} {1} {2} {2}+\ frac {2} {2} {17} {17} {17} {17} {17} {17} {17}）$ - king。 为了实现这一目标，我们为比赛使用新颖的结构结果。
A tournament is an orientation of a complete graph. We say that a vertex $x$ in a tournament $\vec 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 (SIAM J. Comput., 2003) in investigating the query complexity of finding a king, that is, the number of arcs in $\vec 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. (Frontiers in Algorithmics, 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} \operatorname{polylog} n)$ queries, we can identify a $(\frac{1}{2}+\frac{2}{17})$-king. To achieve this goal we use a novel structural result for tournaments.
