We found, implemented and tested algorithm for graph isomorphism and it appears to be polynomial time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A graph is rigid if its automorphism group is trivial.
Two graphs $G_1,G_2$ of order $n$ are isomorphic iff there exist permutation matrix $P$ such that $P A_1 P^{-1}=P A_1 P^T = A_2$ where $A_1,A_2$ are their adjacency matrices. We believe it is rigorous to multiply by $P$ and have $P A_1 = A_2 P$.
Let $P$ be $n$ by $n$ matrix with entries $n^2$ variables $x_{i,j}$.
Construct the following system of linear equations $J$.
For the rows $k$ of $P$ add the equations $\sum_{1 \le i \le n} x_{k,i} = 1$. For the columns $k$ of $P$ add the equations $\sum_{1 \le i \le n} x_{i,k} = 1$.
This is necessary condition $P$ to be permutation and if the variables are zero or one it is sufficient.
Let $M = P A_1 - A_2 P$. The entries of $M$ are linear equations in $x_{i,j}$.
For all $n^2$ entries of $M$ add to $J$ the constraints $M_{i,j}=0$.
$J$ has $n^2+2n$ linear equations in $n^2$ variables.
If we can find zero/one solution to $J$, we can solve GI.
Main idea for finding the unique zero/one solution.
Guess variable $x_{i,j}=1$. This forces all $x_{i,k}=0$ for the row and $x_{k,j}=0$ for the columns. These are $2n$ equations in $2n-1$ variables. Add these equation to $J$ and let the resulting system be $J'$. Experimentally, if we make the wrong guess in the unique solution, $J'$ doesn't have any solutions over the rationals and this can be found using linear algebra. If the guess is wrong, set $x_{i,j}=0$ and substitute in $J$. If the guess is correct, we might find zero/one solution over the rationals.
Repeat for all $n^2$ variables.
ADDED explaining the "guessing" part. $J$ has infinitely many integer solutions but single zero/one solution since the graph is rigid. Let $P'$ be the matrix of the unique zero/one solution. We are guessing $P'$ entry by entry. Assume $P'_{1,1}=1$. In $J'$ add $x_{1,1}=1,x_{1,i}=0,x_{i,1}=0,1 \le i \le n$. This reduces the number of variables by $2n-1$. Since the guess is correct, we keep the unique zero/one solution and $J'$ has integer solution. In practice the integer solution is zero/one over the integers.
Assume we make the wrong guess $P'_{1,2}=1$. Add the rows and columns constraints $x_{1,2}=1,x_{1,i}=0,x_{i,2}=0,1 \le i \le n$. Experimentally in the wrong guess $J'$ doesn't have any solutions over the integers and hence no zero/one solution. In $J$ replace $x_{1,2}=0$ in all equations, decreasing the variables by $1$
The complexity of the algorithm is polynomial in $n$, probably something like $O(n^8)$.
Our main pain is that guessing the wrong solution might not be detected over the rationals or integers.
