License:
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.84
URN: urn:nbn:de:0030-drops-90887
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9088/
Kolla, Alexandra ;
Koutis, Ioannis ;
Madan, Vivek ;
Sinop, Ali Kemal
Spectrally Robust Graph Isomorphism
Abstract
We initiate the study of spectral generalizations of the graph isomorphism problem.
b) The Spectral Graph Dominance (SGD) problem: On input of two graphs G and H does there exist a permutation pi such that G preceq pi(H)?
c) The Spectrally Robust Graph Isomorphism (kappa-SRGI) problem: On input of two graphs G and H, find the smallest number kappa over all permutations pi such that pi(H) preceq G preceq 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.
G preceq c H means that for all vectors x we have x^T L_G x <= c x^T L_H x, where L_G is the Laplacian G.
We prove NP-hardness for SGD. We also present a kappa^3-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.
BibTeX - Entry
@InProceedings{kolla_et_al:LIPIcs:2018:9088,
author = {Alexandra Kolla and Ioannis Koutis and Vivek Madan and Ali Kemal Sinop},
title = {{Spectrally Robust Graph Isomorphism}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {84:1--84:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9088},
URN = {urn:nbn:de:0030-drops-90887},
doi = {10.4230/LIPIcs.ICALP.2018.84},
annote = {Keywords: Network Alignment, Graph Isomorphism, Graph Similarity}
}
Keywords: |
|
Network Alignment, Graph Isomorphism, Graph Similarity |
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
04.07.2018 |