Analysis of Complex Networks

1.4 Approximating Orbits

The automorphism group Aut(G) of a graph G is a subgroup of S_n, the symmetric group on n objects, so | Aut(G)| ≤ n!. Constructing all the elements of the automorphism group could take exponential time, e.g., K_n has S_n as its automorphism group. However, it may be sufficient to find a relatively small generating set that represents Aut(G). Indeed, it is always possible to find a generating set of size log n for a group H of size n [1].

Unfortunately it is not known whether or not such a small set representing Aut(G) can be computed in polynomial time, because the problem of determining the automorphism group can be shown to be equivalent to graph isomorphism (i.e., determining whether two graphs are isomorphic). The relationship between the two problems is shown more explicitly in [1].

Since the problem of determining when two graphs are isomorphic has been studied extensively and is not known to be solvable by a polynomial bounded algorithm, heuristics are needed to find the orbits of the automorphism group. If such heuristics are easy to compute and provide a high degree of accuracy, the complexity of a graph can be computed efficiently with a high degree of confidence.

The orbits of a graph consist of vertices with similar properties such as having the same degree. So if it were possible to create a small list of all these properties and if, in addition, there were polynomial time tests for each one, then there would be a polynomial time algorithm for ...