6
$\begingroup$

The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $S_N$ and the function $f \colon \pi \mapsto \pi(G)$ where $G$ is some graph, and $\pi \in S_N$.

The hidden subgroup is the group $Aut(G)$; the group of automorphisms on $G$.

But consider the following adjacency matrix

$$ \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} $$

In this graph, every node is indistinguishable, so the automorphism group is equal to the symmetric group: $Aut(G) = S_N$.

This is an issue. Two graphs are isomorphic if their disjoint union has an automorphism that exchanges their nodes and edges. But running the HSP on the above example of $G$ gives us the full $S_N$ "subgroup" as an output. This group has $N!$ entries, meaning that we would have to search through all $N!$ entries until we find an automorphism that swaps the components of the graphs. But this is clearly $O(N!)$ time.

Graph isomorphism is thought to be intractable on quantum computers, yes. But I don't think this is the reason. So how would an algorithm alleviate this?

$\endgroup$
3
  • 1
    $\begingroup$ There are two graphs in the Graph Isomorphism Problem and you form the wreath product between them IIRC - here you've only given one graph $G$. But then, surely it's even classically easy to tell whether a graph on $n$ vertices is (isomorphic to) the complete graph $K_n$, isn't it? $\endgroup$ May 5, 2023 at 0:41
  • $\begingroup$ Well, I guess your adjacency matrix is the complete graph *with self loops. But still I’d guess it’s easy to find out whether a test graph is isomorphic thereto. Just look at the spectrum of the adjacency matrix. I doubt there’s anything isospectral thereto. $\endgroup$ May 5, 2023 at 2:29
  • $\begingroup$ @MarkS I think I may understand what you're saying. The graphs generated by "combining" two subgraphs that we want to check the isomorphic-ness of can only have a polynomial number of elements in the automorphism group? Whereas I provided a graph that cannot be generated by "combining" two subgraphs. I don't see how this is necessarily true though. $\endgroup$ May 5, 2023 at 2:53

1 Answer 1

6
+200
$\begingroup$

TL;DR: We do not need to inspect all the elements of the hidden subgroup ${\mathcal H}=Aut(G)$. We only need to inspect the elements of the generating set that HSP subroutine has found. An efficient HSP subroutine will return a generating set whose size is polynomial in $\log|\mathcal{H}|$. Finally, note that $\log N!=O(N\log N)$, so even if $Aut(G)\simeq S_N$, we still need to inspect a number of permutations that is polynomial in $N$.

Background

For any finite set $A$, let $S_A$ denote the group of all permutations of $A$. If $G=(V,E)$ with $E\subset V\times V$ is a graph and $\pi\in S_V$ a permutation of its vertices, then set $\pi(G)=(V,\pi(E))$ where $\pi(E)=\{(\pi(u),\pi(v))\,|\,(u,v)\in E\}$. Finally, let $Aut(G)\subset S_V$ denote the subgroup of $S_V$ consisting of vertex permutations $\pi$ that fix $G$, i.e. $\pi(G)=G$.

In the Graph Isomorphism (GI) decision problem we are given two graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ with $N$ vertices and are asked to determine whether they are isomorphic, i.e. if there exists a permutation $\pi\in S_V$ such that $G_1=\pi(G_2)$.

In the Hidden Subgroup Problem (HSP) we are given a group ${\mathcal G}$ and a function $f:{\mathcal G}\to X$ to some set $X$ which hides$^1$ an unknown subgroup ${\mathcal H}$ of ${\mathcal G}$ and are asked to provide a generating set for ${\mathcal H}$. There is a subtlety here. Many generating sets for a large group are themselves large, after all ${\mathcal G}$ is a generating set for ${\mathcal G}$. However, an efficient HSP subroutine by definition outputs a generating set whose size is polynomial in $\log|\mathcal{G}|$. This is always possible since, by group theory, every group ${\mathcal G}$ has a generating set with at most $\log_2|{\mathcal G}|$ generators$^2$.

Reduction

Imagine that we have a magic computer that solves the HSP for permutation groups. We will use it to solve GI for two connected$^3$ graphs $G_1$ and $G_2$ as follows. First, create the disjoint union $G=(W,E)$ where $W=V\sqcup V=V_1\cup V_2$ and $E=E_1\sqcup E_2$. Next, run the HSP solver on the magic computer with $\mathcal{G}:=S_W$, $X$ the set of graphs with vertices in $W$ and $f:\mathcal{G}\to X$ defined by $f(\pi):=\pi(G)$. It is an exercise in the application of definitions to show that $f$ hides $Aut(G)$. Therefore, our magic computer returns a set $\mathcal{S}$ that generates $Aut(G)$.

Now, suppose that every generator $\sigma\in\mathcal{S}$ maps $V_1$ to $V_1$. Then it is impossible to use the generators to construct a permutation that sends a $v\in V_1$ to $w\in V_2$. Consequently, in this case, every $\pi\in Aut(G)$ maps $V_1$ to $V_1$ and $V_2$ to $V_2$. Therefore, $G_1$ is not isomorphic to $G_2$. Conversely, if there is a generator $\sigma\in\mathcal{S}$ that sends $v\in V_1$ to $w\in V_2$, then $\sigma$ necessarily maps $V_1$ to $V_2$ and $V_2$ to $V_1$. Therefore, $G_1$ is isomorphic to $G_2$.

Complexity

Thus, we only need to inspect the effect of every $\sigma\in\mathcal{S}$ on every element of $v\in V_1$ in order to determine whether $G_1$ and $G_2$ are isomorphic. Obviously, $V_1$ has size polynomial in $N$. However, $\mathcal{S}$ has size polynomial in $\log|Aut(G)|\leqslant\log|S_N|=\log N!=O(N\log N)$, so $\mathcal{S}$ also has size polynomial in $N$. We conclude that the cost of classical post-processing is also polynomial in $N$.

Remarks

Note that the reduction above means that the HSP subroutine will never be invoked on a complete graph. After all, $G$ is disconnected! Nevertheless, $Aut(G)$ may be $S_N$. Still, as the argument above shows, the complexity of the classical post-processing remains polynomial.


$^1$ Function $f:G\to X$ hides $H$ if $f$ is constant on each coset of $H$ and injective on every transversal.
$^2$ See e.g. $A2.1.1$ on page $611$ in Nielsen & Chuang for proof.
$^3$ Fun exercise: What goes wrong if $G_1$ and $G_2$ are not connected? How to fix the issue?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.