Chapter 30. Score Sets and Kings

The idea of comparison-based ranking has been discussed earlier in the chapter Comparison based ranking, where score sequence was introduced as a way of ranking vertices in a tournament. Oriented graphs are generalizations of tournaments. In fact, just like one can think of a tournament as expressing the results of a round-robin competition without ties (with vertices representing players and arrows pointing to the defeated players), one can think of an oriented graph as a round-robin competition with ties allowed (ties are represented by not drawing the corresponding arcs).

Figure 30.1. A round-robin competition involving 4 players.

A round-robin competition involving 4 players.


Figure 30.1 shows the results of a round-robin competition involving 4 players and , with (a) ties not allowed and (b) ties allowed. In the first instance there is always a winner and a loser whenever two players square off, while in the latter case player ties with player and player ties with player .

In 2009 Antal Iványi studied directed graphs, in which every pair of different vertices is connected with at least and at most arcs. He named them -tournaments or simply -tournament.

If , then the -tournaments are called -tournaments. In this chapter we deal first of all with -tournaments and -tournaments. -tournaments are in some sense equivalent with -tournaments. We use the simple notations 1-tournament , 2-tournament , -tournament . It is worth mentioning that is a classical tournament, while oriented graphs are -tournaments. If we allow loops then every directed graph is some -tournament (see the chapter Comparison Based Ranking of this book).

We discuss two concepts related with -tournaments, namely score sets and kings. A score set is just the set of different scores (out-degrees) of vertices, while a king is a dominant vertex. We shall study both concepts for 1-tournaments first and then extend these to the more general setting of oriented graphs.

Although we present algorithms for finding score sets and kings in -tournaments and -tournaments, much of the focus is on constructing tournaments with special properties such as having a prescribed score set or a fixed number of kings. Since players in a tournament are represented by vertices, we shall use the words player and vertex interchangeably throughout this chapter without affecting the meaning.

We adopt the standard notation to denote a tournament with vertex set and arc set . We denote the number of vertices by , and the out-degree matrix by , and the in-degree matrix by . Furthermore, we use the term -tournament and the notation to represent a tournament with vertices and exactly arcs between the elements of any pair of different vertices. In a similar way and denote a regular, resp. a null graph. When there is no ambiguity we omit one or even both indices and shall refer to the corresponding tournaments as , , and . The score sequences are denoted by , while the score sets as sets by and as sequences by .

In Section 30.1 the score sets of 1-tournaments are discussed, while Section 30.2 deals with the sore sets of oriented graphs. In Section 30.3 the conditions of the unique reconstruction of the score sets are considered at first for -tournaments, then in more details for 1-tournaments and 2-tournaments. In Section 30.4 and Section 30.5 results connected with different kings of tournaments are presented.

Some long and accessible proofs are omitted. In these cases the Reader can find the coordinates of the proof in Chapter notes and Bibliography.

30.1. 30.1 Score sets in 1-tournaments

In a round-robin competition with no ties allowed, what are the sets of nonnegative integers that can arise as scores of players? Note that here we are not interested in the scores of individual players (the score sequence), rather we are looking for the sets of nonnegative integers with each integer being the score of at least one player in the tournament. This question motivates the study of score sets of tournaments.

The set of different scores of vertices of a tournament is called the score set of the tournament. In other words, the score set is actually the score sequence of a tournament with repetitions removed. For example the tournament given in Figure 30.2 has score sequence , whereas the score set of this tournament is . Figure 30.3 shows the out-degree matrix of the tournament represented on Figure 30.2.

Figure 30.2.  A tournament with score set A tournament with score set \{0,2\} ..

A tournament with score set \{0,2\} .

Figure 30.3.  Out-degree matrix of the tournament represented in Figure 30.2.

Out-degree matrix of the tournament represented in Figure 30.2.

30.1.1. 30.1.1 Determining the score set

Determining the score set of a tournament is quite easy. The following algorithm Set1 takes the data of a tournament as input and returns the score set of .

The procedures of this chapter are written using RAM model of computations and pseudocode according to the third edition of the textbook Introduction to Algorithms published by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein in 2009.

Set1( )

  1     2  
                     FOR
                   all vertex    3       4    
                     FOR
                   all vertex    5       
                     IF
                   
                        
                  
                     //
                   is  an arc of ?   6             7    
                     IF
                   
                        
                  
                     //
                   is the found score new?   8          9  
                     RETURN
                   
                   
               

Since the scores of the vertices depend on out-degrees, any algorithm determining the score set requires time. Due to the embedded loops in lines 02–08 the running time of Set1 is even in the best case. The precise order of the running time depends among others on the implementation of the iF instruction in line 07. E.g., if line 07 is implemented by the sequential comparison of the actual score with the elements of , then the running time is for a score sequence containing different elements and is for a regular tournament.

Out-degree matrix is a useful data structure in the implementation of graph algorithms. The input data of the following algorithm Quick-Set1 are and , and the output is the score sequence a as a nonincreasingly ordered sequence and the score set as a decreasingly ordered sequence. Quick-Set1 calls the well-known sorting procedure Insertion-Sort .

