2014/11/30 by Stefan Klus, Tuhin Sahai
Computer Science · #Adjacency list #Adjacency matrix #Advanced Graph Theory Research #Chordal graph #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #Graph homomorphism #Graph isomorphism #Heuristic #Indifference graph #Isospectral #Pathwidth #cs.DM #msc:05C50 #msc:05C60
paper · pdf · doi:10.1093/imaiai/iay001
openalex created_date 2016/06/24 · arxiv created 2017/12/19 · openalex publication_date 2018/01/19 · arxiv updated 2019/08/14 · openalex updated_date 2026/08/05
In this paper, we propose algorithms for the graph isomorphism (GI) problem that are based on the eigendecompositions of the adjacency matrices. The eigenvalues of isomorphic graphs are identical. However, two graphs GA and GB can be isospectral but non-isomorphic. We first construct a GI testing algorithm for friendly graphs and then extend it to unambiguous graphs. We show that isomorphisms can be detected by solving a linear assignment problem (LAP). If the graphs possess repeated eigenvalues, which typically correspond to graph symmetries, finding isomorphisms is much harder. By repeatedly perturbing the adjacency matrices and by using properties of eigenpolytopes, it is possible to break symmetries of the graphs and iteratively assign vertices of GA to vertices of GB, provided that an admissible assignment exists. This heuristic approach can be used to construct a permutation which transforms GA into GB if the graphs are isomorphic. The methods will be illustrated with several guiding examples.