Searching for Sorted Sequences of Kings in Tournaments
Jian Shen, Sheng Li, Jie Wu · SIAM Journal on Computing · 2003
A tournamentT n is an orientation of a complete graph on n vertices. A king in a tournament is a vertex from which every other vertex is reachable by a path of length at most 2. A sorted sequence of kings in a tournament T n is an ordered list of its vertices u 1 , u 2 , . . ., u n such that u i dominates $u_{i+1}$ ($u_i \rightarrow u_{i+1}$) and $u_i$ is a king in the subtournament induced by $\{u_j: i \le j \le n\}$ for each i=1,2, . . .,n-1. In particular, if T n is transitive, searching for a sorted sequence of kings in T n is equivalent to sorting a set of n numbers. In this paper, we try to find a sorted sequence of kings in a general tournament by asking the following type of binary question: "What is the orientation of the edge between two specified vertices u, v?" The cost for finding a sorted sequence of kings is the minimum number of binary questions asked in order to guarantee the finding of a sorted sequence of kings. Using an adversary argument proposed in this paper, we showthat the cost for finding a sorted sequence of kings in T n is $\Theta(n^{3/2})$ in the worst case, thus settling the order of magnitude of this question. We also show that the cost for finding a king in T n is $\Omega(n^{4/3})$ and O(n 3/2 ) in the worst case. Finally, we show a connection between a sorted sequence of kings and a median order in a tournament.