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.

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 -