Monte-Carlo algorithms in graph isomorphism testing
László Babai · 2006
We present an O(V^4 log V) coin flipping algorithm to test vertex-colored graphs with bounded color multiplicities for color-preserving isomorphism. We are also able to generate uniformly distributed random automorphisms of such graphs. A more general result finds generators for the intersection of cylindric subgroups of a direct product of groups in O(n 7/2 log n) time, where n is the length of the input string. This result will be applied in another paper to find a polynomial time coin flipping algorithm to test isomorphism of graphs with bounded eigenvalue multiplicities. The most general result says that if AutX is accessible by a chain G0 ≥ · · · ≥ Gk = AutX of quickly recognizable groups such that the indices |Gi−1: Gi | are small (but unknown), the order of |G0 | is known and there is a fast way of generating uniformly distributed random members of G0 then a set of generators of AutX can be found by a fast algorithm. Applications of the main result improve