Reduction of graph isomorphism to isomorphism and conjugacy of permutation subgroups

Abstract

This paper provides polynomial time reductions from Graph Isomorphism to isomorphism and conjugacy of two permutation subgroups, in both cases input as a set of generating elements. It also covers a reduction from conjugacy to isomorphism for the case where the conjugating permutation may be from the whole symmetric group.