The Graph Isomorphism Problem

The graph isomorphism ($\mathsf{GI}$) problem is one of the few known problems in computational complexity that are in the complexity class $\mathsf{NP}$, but neither known to be in $\mathsf{P}$ nor in $\mathsf{NP}$-complete. So it is a very good candidate for a so called $\mathsf{NP}$-intermediate problem. Another well known candidate is factorization.
For many types of graphs the $\mathsf{GI}$ problem could be solved efficiently, i.e., using only poly($n$) many resources, whereof $n$ is the number of vertices in the graph. However, one is able to generate hard instances where all the algorithms fail and an exponential amount of resources is needed in order to solve the problem. But finding such hard instances is not easy. In particular for random graphs, the isomorphism problem is almost always easy. So the average complexity of $\mathsf{GI}$ is low, but the worst case complexity is hard.

Definition [Graph Isomorphism] Two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$ are isomorphic if there is a bijective mapping $\sigma: V_1 \rightarrow V_2$ such that if there is an edge between the vertices $u$ and $v$ in $G$, i.e., $(u,v) \in E_1$, then there is an edge between the vertices $\sigma(u)$ and $\sigma(v)$ in $H$, i.e. $(\sigma(u),\sigma(v)) \in E_2$.

The actual description of the problem is easy and understandable even to people that perhaps see graphs first their first time. In Figure 1 the undirected graph $G$ is shown.

Figure 1 - The graph $G$

$G$ has $8$ vertices and each one is of degree $3$. In Figure 2 you can see the two graphs $H_1$ and $H_2$. One of these is isomorphic to $G$ and the other one is not.

Figure 2 - On the left it is graph $H_1$ and on the right $H_2$

Question: Suppose you could drag each vertex with your mouse. Which set of vertices can be rearranged such that the graph $G$ appears? That means, is $G \cong H_1$ or $G \cong H_2$?



It is not that easy, right? The first thing you can do is to count the vertices. But $H_1$ as well as $H_2$ have $8$ vertices. So this does not help. Also looking at the degree of each vertex does not help.

You can start to bruteforce the solution. You probably start by picking one of the $8$ vertices from $H_1$ or $H_2$ and move it to the position of vertex $1$ from $G$. Then you pick one of the remaining $7$ vertices and move it to the position of vertex $2$ from $G$. You can repeat this until the last vertex is moved. Finally, you have to decide if the graph you just created looks equal to $G$ or not. If yes, the graphs are isomorphic, if not, you have to start again and pick the vertices in another order.
Clearly, you can do this in $8!$ possible ways. For a graph with $n$ vertices this would be $n!$ and is even worse than exponential.

Of course, there are more clever ways to do this. What one needs in order to solve the problem faster is a property of the graph that is invariant under isomorphic transformations. A lot of graphs invariant are known and many of them can indeed be used to distinguish two graphs if they are not isomorphic, e.g.

1. Tutte Polynomial
2. Chromatic Number
3. Clique Number

for more see invariants see this list. However, some of the invariants again can only be calculated with the help of exponential many resources.

The two graphs in Figure 2 can be distinguished for example using the invariant called independence number. That is the size of the maximal set of vertices that are pairwise not adjacency in the graph. In the graph $H_1$ you can pick at most $4$ vertices that are not adjacency, e.g., c,e,g and h. But in $H_2$ you can only pick $3$ vertices that are not adjacency, e.g., a, e and h. And $3$ is also the number of maximal non adjacency vertices you can pick in the original graph $G$, e.g., 1,4 and 7. So $G \cong H_2$ and $G \not\cong H_1$.

You can check this in SAGE via:

--- Input
M_G = matrix(ZZ,8, [0,1,0,0,1,0,0,1, 1,0,1,0,0,0,0,1, 0,1,0,1,0,0,1,0, 0,0,1,0,1,1,0,0, 1,0,0,1,0,1,0,0, 0,0,0,1,1,0,1,0, 0,0,1,0,0,1,0,1, 1,1,0,0,0,0,1,0]);
G = DiGraph(M_G);
G.to_undirected();
M_H1 = matrix(ZZ,8, [0,0,1,0,0,0,1,1, 0,0,1,0,1,0,0,1, 1,1,0,1,0,0,0,0, 0,0,1,0,1,0,1,0, 0,1,0,1,0,1,0,0, 0,0,0,0,1,0,1,1, 1,0,0,1,0,1,0,0, 1,1,0,0,0,1,0,0]);
H1 = DiGraph(M_H1);
H1.to_undirected();
M_H2 = matrix(ZZ,8, [0,0,1,1,0,1,0,0, 0,0,0,0,1,0,1,1, 1,0,0,0,1,0,0,1, 1,0,0,0,1,1,0,0, 0,1,1,1,0,0,0,0, 1,0,0,1,0,0,1,0, 0,1,0,0,0,1,0,1, 0,1,1,0,0,0,1,0]);
H2 = DiGraph(M_H2);
H2.to_undirected();
print "G ~ H1 ? ",G.is_isomorphic(H1);
print "G ~ H2 ? ",G.is_isomorphic(H2); 
--- Output

