Spectrally Robust Graph Isomorphism

Abstract

We initiate the study of spectral generalizations of the graph isomorphism problem. (a) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation ? such that G ?(H)? (b) The Spectrally Robust Graph Isomorphism (?-SRGI) problem: On input of two graphs G and H, find the smallest number ? over all permutations ? such that ?(H) G ?c?(H) for some c. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. G cH means that for all vectors x we have xTLGx ? cxTLHx, where LG is the Laplacian G. We prove NP-hardness for SGD. We also present a ?3-approximation algorithm for SRGI for the case when both G and H are bounded-degree trees. The algorithm runs in polynomial time when ? is a constant. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.