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 $\pi$ such that $G⪯\pi (H)$? (b) The Spectrally Robust Graph Isomorphism (SRGI) problem: On input of two graphs $G$ and $H$, find the smallest number $\kappa$ over all permutations $\pi$ such that $\pi (H)⪯G⪯\kappa c\pi (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⪯cH$ means that for all vectors $x$ we have $x^T{L}_{G}x\le c{x}^T{L}_{H}x$, where $L_G$ is the Laplacian $G$. We prove NP-hardness for SGD. We also present a $\kappa$-approximation algorithm for SRGI for the case when both $G$ and $H$ are bounded-degree trees. The algorithm runs in polynomial time when $\kappa$ is a constant.

Extended version of a paper appearing in the proceedings of ICALP 2018