[Solved]: Does spectral graph theory say anything about graph isomorphism

Problem Detail: 

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?

Asked By : user13675

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/25988

3.2K people like this

 Download Related Notes/Documents