Quick-Set1( )

  1  
                     FOR
                   
                   
                  
                     TO
                   
                     2       3    
                     FOR
                   
                  
                  
                     TO
                   
                     4             
                  
                     //
                   score sequence is computed   5     6  
                     Insertion-Sort(
                     
                     )
                        
                  
                     //
                   sorting of the score vector   7     8  
                     FOR
                   
                   
                  
                     TO
                   
                     9    
                     IF
                   
                    10         11         12  
                     RETURN
                   
                   
               

Since the embedded loops in lines 02–05 need time, and the remaining part of the code requires less, the running time of Quick-Set1 is in all cases.

30.1.2. 30.1.2 Tournaments with prescribed score set

Constructing a 1-tournament with a prescribed score set is more difficult than determining the score set of a 1-tournament with prescribed score sequence or with prescriben our-degree matrix. Quite surprisingly, if sufficiently many players participate in a tournament then any finite set of nonnegative integers can arise as a score set. This was conjectured by K. B. Reid in 1978 and turned out to be a relatively challenging problem.

Reid proved the result when , or , or if contains consecutive terms of an arithmetic or geometric progression. That is, Reid showed that any set of one, two or three nonnegative integers is a score set of some tournament and additionally, any set of the form for or for , is a score set of some tournament. Hager settled the cases and in 1986 and finally in 1987, T. Yao gave an existence proof of the general Reid's conjecture based on arithmetic analysis.

Theorem 30.1 (Yao, 1988) Every finite nonempty set of nonnegative integers is the score set of some tournament.

Let us try to formulate Reid's conjecture purely as a statement about numbers. Let be an increasing sequence of nonnegative integers. The conjecture means that there exist positive integers such that

is the score sequence of some 1-tournament with vertices. By Landau's theorem, , with , is the score sequence of some -tournament if and only if , for and . Thus it can be readily seen that Reid's conjecture is equivalent to the following statement.

For every nonempty set of nonnegative integers , where , there exist positive integers , such that

It is this equivalent formulation of Reid's conjecture that led to Yao's proof. The proof is not combinatorial in nature, but uses first of all some results of number theory. Commenting on Yao's proof Qiao Li wrote in 2006 in the Annals of New York Academy of Sciences:

Yao's proof is the first proof of the conjecture, but I do not think it is the last one. I hope a shorter and simpler new proof will be coming in the near future.

However, the prophecized constructive proof has not been discovered yet. This is in sharp contrast with Landau's theorem on score sequences, for which several proofs have emerged over the years. Recently, S. Pirzada and T. A. Naikoo gave a constructive combinatorial proof of a new special case of Reid's theorem. Their proof gives an algorithm for constructing a tournament with the prescribed score set, provided the score increments are increasing.

Theorem 30.2 (Pirzada and Naikoo, 2008) If are nonnegative integers with , then there exists a 1-tournament with score set

Figure 30.4.  Construction of tournament Construction of tournament T with odd number of distinct scores. with odd number of distinct scores.

Construction of tournament T with odd number of distinct scores.

Figure 30.5.  Construction of tournament Construction of tournament T with even number of distinct scores. with even number of distinct scores.

Construction of tournament T with even number of distinct scores.

Since any set of nonnegative integers can be written in the form of 30.3, the above theorem is applicable to all sets of nonnegative integers with increasing increments (i.e., .) The importance of Pirzada-Naikoo proof of Theorem 30.2 is augmented by the fact that Yao's original proof is not constructive and is not accessible to a broad audience.

Footnote. Yao's proof originally appeared in Chinese in the journal Kexue Tongbao. Later in 1989, the proof was published in English in the Chinese Science Bulletin. Unfortunately neither are accessible through the world wide web, although the English version is available to subscribers of the Chinese Science Bulletin. In Hungary this journal is accessible in the Library of Technical and Economical University of Budapest.

The following recursive algorithm is based on Pirzada and Naikoo's proof of Theorem 30.2. The algorithm takes the set of increments of the score set as input and returns a tournament whose score set is . Let for . Let denote the regular tournament on vertices and let denote the vertex and arc disjoint union of tournaments and .

Score-Reconstruction1( )

  1  
                     IF
                   
                   is odd   2    print 
                     Odd(
                     
                     )
                     3  
                     ELSE
                   print 
                     Even(
                     
                     )
                   
               

This algorithm calls one of the two following recursive procedures Odd and Even according to the parity of . The input of both algorithm is some prefix of the sequence of the increments , and the output is a tournament having the score set corresponding to the given increments.

Odd( )

  1  
                     IF
                   
                     2    
                     RETURN
                   
                     3  
                     ELSE
                   
                     4          5          6        = 
                     Odd(
                     
                     )
                     7          8        such that   9        dominates   10        dominates   11        dominates   12  
                     RETURN
                   
                   
               

We can remark that the tournament constructed by the first execution of line 03 of Odd contains the vertices whose score is , while the tournament constructed in line 04 contains the vertices whose score is in the tournament appearing as output. The vertices having smaller scores appear during the later execution of lines 03 and 04 with exception of the vertices having score since those vertices will be added to the output in line 02.

