Graph isomorphism problem

The goal is to determine whether two undirected weighted graphs are isomorphic using spectral information. Efficient algorithms for the solution of the graph isomorphism or graph matching problem are required in a wide variety of different areas such as pattern recognition, object detection, face recognition, and fingerprint analysis. There exists no polynomial-time algorithm to check whether two arbitrary graphs are isomorphic. The graph isomorphism problem is one of only a few problems for which the complexity class is still unknown.

Two graphs $G_A =(V_A, E_A)$ and $G_B = (V_B, E_B)$ with adjacency matrices $A$ and $B$ are said to be isomorphic if one of the following equivalent conditions is satisfied:

There exists a permutation $\pi \in \mathcal{S}_n$ such that $(v_i, v_j) \in E_A \iff (v_{\pi(i)}, v_{\pi(j)}) \in E_B$ , where $\mathcal{S}_n$ denotes the symmetric group of degree $n$ .
There exists a permutation matrix $P \in \mathcal{P}_n$ such that $B = P^T A P$ , where $\mathcal{P}_n$ is the set of all $n \times n$ permutation matrices.