Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?

Two known theorems of spectral graph theory are:

  1. Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.

  2. Almost all trees are cospectral.

  3. The eigenvalues of a graph's adjacency matrix are invariant under relabeling (but this is not a necessary and sufficient condition).

Furthermore, is graph isomorphism "easy" to solve?

  • $\begingroup$ Correct: en.wikipedia.org/wiki/Graph_isomorphism_problem... But they state that it is not known to be in NP-complete or P... $\endgroup$ – user13675 May 21 '14 at 23:42
  • 1
    $\begingroup$ By '"easy" to solve' do you mean something like, are there algorithms that work well in practice even though their worst-case complexity is bad or unknown? If so, nauty apparently does a good job in practice. $\endgroup$ – David Richerby May 21 '14 at 23:56

Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is "NP-intermediate", that is, not in P but not NP-complete. Some conjecture that it should be solvable in quasipolynomial time (algorithms running in time $2^{\log^{O(1)} n}$). The best currently known algorithm, due to Luks, has running time $2^{O(\sqrt{n\log n})}$. It uses the so-called group theory method.

The two most common approaches are individualization/refinement and the group theory method. The former approach tries to match vertices of one graph to vertices of the other. Given a vertex of degree $d$ belonging to the first graph, it can only be matches to a vertex of degree $d$ in the other graph, but this offers no saving if both graphs are $d$-regular. Individualization/refinement is a framework for generating more detailed "types" of vertices.

It is possible that a similar approach can enhance the spectral method (which as stated fails for cospectral graphs), but I am not aware of any work along these lines (though it might exist; I'm not an expert in this area).

The group theory method reduces graph isomorphism to the problem of finding generators for the automorphism groups of graphs. Given two graphs $G_1,G_2$, the idea is to compute generators for $\operatorname{Aut}(G_1 \cup G_2)$, and check whether any of them switches a vertex of $G_1$ with a vertex of $G_2$. For more details, see for example lecture notes of Arvind.

For a recent overview of the state of the art, consult a paper by Babai; Babai is one of the principle researchers in the area.

Practical graph isomorphism is a completely different issue. A recent overview can be found in a paper of McKay, author of the popular package nauty.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.