Even( )

  1     2     3   = 
                     Odd(
                     
                     )
                     4     5   such that  dominates    6  
                     RETURN
                   
                   
               

Since the algorithm is complicated, let's consider an example.

Example 30.1 Let and . Since is odd, Score-Reconstruction1 calls Odd in line 02 with parameters and .

The first step of Odd is the construction of in line 03. Denoting the vertices of this regular 5-tournament by and using the result of Exercise 30.1 we get the out-degree matrix shown in Figure 30.6.

Figure 30.6.  Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5}^{(3)} ..

Out-degree matrix of the tournament T_{5}^{(3)} .


The second step of Odd is the construction of . Let and be the vertices of this tournament.

The third step of Odd is the recursive call with parameters and . The fourth action of Odd is the construction of . Let and be the vertices of this tournament. The fifth step is the construction of . Let be the only vertex of this graph. The sixth action is the call of Odd with parameters and . Now the number of increments equals to 1, therefore the algorithm constructs in line 02.

The seventh step is the construction of in line 07, then the eighth step is adding new arcs (according to lines 08–11) to the actual constructed in line 07 and consisting from 3 regular tournaments having altogether 5 vertices . The result is shown in Figure 30.7.

Figure 30.7.  Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5}^{(3)} ..

Out-degree matrix of the tournament T_{5}^{(3)} .


Ninth step of Odd is joining the tournaments and to and the final step is adding of the domination arcs. The out-degree matrix of the output of Odd is shown in Figure 30.8.

Figure 30.8.  Out-degree matrix of the tournament Out-degree matrix of the tournament T_{5} ..

Out-degree matrix of the tournament T_{5} .


30.1.2.1.  Correctness of the algorithm

Let be a set of nonnegative integers with . Score-Reconstruction1 performs two types of recursions: first if is odd and the second if is even. Assume to be odd. For , the set contains one nonnegative integer and the algorithm returns the regular tournament as output. Note that each vertex of has score , so that score set of is . This shows that the algorithm is correct for .

If , then the set of increments consists of three nonnegative integers with . Now , therefore , so that as . Let be a regular tournament having vertices. Then each vertex of has score .

Again, since , therefore , so that . Let be a regular tournament having vertices. Then each vertex of has score . Also since , let be a regular tournament having vertices. Then each vertex of has score .

If , Score-Reconstruction1 outputs a tournament whose vertex set is the disjoint union of vertex sets of , and and whose arc set contains all the arcs of , and such that every vertex of dominates each vertex of , and every vertex of dominates each vertex of and . Thus has vertices with score set

This shows that the algorithm is correct for too. When the set of increments consists of an odd number of nonnegative integers, the algorithm recursively builds the required tournament by using the procedure Odd . To see this, assume that the algorithm works for all odd numbers upto . That is, if are nonnegative integers with , then the algorithm outputs a tournament having vertices with score set . Let us call this tournament .

We now show how the algorithm constructs a tournament with vertices with score set , where are nonnegative integers with .

Since therefore , , , , so that , that is, .

The procedure Odd constructs as a regular tournament having vertices. Each vertex of has score

Again, , therefore , so that as .

The procedure Odd constructs as a regular tournament having vertices. Each vertex of has score

Now Score-Reconstruction1 sets and adds additional arcs in such a way that every vertex of dominates each vertex of , and every vertex of dominates each vertex of and . Therefore is a tournament having

vertices with score set

Hence by induction, the algorithm is correct for all odd .

To prove the correctness for even case, note that if is odd, then is even. Let be nonnegative integers with . Therefore , where is odd. The procedure Even uses the procedure Odd to generate a tournament having vertices with score set .

Also, since , , the procedure Even generates a regular tournament having vertices such that the score for each vertex is .

Finally the algorithm generates the tournament and adds additional arcs so that every vertex of dominates each vertex of . The resulting tournament consists of

vertices and has score set

This shows that the algorithm is correct for even as well.

30.1.2.2.  Computational complexity

The running time of Score-Reconstruction1 depends on the size of the score set as well as the largest increment . The details are left as an exercise for the Reader (see Exercise 30.1-1).

Exercises

30.1-1 The out-degree matrix of a tournament is defined as a matrix with entry equal to 1 if player defeats player and 0 otherwise (see (30.16)). A tournament is completely determined by its out-degree matrix. Write an algorithm to generate the out-degree matrix of a regular tournament on vertices, where is any odd positive integer. Hint. Circularly place ones in each row.

30.1-2 Use Exercise 30.1-1 and the discussion in this section to determine the worst-case running time of Score-Reconstruction1 .

30.1-3 Obtain the out-degree matrix of a tournament with score set . How many vertices does this tournament have? Draw this tournament and give its outdegree-matrix.

30.1-4 Use the tournament obtained in Exercise 30.1-3 to generate the out-degree matrix of a 1-tournament with score set . Write the score sequence of your tournament.