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 :
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).