TY - GEN
T1 - Spectrally robust graph isomorphism
AU - Kolla, Alexandra
AU - Koutis, Ioannis
AU - Madan, Vivek
AU - Sinop, Ali Kemal
N1 - Funding Information:
1 Supported by NSF CAREER grant CCF-1452923. 2 Supported by NSF CAREER grant CCF-1319376.
Funding Information:
Supported by NSF CAREER grant CCF-1452923. 2 Supported by NSF CAREER grant CCF-1319376.
Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2018/7/1
Y1 - 2018/7/1
N2 - 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.
AB - 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.
KW - Graph isomorphism
KW - Graph similarity
KW - Network alignment
UR - http://www.scopus.com/inward/record.url?scp=85049782838&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85049782838&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2018.84
DO - 10.4230/LIPIcs.ICALP.2018.84
M3 - Conference contribution
AN - SCOPUS:85049782838
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
A2 - Kaklamanis, Christos
A2 - Marx, Daniel
A2 - Chatzigiannakis, Ioannis
A2 - Sannella, Donald
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Y2 - 9 July 2018 through 13 July 2018
ER -