Spectrally Robust Graph Isomorphism

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\preceq π(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) \preceq G\preceq κc π(H)$ for some $c$. SRGI is a natural formulation of the network alignment problem that has various applications, most notably in computational biology. Here $G\preceq c H$ means that for all vectors $x$ we have $x^T L_G x \leq c x^T L_H x$, where $L_G$ is the Laplacian $G$. We prove NP-hardness for SGD. We also present a $κ$-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.