@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",

}