Given graphs $G, H$ determining whether $G$ is isomorphic to $H$, i.e., $G \cong H$, does not have a polynomial time algorithm and has not been proven to be NP-Complete. We consider undirected graphs. I am outlining the main idea for an algorithm and request feedback.
Approach
We label the vertices of the graph for convenience.
There are all-pairs shortest path algorithms for a graph that run in polynomial time in number of vertices such as Floyd-Warshall algorithm ($O(V^3)$). We set all edge weights to $1$ in $G, H$ and compute all-pairs shortest paths. We get $V \times V$ path matrices $P_G, P_H$ for $G$ and $H$ respectively where the entry for row $i, j$ has the path length between vertices $i$ and $j$. These $P_G$ and $P_H$ are equivalent (provided $G \cong H$) because,
- they can be transformed into one another by a combination of elementary row/column operations
- $Rank(P_G) = Rank(P_H)$
Note that these matrices will not be equivalent if $G \ncong H$ however the converse is not true (Question: Is this correct?).
Each path is a tuple $\langle v_{start}, v_{end}, length_{start,end} \rangle$.
We can expand this into the tuple $\langle v_{start}, v_{end}, d_{start}, d_{end}, length_{start,end} \rangle$ where $d_i$ is the degree of vertex labeled $i$.
We now assign each vertex a color. The color is an integer chosen from a pre-computed table of primes. The color assignment is done as $Prime(d_i)$ for vertex labeled $v_i$ and $Prime(n)$ gives the $n$th prime.
In $P_G$ and $P_H$, we replace the path length entries with $color_{row} \times color_{col} \times Prime(length_{row, col})$
We now have canonical labeling of the paths that is a function of the start vertex's degree, end vertex's degree and unit path length connecting the two. What we still don't know is that when run on two different graphs, we may have multiple shortest paths (of the same length). We can disambiguate them only if we had canonical labels on the vertices as well. Although we have the vertex color, let us do one more thing to get a canonical vertex label.
What we have is a canonical vertex color that is a function of the vertex degree. We also have canonical paths to other vertices on the graph. So, lets go back to matrices $P_G$ and $P_H$ and compute the product of non-zero column entries for each row. This gives us an integer for each vertex that is a function of its color and all the paths to other vertices in the graph. We call this the canonical vertex label.
Now we can group the vertices into equivalence classes within the same graph based on their canonical vertex label and assign the canonical label for the class (same as the canonical label of any vertex in the class).
We can then compute the isomorphism between $G$ and $H$ by mapping members of the set of equivalence classes in $G$ with members of the set of equivalence classes in $H$ using their canonical class label. If there are equivalence classes that don't have a corresponding match, the graphs are non-isomorphic.
I know this is not a complete proof and there are gaps. The questions I have are:
- Does this have a chance of working? What are the obstacles?
- Are there counterexamples of non-isomorphic graphs that will cause this to fail? I am going based on what I read about color refinement algorithm:
However, color refinement sometimes fails to distinguish non-isomorphic graphs. The simplest example is given by any two non-isomorphic regular graphs of the same degree with the same number of vertices.
V. Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky. Graph Isomorphism, Color Refinement, and Compactness. URL: https://arxiv.org/pdf/1502.01255.pdf
- In theory, we can also check by applying a series of row/column transformation operations and transform the canonical $P_G$ to canonical $P_H$ i.e., test matrix equivalence $canonical P_G \equiv canonical P_H$. (My matrix algebra is a bit rusty and I have no idea what the complexity of this would be).
First of all, this doesn't work.
For example, in any strongly-regular graph, all vertices will have the same label. (This would even be true for any regular graph of diameter $2$.) If the strongly regular graph is $k$-regular, then each vertex has $k$ shortest paths of length $1$ and $n-k-1$ shortest paths of length $2$. Each path gets label either $p_k \times p_k \times p_1 = 2 p_k^2$ or $p_k \times p_k \times p_2 = 3p_k^2$, and so each canonical vertex label is $(2p_k^2)^k (3pk_2)^{n-k-1}$.
Just take any two strongly-regular graphs with the same degree and number of vertices, and you'll get a counterexample.
Second, you shouldn't expect this to work even if you don't have an explicit counterexample. Lots of people have tried the general technique of "label each vertex with (insert vertex property here)" and nobody has thought of anything that works. The more you refine your labeling, the harder it is to describe a counterexample, but plenty of counterexamples still exist.
(The counterexamples will all tend to be highly symmetric. But that's not interesting, because existing graph isomorphism algorithms are already very efficient on graphs that aren't highly symmetric.)
For your final bullet point, if by matrix equivalence you mean equivalence up to permuting the rows and columns by the same permutation, then this will check for isomorphism, because that's exactly the brute-force check for automorphisms: your matrices include all the data of the adjacency matrices. But it won't be efficient.
If by matrix equivalence you mean diagonalizing and looking at eigenvalues, then take my previous counterexample and ask for the two strongly-regular graphs to be cospectral - that is, have the same strong regularity parameters.