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.

The complexity of the algorithm is polynomial in $n$, probably something like $O(n^6)$.

Our main pain is that guessing the wrong solution might not be detected over the rationals or integers.