G ~ H1 ?  False
G ~ H2 ?  True

# Graph Isomorphism and Double Columnar Transposition #

Suppose we have to solve the task to decide if $G \cong H$, both having $n$ vertices. If we denote with $\text{M}_G$ the adjacency matrix of $G$ and with $\text{M}_H$ the one of $H$, then it is well known that the task to decide if the two graphs are isomorphic is equivalent to decide if there exists a permutation matrix $\text{P}$ such that $$\text{P}\text{M}_G\text{P}^{-1} = \text{P}\text{M}_G\text{P}^{t}  = \text{M}_H$$ From this you can also see, that the determinant of the adjacency matrix can not be used to decide isomorphism, since the determinant stays the same if always a column and a row are permutet.

In the example above, the adjacency matrix of $G$ is
$$\begin{bmatrix} 0&1&0&0&1&0&0&1\\ 1&0&1&0&0&0&0&1\\ 0&1&0&1&0&0&1&0\\ 0&0&1&0&1&1&0&0\\ 1&0&0&1&0&1&0&0\\ 0&0&0&1&1&0&1&0\\ 0&0&1&0&0&1&0&1\\ 1&1&0&0&0&0&1&0\\ \end{bmatrix}$$ and the permutation matrix $P$ that creates $H_2$ is
$$\begin{bmatrix} 0&1&0&0&0&0&0&0\\ 0&0&0&0&0&1&0&0\\ 0&0&1&0&0&0&0&0\\ 0&0&0&0&0&0&0&1\\ 0&0&0&0&0&0&1&0\\ 1&0&0&0&0&0&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&1&0&0&0&0\\ \end{bmatrix}$$

In a previous blog post i talked about the Double Columnar Transposition cipher (DCTC) and some approaches for cryptanalysis. If you define the DCTC using matrices and if you assume the simplest case for that DCTC (i.e., the ciphertext can be arranged to a square with sidelength $n$ and the two keywords are equal and of length $n$) then you can solve the DCTC if you can find a permutation matrix $\text{P}$ such that $$\text{P}_1^{t}\text{K}^t\text{P}_2 = \text{C}$$ whereof $\text{K}$ is the plaintext matrix (substituted by integers) and $\text{C}$ the ciphertext matrix. Which can be seen equivalent to solve the task $$\text{P}{M}_G\text{P}^{-1} = \text{P}{M}_G\text{P}^{t}  = \text{M}_H$$

 
In the section "A direct approach" i made some calculationc how many plaintext $\rightarrow$ ciphertext position one has to guess and how many additional relations one obtains from this guessing.

The same argumentation can be applied to the $\mathsf{GI}$ problem. I will sketch the approach in the following. It think it is interesting, since it is an approach that is based on following the edges and not the vertices.

 # Approach #

First i will illustrate the approach using an example.

$$\text{M}_G = \begin{bmatrix} 0&\color{red}{1}&0&0&1&0&0&1\\ 1&0&\color{blue}{1}&0&0&0&0&1\\ 0&1&0&1&0&0&1&0\\ 0&0&1&0&1&1&0&0\\ 1&0&0&1&0&1&0&0\\ 0&0&0&1&1&0&1&0\\ 0&0&1&0&0&1&0&1\\ 1&1&0&0&0&0&1&0\\ \end{bmatrix} \rightarrow \begin{bmatrix} 0&0&1&0&0&0&1&1\\ 0&0&1&0&1&0&0&1\\ 1&1&0&\color{red}{1}&0&0&0&0\\ 0&0&1&0&1&0&1&0\\ 0&1&0&1&0&1&0&0\\ 0&0&0&0&1&0&1&1\\ \color{blue}{1}&0&0&1&0&1&0&0\\ 1&1&0&0&0&1&0&0\\ \end{bmatrix} = \text{M}_H$$

Assume that we guess that the red $1$ on the left moves to the position of the red $1$ on the right and so does the blue $1$. (The left is the adjacency matrix of graph $G$ from above and the right the adjacency matrix of $H_1$, so they are not isomorphic).

Let see, which entries in the permutation matrix $\text{P}$ the two guessed entries are responsible for.
It is not hard to see, that in order to bring the red $1$ to the final position, the permutation matrix must look like:

