Tournament graph

Question

A tournament is a directed graph (digraph) obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge.

Data structure is adjacency matrix.

What s an algorithm to find if the graph is a tournament graph?

Answer 1

There are n^2 entries in the adjacency matrix, and you need the info that is in all of the entries to solve the problem. (You need the 1's to check that the proper edges exist, and the 0's to check that the back-edges don't exist.) Thus since you have to read at least N^2 entries from the matrix, the overall problem must take at least O(N^2) time.

Regarding BFS search attempts: if your traversal takes O(n^2) - which it will, due to the need to look up edges in the adjacency matrix - then it doesn't matter if the back-edge check is constant time, the overall algorithm is still O(n^2).

Yet another way to look at this problem: since the number of edges is equal to the number of possible pairs of vertices, there will be n*(n-1)/2 edges, which is O(n^2). Your traversal is O(V+E), which thus is O(n+n^2), and thus is O(n^2).

Since the best-case time for this algorithm is O(n^2), you might as well simply loop through the upper-right half of matrix (above the diagonal) and check that for each of those entries, either a) it is 1, or b) its transpose equivalent is 1.

Answer 2

Edit: missed the part where the graph was complete.

If M is your adjacency matrix, Mt is the transposed matrix, ~M is the matrix with all the "bits" inverted, and A^B is the xor bit by bit between the two matrix.

Then the matrix is a tournament iff:

~(M^Mt) = I

Answer 3

To add to tonfa's comment:

Brief: The algorithm "for each i ≠ j, check to see that exactly one of (i,j) and (j,i) is in your graph" is asymptotically optimal.

More detail: To just read in the adjacency matrix is going to take you Ω(n²) time. So there is no way to solve this problem in o(n²) time. But let's ignore the input.

Suppose that the matrix is already in memory. To ensure that the undirected version of your graph is complete, you have to somehow determine that, for each i ≠ j, at least one of the edges (i,j) and (j,i) is in your graph. As you have only the adjacency graph, this means you will have to at some point visit at least one of (i,j) or (j,i) for each i ≠ j. There is no other way to guarantee completeness. Verifying this will take n(n+1)/2 = O(n²) steps.