as a

heuristic

for

tournament

isomorphism

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[6], although the research employs Haglin's and Wolf's easier to implement 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].

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

Furthermore, it is possible to uniquely embed any tournament of size into a regular tournament of size [2]. This leads to a polynomial time equivalence between ordinary tournament isomorphism and regular tournament isomorphism.

stopstop

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.

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.

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 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 , , , , , , , , and (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).

This is especially true for tournaments generated with the higher probabilities, where, as shown in Figure 6It 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.

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