Abstract

Graph Isomorphism is one of the most prominent problems in computer science, for which it is not known to be NP-complete or polynomial time solvable. More than three decades ago, Babai, Grigoryev, and Mount (STOC 1982) showed that for graphs, which only have eigenvalues of bounded multiplicity (except at most one eigenvalue), this problem is in P. Although this result has been reproved several times – with different techniques – the boundary has not been extended beyond constant eigenvalue multiplicity so far (except w.r.t.~one single eigenvalue as mentioned above, see second algorithm of Babai, Grigoryev, and Mount, STOC 1982 ).

We show that if for two graphs the sum of squares of the multiplicities corresponding to the eigenvalues with unbounded multiplicity is O(\log n / \log \log n), where n is the number of vertices, then isomorphism testing can be solved in polynomial time. In order to overcome the problems occurring in previous algorithms w.r.t. these graphs, we apply an approximative approach to obtain orthogonal transformations, which correspond to permutations of the automorphism group of such a graph and operate on the spaces of the eigenvalues with unbounded multiplicity. This approach is then coupled with an adapted version of the first algorithm of Babai, Grigoryev, and Mount. Our result and technique provide further insight into the connection between graph spectra and the Graph Isomorphism problem.