Spectrally robust graph isomorphism

Alexandra Kolla, Ioannis Koutis, Vivek Madan, Ali Kemal Sinop

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/TerritoryCzech Republic
CityPrague
Period7/9/187/13/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Graph isomorphism
  • Graph similarity
  • Network alignment

Fingerprint

Dive into the research topics of 'Spectrally robust graph isomorphism'. Together they form a unique fingerprint.

Cite this