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}
and
                ∑ 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.

Algorithm

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 :

• Start with C-tournament T identical to C .
  
  
• Compute the n row-sums for matrix T.
  
  
• Classify each node   i   of T as either HI, LO, or OK, according to whether its
  row-sum is larger than, smaller than, or equal to the corresponding component
    si   of the vector S.
  
  
• Let   'number_ok'   count the OK nodes of T .
  
  
• If   'number_ok'   equals n , then STOP; all the nodes of T are OK, so T is a
  C-tournament having S as its score-vctor.
  
  
• Otherwise, if   number_ok < n , then form the sets 'subset_HI', 'subset_LO',
  and 'subset_OK' of nodes from T.
  
  Note: The first two of these subsets will both be nonempty since (a) every node is
  in one of the three subsets, (b) not all nodes were in 'subset_OK', and (c) the fact
  that the total of the rowsums for T equals the total of the entries in C implies that
  if any row is 'HI', then some other row must be 'LO' to compensate, and vice-versa.
  
  
• Now form the subset   K   which includes all nodes from 'subset_HI', together with
  all nodes from 'subset_OK' and 'subset_LO' which can be reached by following a
  directed path that starts from a node of 'subset_HI'.
  
  Note: This set   K   will be nonempty since it is a superset of 'subset_HI'.
  
  
• There are now only two possibilities: either (a) K contains at least one LO node,
  or else (b) K is disjoint from 'subset_LO'.
  
  
• In case (a), choose any LO node from K, and follow in backward order the directed
  path that allowed that node to enter the set K until reaching some HI node from K.
  Modify the tournament T by reversing the direction of each arc along that backward
  path, and let T* be the resulting multigraph. Go back to step 2, with T being T*.
  
  Note: Because the total number of arcs incident with each node does not change in
  forming T* from T, the multigraph T* will be another C-tournament. But, in reversing
  the backward path's arc-directions, the outdegree of the initial LO node will increase,
  the indegree of the final HI node will decrease, and the indegrees and outdegrees of
  all other nodes will remain unchanged. Hence T* will be "closer" to having rowsums
  that match the corresponding components of vector S.
  
  
• In case (b), it will be impossible for any C-tournament to have S as its score-vector,
  as the subset   K   identifies an inequality (from the aforementioned linear constraint-
  system) which is violated by the given matrix   C   and vector   S  .
  
  Note: Since all nodes of   K   are either HI or OK, and at least one node is HI, the
  total of the rowsums for those rows having indices in   K   will exceed the sum of
  those S-vector components with indices from   K  .
  
  

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.

References

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