A polytomial-time algorithm for recognizing the score-vectors of C-tournaments

Allan B. Cruse
Mathematics Department
University of San Francisco
February 2014

Terminology and background

For an upper-triangular matrix C = (cij) of nonnegative integers having size n-by-n, a C-tournament is a directed multigraph with n nodes whose adjacency-matrix T = (tij) obeys the linear equalities:   tij + tji = cij , for 1 ≤ i < j ≤ n , and   tii = cii   for 1 ≤ i ≤ n. The score-vector of a C-tournament is the sequence S = (s1,s2,...,sn) of outdegrees for its nodes (i.e., the rowsums   sk = tk1 + tk2 + ... + tkn , for 1 ≤ k ≤ n, of the matrix T).
In our unpublished manuscript [from 1978] we utilized the Duality Principle of linear programming to derive a system of linear inequalities which, for a given n-by-n upper-triangular matrix   C = (cij)   of nonnegative integers, can serve to characterize those C-tournaments of order   n   which have a prescribed score-vector S = (s1,s2, ... , sn), namely:
                                    tij   ≥   0,                                           for   i, j ∈ {1,2,...,n}
                ∑ k ∈ K { sk }   ≥   ∑ i ∈ K ∑ j ∈ K { tij } ,         for each set   K ⊆ {1,2,...,n}

with strict equality holding in case   K = {1,2,...,n}. However, because the number of these inequalities increases exponentially with the order   n   of the n-by-n matrix C , directly checking all of these inequalities for a give C and S very quickly becomes computationally prohibitive with larger problem-sizes.   In a recent investigation of C-tournaments by Richard A. Brualdi and Eliseu Fristcher [2014], an algorithm was presented which constructs one (or more) C-tournaments T having a given score-vector S whenever such examples exist, or else demonstrates their infeasibility by identifying a particular inequality from among our aforementioned linear constraints which is unsatisfied with the chosen C and S.   Antal Ivanyi then asked whether a simple polynomial-time algorithm could be devised for recognizing cases in which, for given C and S, our aforementioned linear constraints all are satisfied. This note exhibits such an algorithm, whose comparative simplicity makes its polynomial-time execution apparent, and for which we here provide a sample implementation written in the C/C++ programming language.


Given an n-by-n upper-triangular nonnegative integer matrix   C = (cij)   and specified n-vector   S = (s1,s2,...,sn)   the sum of whose components equals the total of all the entries in C :

Worst-case execution-time

The programming-loops which occur within algorithm steps 2, 3, 4, and 6 above all
have an obvious   O(n)   or   O(n^2)   worst-case execution-time, while step 7 has an implementation with   O(n^3)   worst-case execution-time; indeed, by taking an early
programming-loop exit as soon as one path from a HI node to a LO node has been
identified, its execution-time can be reduced to   O(n^2)  , although a slightly more
delicate argument would be needed to see that the (possibly smaller) subset   K  
achieved at that stage still can serve to identify a violated inequality constraint. The
programming-loop implicit in step 8 is again   O(n^2)  , and if backtracking data has
been maintained as each forward path from a HI node was being developed, then
the programming-loops of step 9 also have   O(n^2)   execution-times. Finally, if   m  
is the maximum entry in the matrix   C  , then after at most   m   algorithm-iterations
there will be another node added to 'subset_OK', and thus after at most   n-times-m  
iterations our algorithm will terminate, either with a C-tournament that has S as its
score-vector, or with a subset K identifying an essential inequality-constraint which
is not satisfied. From these observations we infer an overall polynomial worst-case
execution-time in the problem-size parameters   m   and   n  .

An example-implementation in C/C++

We have written a computer program in C/C++ which implements our algorithm, with verbose screen output (as depicted below) intended to assist users in understanding the algorithm and its related data-structures, as well as to let users watch algorithm progress in advancing toward its termination criterion within the predicted number of computational steps.

Users may freely download and edit our source-code for any pedagocical purposes, for example, to vary our problem-size parameters, to add additional screen-output, to curtail unwanted display of intermediate calculations, or to experiment with ideas for increasing algorithm efficiency. We will be grateful, of course, if our initial authorship is acknowledged.


R. A. Brualdi and E. Fritscher, Tournaments associated with multigraphs, Discrete Math., January 2014, 17 pages (submitted).

Website created on 20 FEB 2014; Last updated on 25 FEB 2014