Searching for sorted sequences of kings in tournaments
A tournament T-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) --> u(i+1)) and u(i) is a king in the subtournament induced by {u(j) : i less than or equal to j less than or equal to 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 show that 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.
sorted sequence of kings king tournament adversary argument divide-and-conquer algorithm recursive relation