Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?

Question

The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as follows based on the detailed proof given in Section 1.5 of The Graph Isomorphism Problem - Its Structural Complexity.

1. Prove that the graph automorphism problem is Turing-reducible to the graph isomorphism problem.
2. Prove that the graph automorphism problem has a polynomial time computable or-function.
3. Prove that the graph isomorphism problem has both polynomial time computable and- and or-functions.
4. Combining the previous results, it may be argued that the graph automorphism problem is Karp-reducible to the graph isomorphism problem.

My question is whether similar reduciblity can be inferred for the problems under hidden subgroup representations (HSP). Let me define those representations.

Graph isomorphism as a hidden subgroup problem

Let the $2 n$ vertex graph $\Gamma = \Gamma_1 \sqcup \Gamma_2$ be the disjoint union of the two graphs $\Gamma_1$ and $\Gamma_2$ such that $Aut \left(\Gamma_1\right) = Aut \left(\Gamma_2\right) = \left\{e\right\}$ (a limited version). A map $\varphi : S_{2n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{2n}$ is said to have hidden subgroup structure if there exists a subgroup $H_\varphi$ of $S_{2n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{2n}/H \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that the diagram is a commutative diagram, where $S_{2n}/H_{\varphi}$ denotes the collection of right cosets of $H_\varphi$ in $S_{2n}$, and where $\nu : S_{2n}/H_\varphi$ is the natural map of $S_{2n}$ onto $S_{2n}/H_\varphi$. We refer to the group $S_{2n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph isomorphism problem is to determine a hidden subgroup $H$ of $S_{2n}$ with the promise that $H$ is either trivial or $|H| = 2$.

Graph automorphism as a hidden subgroup problem

For a graph $\Gamma$ with $n$ vertices, a map $\varphi : S_{n} \to \text{Mat}\left(\mathbb{C}, N \right)$ from the group $S_{n}$ is said to have hidden subgroup structure if there exists a subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{n}/\text{Aut}\left(\Gamma\right) \to \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that for each $g \in \text{Aut}\left(\Gamma\right)$, $g \left(\Gamma\right) = \Gamma$ and, the diagram is commutative, where $S_{n}/\text{Aut}\left(\Gamma\right)$ denotes the collection of right cosets of $\text{Aut}\left(\Gamma\right)$ in $S_{n}$, and where $\nu : S_{n}/\text{Aut}\left(\Gamma\right)$ is the natural map of $S_{n}$ onto $S_{n}/\text{Aut}\left(\Gamma\right)$. We refer to the group $S_{n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph automorphism problem is to determine a hidden subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$ with the promise that $\text{Aut}\left(\Gamma\right)$ is either of trivial or non-trivial order depending on the type of $\Gamma$.

My questions:

I think it can be trivially shown that the hidden subgroup representation of the graph automorphism problem is Turing-reducible to the graph isomorphism problem by giving two input graphs as the original graph and the candidate automorphism of the original graph.

If I am correct, the remaining question is whether there is a Karp-reduction for the hidden subgroup representation. If there is, how it can be shown.

Answer 1

I think your focus on the rigid case of GI limits you too much. Instead phrase (non-rigid) GI as an HSP in the same way, but now the goal is to determine the size of the hidden subgroup, or a generating set. The difference between the isomorphic and non-isomorphic cases will be a factor of 2 in the order of the hidden subgroup. If you phrase the problem as finding generators of the hidden subgroup, then the question is just whether any generator switches $\Gamma_1$ and $\Gamma_2$.

Now, an instance of "HSP-GA" corresponding to a graph $\Gamma$ is given by the function from $S_n \to M_n(\mathbb{C})$ defined by $f(\pi) = A(\pi(\Gamma))$ where $A(\cdot)$ denotes the adjacency matrix. In particular, $f(1) = A(\Gamma)$. Then apply the usual Karp reduction from GA to GI to get a pair of graphs $\Gamma_1, \Gamma_2$, and consider the HSP-GI instance, of the type described in the preceding paragraph, corresponding to the pair $\Gamma_1, \Gamma_2$ (that is, the disjoint union $\Gamma_1 \cup \Gamma_2$).