Efficient graph automorphism by vertex partitioning

摘要

We describe a vertex partitioning method and squeeze tree search technique, which can be used to determine the automorphism partition of a graph in polynomial time for all graphs tested, including those which are strongly regular. The vertex partitioning procedure is based on first transforming the graph by the 1-or 2-subdivision transform or the 1-or 2-superline transform and then employing a distance signature coding technique on the vertices of the transformed graph. The resulting adjacency refinement partition of the transformed graph is reflected back to the original graph where it can be used as an initial vertex partition which is equal to or coarser than the desired automorphism partition.The squeeze tree search technique begins with two partitions, one finer than the automorphism partition and one coarser than the automorphism partition. In essence, it searches through all automorphisms refining the coarser partition and coarsening the finer partition until the two are equal. At this point the result is the automorphism partition. The vertex partitioning method using the 2-superline graph transform preceeding the squeeze tree search is so powerful that for all the graphs in our catalog (random, regular, strongly regular, and balanced incomplete block designs) it produces the automorphism partition, thereby making the tree search nothing more than a verification that the initial partition is indeed the automorphism partition.