$$\begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}\cdot \text{M}_G \cdot \begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}$$ which is equal to
$$\begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&\color{red}{1}&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}$$ Since the right permutation matrix is just the transpose of the left, we have to combine the two entries and the matrix $$\text{P} = \begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}$$ Hence we just got an entries "for free". If we apply the new $\text{P}$ to the equation, we get
$$\begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}\cdot \text{M}_G \cdot \begin{bmatrix} 0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}$$ which is equal to $$\begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&\color{red}{0}&\color{red}{1}&0&0&0&0\\ 0&0&\color{red}{1}&\color{red}{0}&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix}$$ Now, we can compare the $4$ determined entries with the target matrix $\text{M}_H$ and see if all of them agree. If they do not, which is called Abort-Criteria 1, start again and guess a different position for the red $1$. But in this case they do. So, we proceed by taking the blue $1$ into account.  To move the blue $1$ from the second row to the seventh, $\text{P}$ must get an $1$ in row $7$  and column $2$, i.e.,
$$\begin{bmatrix} 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&0&0\\ \end{bmatrix} \not\in \text{PermMatrices}$$ But this $\text{P}$ is not a valid permutation matrix anymore, hence we reached Abort-Citeria 2. So the guessed positions of the red and the blue one can not be correct, at least in this combination.

Some rough calculations. Assume we have the undirected, loop-free graph $G$ with $n$ vertices and density $\delta$, i.e., $$\delta = \frac{2|E|}{|V|(|V|-1)} = \frac{2|E|}{n(n-1)}$$ Each edge in $G$ is responsible for two $1$s in the adjacency matrix $\text{M}_G$ of $G$. So the number of $1$s in $\text{M}_G$ is $\delta n (n-1) = T$.
We pick $m$ of these $1$ entries in $\text{M}_G$ and guess their new position in $\text{M}_H$. The positions of these $m$ entries in $\text{M}_G$ are fixed. We only vary our guesses about their destination position. We get $T$ for the first, $T-1$ for the second,..., $T-(m-1)$ for the last, i.e., in total $$\prod^{m-1}_{i=0} (T-i) = \prod^{m-1}_{i=0} (\delta n(n-1)-i)$$ possible combination to guess. For each of the $m$ entries we get $2$ entries in the $\text{P}$ matrix  (checking for Abort-Criteria 1) hence in total $2m$ entries in $\text{P}$. And those entries again are responsible for $(2m)^2$ positions that can be compared with $\text{M}_H$. We always move $m$ entries on purpose, but the rest $(2m)^2-m$ entries arise randomly(?). The probability that one of these $(2m)^2-m$ entries, say $e_G$, is identical with the one in $\text{M}_H$, say $e_H$ is:
$$\begin{align*} & \text{Pr}[e_G = 1]\text{Pr}[e_H = 1] + \text{Pr}[e_G = 0]\text{Pr}[e_H = 0] \\ & = \frac{T}{n^2}\frac{T}{n^2} + \left(1-\frac{T}{n^2}\right)\left(1-\frac{T}{n^2}\right) \\ & = \frac{T^2}{n^4} + 1 - 2\frac{T}{n^2} +  \frac{T^2}{n^4}\\ & = 1 - 2\left(\frac{T}{n^2}-\frac{T^2}{n^4}\right) \approx 1 - 2(\delta - \delta^2)  \end{align*}$$ Hence for $m$ such entries we simply have (assuming sufficient independence) the probability for all of them being equal of
$$\begin{align*} &  \approx \left(1 - 2(\delta - \delta^2)\right)^{(2m)^2-m}\;\;\;(*)  \end{align*}$$ If we now multiply the number of possibilities and the probability and using the slightly larger product $$(\delta n(n-1))^m = \prod^{m-1}_{i=0} (\delta n(n-1)) > \prod^{m-1}_{i=0} (\delta n(n-1)-i)$$ so we get
$$\begin{align*} \approx (\delta n(n-1))^m \left(1 - 2(\delta - \delta^2)\right)^{(2m)^2-m} \end{align*}$$ of total possibilities. For $\delta = 1/2$ the probability (*) reaches its minimum (so we are looking at the best possible case). If we plug this in, we get $$2^{-4m^3+m^2-m}(n-1)^mn^m$$ To reduce this to at most one final candidate, we compute
$$\begin{align*} & 2^{-4m^3+m^2-m}(n-1)^mn^m \leq 1 \\ &\Leftrightarrow 2^{m^2}(n-1)^mn^m \leq 2^{4m^3+m}\\ &\Leftrightarrow m^2+m\log_2(n-1)+m \log n \leq 4m^3+m\\ &\approx 2\log_2 n \leq 4m^2-m^1+1\\  \end{align*}$$
$$\begin{equation}  m \geq \frac{1}{8} + \left( \frac{\sqrt{32\log_2(n) - 15}}{8}  \right) \end{equation}$$ which is exponential in $m$ but not in $n$.

So, for example a graph with $n = 10000$ vertices, $m=3$ is sufficient. But this means also, that one has to test all the $\prod^{m-1}_{i=0} (\delta n(n-1)) \approx 10000^6/8$ candidates to find the correct one.

I think this can be optimized, especially by taking Abort-Criteria 1 into account. The advantage of this approach would be that it not only decides if the two graphs are isomorphic, but also returns the permutation matrix of the isomorphism.

Update. A simple but very good optimization is to use only those possibilities as further input in round $i$ which survived rounds $1$ to $i-1$.