Sociologists are often interested in determining the most dominant actors in a social network. Moreover, dominance in animal societies is an important theme in ecology and population biology. Social networks are generally modelled as digraphs with vertices representing actors and arcs representing dominance relations among actors. The concept of “king” is very closely related to dominance in digraphs. Kings and serfs were initially introduced to study dominance in round-robin competitions. These concepts were latter extended to more general families of digraphs such as multipartite tournaments, quasi-transitive digraphs, semicomplete multipartite digraphs and oriented graphs. In this section our focus will be on algorithmic aspects of kings and serfs in tournaments and their applications in majority preference voting.
A king in a tournament dominates every other vertex either directly or through another vertex. To make the idea more formal we define a path of length from a vertex to a vertex in a tournament (or any digraph) as a sequence of arcs where is the initial vertex of , is the terminal vertex of and the terminal vertex of is the same as the initial vertex of , for all . If there is a path of length 1 or 2 from a vertex to a vertex , then is said to be reachable from within two steps. Analogously, if there is a path of length or from to then is said to be reachable from within steps. Let be an -tournament. A vertex in is called an r-king, where , if every other vertex in the tournament is reachable within steps from . A vertex is called an r-serf if is reachable within if is reachable within steps from every other vertex in , In particular, a 2-king is simply called a king and a 2-serf is called a serf.
Figure 30.10. A tournament with three kings and three serfs . Note that is neither a king nor a serf and are both kings and serfs.
S. B. Maurer introduced the dual terms of king and serf in a delightful exposition of a tournament model for dominance in flocks of chicken. In his influential series of papers on dominance in animal societies, H. G. Landau proved that every tournament has a king (although he did not use the word king). In fact, he showed the following.
The proof is quite intuitive. Suppose to the contrary that is a vertex with maximum score in a tournament and is not a king. Then there exists another vertex in such that is not reachable from within 2 steps. But this means that and all out-neighbours of are reachable from in 1 step and so , a contradiction. Another classical result by J. W. Moon states that
It is natural to ask if the bound on the number of kings given in Theorem 30.17 is tight. The answer is yes, as demonstrated by the following example.
Example 30.2 Let be a tournament with vertex set . Let us denote by , an arc directed from to . Suppose that the arc set of consists of the arcs , , all arcs of the form , with and all arcs of the form with . Then it can be easily verified (Exercise 30.4-2) that has no transmitters and , and are the only kings in .
K. B. Reid proved the existence of a tournament with an arbitrary number of vertices and an arbitrary number of kings, with few exceptions.
Hence no tournament has exactly two kings. The above theorems can be stated just as well in terms of serfs. To see this, note that the converse of a tournament , obtained by reversing the arcs of , is also a tournament and that the kings and serfs of and are interchanged.
The king set of a tournament consists of all kings in the tournament. We can define the serf set analogously. The problem of determining the king set of a tournament is very important both for theoretical and practical considerations. In voting theory literature, political scientists often refer to the uncovered set in majority preference voting. This uncovered set is actually the king set for the tournament whose vertices consist of the candidates to be elected and arcs represent the outcomes of the two-way race between candidates. Here we present a simple polynomial time algorithm for determining the king set of a tournament. Given an -tournament , let us define an matrix as
We call , the out-degree matrix of . When there is no danger of ambiguity we will drop the subscript and simply denote the out-degree matrix by .
takes a tournament as input, calculates the out-degree matrix of and uses it to generate the king set of . Let be the zero matrix and let be the identity matrix.
1 2 3
IF6 7 8 9 dominates 9
The algorithm works on the same principle as the algorithm for finding the number of paths, from one vertex to another, in a digraph (Exercise 30.4-1 asks you to derive this algorithm). The entry of the matrix is equal to the number of paths of length two from vertex to vertex (check this!). Therefore, the entry of matrix counts the number of paths of length one or two from to ; and if vertex is a king, all entries in the row of must be non-zero.
The computational complexity of Algorithm
depends on the way is computed. If naive matrix multiplication is used, the algorithm runs in time. However, using the fast matrix multiplication by Coppersmith and Winograd, the running time can be reduced to . The Reader should note that by using the duality of kings and serfs,
can be adapted for finding the serf set of a tournament.
Kings frequently arise in political science literature. A majority preference voting procedure asks each voter to rank candidates in order of preference. The results can be modeled by a tournament where vertices represent the candidates and arcs point toward the loser of each two way race, where candidate defeats candidate if some majority of voters prefer to . Political scientists are often interested in determining uncovered vertices in the resulting tournament. A vertex is said to cover another vertex if defeats and also defeats every vertex that defeats. The covering relation is clearly transitive and has maximal elements, called uncovered vertices. An uncovered vertex has the strategically important property that defeats any other vertex in no more than two steps, i.e., either
there is some third alternative such that defeats and defeats .
Thus an uncovered vertex is actually a king. In fact the uncovered set, consisting of all uncovered vertices, is precisely the set of all kings (see Exercise 30.4-8).
The idea behind finding kings in a tournament can be easily extended to finding -kings for any positive integer .
1 2 3
IF6 7 8 9
The above algorithm runs in if the matrix multiplications are performed naively, and in time if fast matrix multiplication is incorporated.
As we have seen, kings dominate in tournaments. However, there exists a stronger notion of dominance in tournaments in the form of strong kings. Let us write to denote that defeats in a tournament , or in other words is an arc of . If and are disjoint subsets of vertices of then we write to denote that all vertices in defeat all vertices in . We define , where denotes the vertex set of . Let . When no ambiguity arises, we drop the subscript from the notation.
A vertex in a tournament is said to be a strong king if or for every other vertex of .
Note that is the number of paths of length two through which is reachable from . Therefore, , where is the out-degree matrix of .
Obviously, it is not true that every king is a strong king. For example, Figure 30.11 demonstrates a tournament with three kings, namely , and . However, only and are strong kings as . Figure 30.11 also shows that when searching for the most dominant vertex in real life applications, a king may not be the best choice (vertex is a king, but it defeats only one vertex and is defeated by all other vertices). Therefore, choosing a strong king is a better option. This intuition is further confirmed by the fact that, in the probabilistic sense it can be shown that in almost all tournaments every vertex is a king.
We have already shown that every tournament has a king. We now prove that every tournament has a strong king.
Then and . This implies that , a contradiction.
The problem of finding strong kings is no harder than finding kings in tournaments. Like
, we present a polynomial time algorithm for finding all strong kings in a tournament using the out-degree matrix .
1 2 3
IF6 7 8 9
has the same order of running time
So far we have been focusing on finding certain type of dominant vertices (like kings and strong kings) in a tournament. Another very important problem is to construct tournaments with a certain number of dominant vertices. Maurer posed the problem of determining all 4-tuples for which there exists a tournament on vertices with exactly kings and serfs such that of the kings are also serfs. Such a tournament is called an -tournament. For example the tournament given in Figure 30.11 is a -tournament. Reid gave the following characterization of such 4-tuples.
either or and ,
is none of , , or .
However, the corresponding problem for strong kings has been considered only recently. For , a tournament on vertices is called an -tournament if it has exactly strong kings. The construction of - tournaments follows from the results proved by Chen, Chang, Cheng and Wang in 2004. The results imply the existence of -tournaments for all satisfying
takes positive integers and as input satisfying the constraints (26.2) and (26.3) and outputs an -tournament and the set of its strong kings. Also for any vertex of a tournament , we adopt the notation of Chen et al. in letting (respectively, ) denote the set of vertices reachable from in one step (respectively, set of vertices from which is reachable in one step). Note that and are often referred to as the first out-neighbourhood and first in-neighbourhood of respectively.
1 3 null digraph on verices 4
IFis odd 5 6 7
TO9 10 11
IFis even 12 13 14 15 choose arbitrarily 16 17 18 19 20 21
TO23 24 25
The algorithm consists of performing two separate inductions to generate an -tournament, one for odd and one for even . If is odd then we start by letting , the regular tournament on vertices (which always exists for odd ), and inductively add vertices to that are defeated by all the vertices of . Thus the resulting tournament has vertices and kings (the vertices of ). The construction for even is a bit more involved. We start with . Note that every vertex of has score . We then add three vertices , and and several arcs to such that for a fixed existing vertex of .
The resulting tournament (illustrated in Figure 30.12) has vertices with scores , , and , for all vertices of . Now by Theorem 30.19 all vertices of and the new vertex are strong kings of , while and are not (Exercise 30.4-9). Thus is a -tournament that can now be extended to an -tournament by adding more vertices that are defeated by all the existing vertices of (just like in the case of odd ).
runs in quadratic time as it takes operations to construct a regular tournament and the remaining steps in the algorithm are completed in linear time.
30.4-1 The out-degree matrix of an -vertex oriented graph is an matrix whose entry is given by . Describe an algorithm based on the out-degree matrix for finding the number of paths of length between any two vertices of the graph.
30.4-2 Draw the tournament discussed in Example 30.2 and show that it has no transmitters and exactly three kings.
30.4-3 Using the 5-tournament in Example 30.2 give the construction of an -tournament with no transmitters and exactly three kings.
(or simply a king) if there is a directed path of length 4 from to every other vertex of the tournament.
Footnote. Several bipartite and multipartite tournaments have no 2-king or 3-king. However, a multipartite tournament with at least one vertex of in-degree zero contains a 4-king. Therefore it is logical to look for 4-kings in a multipartite tournament.
Derive an algorithm to obtain all 4-kings in a bipartite tournament and compare its complexity with the complexity of -
for finding -kings in ordinary tournaments.
30.4-7 As the name suggests a multipartite tournament is an orientation of a complete multipartite graph. Extend the algorithm obtained in Exercise 30.4-6 to find all 4-kings in multipartite tournaments. Again compare the performance of your algorithms with -