@inproceedings{28f95df0f3f0421cb9fac0c51bd20706,
title = "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.",
keywords = "Graph isomorphism, Graph similarity, Network alignment",
author = "Alexandra Kolla and Ioannis Koutis and Vivek Madan and Sinop, {Ali Kemal}",
note = "Publisher Copyright: {\textcopyright} 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 ; Conference date: 09-07-2018 Through 13-07-2018",
year = "2018",
month = jul,
day = "1",
doi = "10.4230/LIPIcs.ICALP.2018.84",
language = "English (US)",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Christos Kaklamanis and Daniel Marx and Ioannis Chatzigiannakis and Donald Sannella",
booktitle = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018",
address = "Germany",
}