Reduction from Graph Isomorphism to String Isomorphism

Question

I was studying the reduction from Graph Isomorphism (GI) to String Isomorphism (SI) showed in this bachelor's thesis in Chapter 2.2 and was understanding the procedures just fine until I got stuck in a proof.

My problem is in the following Lemma:

Lemma 2.9. If SI is $O(f(n))$, then GI is $O(f(n^2) + n^2)$.

Given $X = (\Omega, E)$ and $Y = (\Omega, F)$, we create the indicator functions $\eta,\iota : \Omega^2 \rightarrow \{0,1\}$ that encodes which edge is in $E$ and $F$ or not by using some sort of (unordered?) binary string.

Then it gets weird for me. In the natural action $S = im(Sym(\Omega) \rightarrow Sym(\Omega^2))$ of $Sym(\Omega)$ on $\Omega^2$ we get an action in the format $Sym(\Omega) \times \Omega^2 \rightarrow S$? How is a function of $f \in Sym(\Omega)$ applied in $\Omega^2$ and how is $S$ constructed? I understand that the image of $Sym(\Omega) \rightarrow Sym(\Omega^2)$ will have leftovers elements in the right side, but the elements are to be chosen arbitrarily?

The result is a group of bijections $I = Iso_{S}(\eta,\iota)$ that maps pairs from $\eta$ to pairs of $\iota$, resulting in $I = Iso(X,Y)$, as these two functions are indicator functions for edges. But I also can't really see from where the resulting complexity comes from.

Can someone help me?

Answer 1

In the string isomorphism problem, we are given two length-$N$ strings over the same alphabet and a group $G$ of allowable permutations: a subgroup of $S_N$. The problem is to find all the elements of $G$ which permute one string into the other (or, in the decision version of the problem, to determine if there is any such element).

The rough idea of this lemma is this. We encode $n$-vertex graphs as $n \times n$ adjacency matrices, and think of these as length-$n^2$ strings over the alphabet $\{0,1\}$. To remember that these are adjacency matrices, the subgroup $G$ that we use is the subgroup of those permutations that come from permuting the rows of the adjacency matrix in some way, then permuting the columns in the exact same way. These correspond exactly to permuting the vertices of a graph.

Let's take a simple example, with $n=3$. Take the graphs $X$ with edges $\{12, 13\}$ and $Y$ with edges $\{13, 23\}$. Then:

1. Their adjacency matrices are: $$A_X = \begin{bmatrix}0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0\end{bmatrix} \qquad \text{and} \qquad A_Y = \begin{bmatrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0\end{bmatrix}$$
2. We can "flatten these out" to read them as strings $011100100$ and $001001110$. (I'm just concatenating all the rows here).
3. The subgroup $G$ can be generated by the following two permutations: $$g_1 = (1\;5)\;(2\;4)\;(3\;6)\;(7\;8) \qquad \text{and} \qquad g_2 = (2\;3)\;(4\;7)\;(5\;9)\;(6\;8).$$ These correspond to swapping rows/columns $1$ and $2$, and to swapping rows/columns $2$ and $3$, respectively. To check this, apply $g_1$ to the string $abcdefghi$ getting $edfbachgi$, which if we write it as a $3\times 3$ matrix again is the transformation $$\begin{bmatrix}a & b & c \\ d & e & f \\ g & h & i\end{bmatrix} \leadsto \begin{bmatrix}e & d & f \\ b & a & c \\ h & g & i\end{bmatrix}.$$ This is exactly what we get by swapping rows $1$ and $2$ then columns $1$ and $2$. Similar work explains $g_2$.
4. In fact, there is a permutation in $G$ that turns $011100100$ into $001001110$. This permutation is the permutation $$g_1g_2g_1 = (1\;9)\;(2\;8)\;(3\;7)\;(4\;6)$$ that corresponds to swapping rows/columns $1$ and $3$. So the two strings are isomorphic. So are the two graphs: the graph isomorphism swaps vertices $1$ and $3$.

The reason for the complexity is that we've turned an $n$-vertex $\textsf{GI}$ problem into an $n^2$-length $\textsf{SI}$ problem, with $O(n^2)$ processing time for the transformation (because we need to build the adjacency matrix). If we can solve a length-$n$ instance of $\textsf{SI}$ in $O(f(n))$ time for all $n$, then we can solve the resulting length-$n^2$ instance of $\textsf{SI}$ in $O(f(n^2))$ time. This means that we can solve an $n$-vertex instance of $\textsf{GI}$ in $O(f(n^2)) + O(n^2)$ time: $O(n^2)$ for the transformation, and $O(f(n^2))$ for whatever our $\textsf{SI}$ algorithm is.