Authors: V. Arvind, Richard Beigel, and Antoni Lozano
Abstract: Motivated by the question of the relative complexities of the Graph Isomorphism and the Graph Automorphism problems, we define and study the modular graph automorphism problems. These are the decision problems MODkGA which consist, for each k > 1, of deciding whether the number of automorphisms of a graph is divisible by k. The MODkGA problems all turn out to be intermediate in difficulty between Graph Automorphism and Graph Isomorphism.
We define an appropriate search version of MODkGA
and design an algorithm that polynomial-time reduces the
MODkGA search problem to the decision problem.
Combining this algorithm with an IP protocol, we obtain a randomized
polynomial-time checker for MODkGA, for all
Download Full Paper