Tournaments are complete graphs in which all edges are given a
direction. There is no known polynomial time algorithm for
determining an isomorphic relationship between two given tournaments
nor is it known to be NP-complete. Dr. David J. Haglin and Dr. Marty
J. Wolf have developed a backtracking algorithm which will find an
isomorphic relationship between two tournaments if one exists. In
order to decrease the time needed to determine such an isomorphism,
the algorithm divides the problem into smaller parts. A preprocessing
phase partitions the vertex sets of the tournaments in question into
smaller subsets based on easily computed edge domination properties.
After this is done, the standard backtracking approach resolves the
final steps of the isomorphism question.
It is apparent that the size of the subsets into which the vertex sets
are partitioned plays an important role. Therefore an effective means
of generating small partitions of the vertex sets will speed up the
backtracking process. This paper discusses the effectiveness of convex
subsets in this partitioning process and compares it to an easily
computed vertex domination scheme.
The research examines the application of the convex subset
algorithm as formulated by Drs. Haglin and Wolf to the isomorphism
test. This algorithm finds all convex subsets of a tournament in
time, although the research employs
Haglin's and Wolf's easier to implement time
Much attention has been given to the comparison of large regular
tournaments. Regular tournaments differ from ordinary
tournaments in that all vertices have an identical out-degree. The
reason for the focus on regular tournaments lies in the
polynomial-time equivalence of regular tournament isomorphism and
ordinary tournament isomorphism.
A tournament is a directed graph in which each pair of vertices
share exactly one edge (see Figure 1).
Two tournaments are said to be isomorphic if it is possible to relabel
the vertices in one tournament and obtain the other as the result
while preserving the orientation of the edges. Determining the
isomorphic relationship becomes harder computationally as the size of
the tournament increases. There is currently no known polynomial time
algorithm to solve the tournament isomorphism problem, nor is it known
to be NP-complete.
Tournament of size 7
A tournament is regular if the number of incoming edges is equal
to the number of outgoing edges for every vertex. A regular
tournament must have an odd number of vertices (see
Furthermore, it is possible to uniquely embed any tournament of size
into a regular tournament of size . This
leads to a polynomial time equivalence between ordinary tournament
isomorphism and regular tournament isomorphism.
Regular tournament of size 7
The backtracking algorithm designed by Haglin and Wolf
will find an isomorphism if one exists. It works by using a
constraint matrix with the vertices of one tournament along
the rows and the vertices of the other tournament along the
columns. Initially the matrix is filled with 1's indicating a possible
mapping from each vertex in one tournament to each vertex in the other
tournament. The backtracking algorithm will need to examine all
possibilities in order to resolve the isomorphism problem, leading
to a potential exponential running time. Therefore it is desirable
to eliminate as many combinations as possible before the backtracking
algorithm resolves the final possibilities. This elimination is
achieved through partitioning of the vertex sets in both tournaments.
One method of partitioning the vertex set is score sequence of
signatures or SSOS.
This method, developed by Drs. Haglin and Wolf, examines each vertex
in a given tournament based on the vertices dominated by that
vertex. Each of these dominated vertices is assigned a score determined by
the number of vertices it in turn dominates. The resulting
scores make up the score sequence. Combining the score sequences of
all vertices then yields the score sequence of signatures.
Given that in two isomorphic tournaments every vertex in one
tournament with a particular SSOS must have a matching vertex with the
same SSOS in the other tournament, the SSOS is then used to update the
constraint matrix. SSOS was used to determine the effectiveness of
convex subsets in the partitioning process, in particular since it is
beneficial both in cases where an isomorphism exists and where there
is no isomorphism.
A convex subset is a subset of vertices such that all
vertices not in the subset either dominate or are dominated by all
vertices in the convex subset (see Figure 3).
All vertices outside of the convex subset dominated by those inside
are the losers. The vertices which dominate all vertices in
the convex subset are the winners. Clearly every vertex by
itself as well as the collection of all vertices form convex subsets,
however this research was only concerned with non-trivial convex
subsets of sizes between and . Therefore, the term
convex subsets will denote only the non-trivial variety.
Tournament of size 7 with convex subset, winners and losers
After finding all convex subsets they can then be used to update the
constraint matrix. Every vertex in a convex subset of a given size
can only map onto the vertices in the other tournament which are also
in a convex subset of that size. If the there are different number of
convex subsets or if the sizes of the individual convex subsets vary
then the tournaments are non-isomorphic. This means that like SSOS,
convex subsets are beneficial whether there is an isomorphism or not.
The first step in this research was the implementation of Haglin and
Wolf's time algorithm for finding all convex subsets. The
coding was done in C++ and utilizes existing
C++ class objects. For this research the new object class
Convex Subset was created with the necessary methods to
interface to the appropriate tournament objects. Two new programs
have been written. One to find the convex subsets in a given
tournament and the other to compare the effectiveness of the convex
subset method to SSOS.
In addition to the new code, existing programs have also been
used to generate large tournaments. These programs include a
program to generate random tournaments and a program to perform
Colburn and Colburn construction, embedding a tournament of
size in a regular tournament of size . The programs
were available through earlier efforts by Drs. Haglin and Wolf.
This research is based on the implementation of the algorithm developed by
Haglin and Wolf . Although there is a
version of this algorithm, this research employed the slower and
easier to implement algorithm. This was done because
greater importance was given to determining the overall usefulness of
convex subsets as opposed to implementing an efficient
algorithm. As mentioned above, in order to have a measure of how well
the convex subset algorithm performed, it was compared to SSOS.
The first tests conducted on small sets of tournaments of size 5
showed promising results because a high percentage of
tournaments was determined to be non-isomorphic based solely on the
use of convex subsets. As seen in Figure 4, the effectiveness
of convex decreases for the small tournaments whereas the effectiveness
of SSOS increases. This was conjectured to be due to the small sizes.
Comparison of convex subsets and SSOS with full sets of
Further testing continued to show the same trend as the tests on the
small tournaments had shown. These tests were run using the available
full sets of tournaments of size 5, 6 and 7 (see Figure 4), as well as
the full sets of regular tournaments of size 9 and 11 (see Figure 5).
To be certain that the effectiveness of convex subsets
decreased as the size of the tournament increases, larger tournaments
were used for testing. A first set of larger tournaments was
generated by applying the Colburn and Colburn construction algorithm to
tournaments of size 9 resulting in tournaments of size 37.
Unfortunately these tournaments contained virtually no convex subsets
and it was assumed that this may be due to the construction algorithm.
Comparison of convex subsets and SSOS with full sets of
This lead to the study of tournaments generated at
random with varying probabilities with respect to edge direction. 1000
unique tournaments for each of the sizes 20, 21, 30, 31, 40, 41, 50,
51, 60, 61, 70, 71, 80, 81, 90 and 91 were generated where each of the
sizes was equally divided into the probabilities ,
that this last probability provides the highest likelihood of obtaining a
regular tournament.) The probability refers to the direction given to
an edge is from a low number vertex to a high numbered numbered, so
that a probability of 1 means that the
edge will always go from the lower numbered vertex to the higher
The result confirmed that the chances of finding a convex
subset in a tournament as the size of the tournament increases are
decreasing (see Figure 5).
This is especially true for tournaments generated with the higher
probabilities, where, as shown in Figure 6
Total number of tournaments with convex subsets
only one tournament of all sizes combined contained a convex subset.
The decreasing trend is more visible in the tournaments generated
probabilities (see Figure 7) where the number of tournaments with convex
subsets is clearly decreasing as the size of the tournaments
Number of tournaments with convex subsets in random sets of
tournaments with high probability
increases. This is the same trend as can be seen in Figure 8 where
the full sets of tournaments of size 5, 6, 7, 8 and 9 were used.
Number of tournaments with low probability containing convex
Although convex subsets do not provide a useful tool for tournament
isomorphism there are a number questions that may prove interesting.
A formal proof that the probability of finding a convex subset
approaches 0 as the size of the tournament increases warrants further
efforts. This implies a need to know how the addition of a new vertex
to a tournament influences the creation of a new convex subset and the
preservation of existing ones in the resulting tournament.
Number of tournaments with convex subsets in full sets of
It is also possible that convex subsets prove more useful with
respect to isomorphism in p-partite
tournaments. These tournaments differ from ordinary
tournaments in having sets of vertices which do not share an edge
among each other but only with all vertices in all other sets.
Convex subsets may prove more useful with these tournaments because
ordinary tournament have at most a polynomial number of convex
subsets, whereas it is known that there are p-partite
tournaments with an exponential number of convex subsets. The
conjecture is that a richer set of convex subsets will yield better
results in the partitioning process.
László Babai and Eugene M. Luks, Canonical labeling of
graphs, Proceedings 15th Annual ACM Symposium on Theory of Computing,
vol. 15, pp 171-182, 1983.
Charles J. Colburn and Marlene J. Colburn, Isomorphism Problems
involving Self-complementary Graphs and Tournaments, 8th Manitoba
Conference on Numerical Mathematics and Computing vol. 8, pp 153-164.
David J. Haglin and Marty J. Wolf, On Convex Subsets in
Tournaments, SIAM Journal on Discrete Mathematics vol.
9,1,(Feb 1996) pp 63-70.
Sampath Kannan, Tournament and Graph Isomorphism Complete Problems,
unpublished manuscript, University of California, Berkeley, 1990.
K. B. Reid and Lowell W. Beineke, Tournaments, Selected Topics in
Graph Theory, Academic Press, 1978, New York.
Marty J. Wolf and David J. Haglin, An Optimal Algorithm for Finding
All Convex Subsets in Tournaments, Technical Report MSU-CS-TR 9509-001
Computer and Information Sciences Department, Mankato State
Marty J. Wolf and David J. Haglin, On Convex Subsets In
p-Partite Tournaments, Technical Report MSU-CS-TR 9509-002
Computer and Information Sciences Department, Mankato State