next_inactive up previous
Up: Research Page

Convex subsets
as a
heuristic
for
tournament
isomorphism

Matthias E. Johnson

Abstract:

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 \(O(n^3)\) time[6], although the research employs Haglin's and Wolf's easier to implement \(O(n^4)\) time algorithm[3].

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[2].

Introduction

Definitions

A tournament is a directed graph in which each pair of vertices share exactly one edge (see Figure 1).
Figure 1: Tournament of size 7
\scalebox{0.5}{\includegraphics{tourn.ps}}
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.

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 Figure 2).

Figure 2: Regular tournament of size 7
\scalebox{0.5}{\includegraphics{regular.ps}}
Furthermore, it is possible to uniquely embed any tournament of size \(n\) into a regular tournament of size \(4n+1\) [2]. This leads to a polynomial time equivalence between ordinary tournament isomorphism and regular tournament isomorphism.

Backtracking

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.

stopstop

SSOS

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.

Convex Subsets

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).
Figure 3: Tournament of size 7 with convex subset, winners and losers
\scalebox{0.5}{\includegraphics{fill.ps}}
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 \(2\) and \(n-1\). Therefore, the term convex subsets will denote only the non-trivial variety.

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.

Implementation

The first step in this research was the implementation of Haglin and Wolf's \(O(n^4)\) 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 \(n\) in a regular tournament of size \(4n+1\). The programs were available through earlier efforts by Drs. Haglin and Wolf.

Testing Methods

This research is based on the implementation of the algorithm developed by Haglin and Wolf [3]. Although there is a \(O(n^3)\) version of this algorithm, this research employed the slower and easier to implement \(O(n^4)\) 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.

Comparisons of convex subsets and 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.
Figure 4: Comparison of convex subsets and SSOS with full sets of small tournaments
\scalebox{0.6}{\includegraphics{allijk.ps}}

Testing results

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).
Figure 5: Comparison of convex subsets and SSOS with full sets of regular tournaments
\scalebox{0.6}{\includegraphics{regijk.ps}}
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[2] 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.

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 \(\frac{5}{100}\), \(\frac{10}{100}\), \(\frac{15}{100}\), \(\frac{20}{100}\), \(\frac{25}{100}\), \(\frac{30}{100}\), \(\frac{35}{100}\), \(\frac{40}{100}\), \(\frac{45}{100}\) and \(\frac{50}{100}\) (Note 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 numbered.

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

Figure 6: Total number of tournaments with convex subsets
\scalebox{0.6}{\includegraphics{rand_t.ps}}
This is especially true for tournaments generated with the higher probabilities, where, as shown in Figure 6
Figure 7: Number of tournaments with convex subsets in random sets of tournaments with high probability
\begin{figure}\begin{center} \begin{tabular}[c]{\vert c\vert c\vert c\vert c\ver... ...\\ \hline 91 & 0 & 0 & 0 & 0 & 0\\ \hline \end{tabular}\end{center} \end{figure}
only one tournament of all sizes combined contained a convex subset. The decreasing trend is more visible in the tournaments generated using low probabilities (see Figure 7) where the number of tournaments with convex subsets is clearly decreasing as the size of the tournaments
Figure 8: Number of tournaments with low probability containing convex subsets
\scalebox{0.6}{\includegraphics{rand_low.ps}}
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.
Figure 9: Number of tournaments with convex subsets in full sets of tournaments
\scalebox{0.6}{\includegraphics{perc.ps}}

Future Work

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.

It is also possible that convex subsets prove more useful with respect to isomorphism in p-partite tournaments[7]. 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.

Bibliography

1
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.

2
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.

3
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.

4
Sampath Kannan, Tournament and Graph Isomorphism Complete Problems, unpublished manuscript, University of California, Berkeley, 1990.

5
K. B. Reid and Lowell W. Beineke, Tournaments, Selected Topics in Graph Theory, Academic Press, 1978, New York.

6
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 University, 1995.

7
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 University, 1995.
next_inactive up previous
Up: Research Page