2026-07-23T05:31:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9088 2024-03-06T10:43:20Z ddc:004 open_access

Spectrally Robust Graph Isomorphism Kolla, Alexandra Koutis, Ioannis Madan, Vivek Sinop, Ali Kemal Network Alignment Graph Isomorphism Graph Similarity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandra Kolla and Ioannis Koutis and Vivek Madan and Ali Kemal Sinop 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.84 urn:nbn:de:0030-drops-90887 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.84 eng https://creativecommons.org/licenses/by/3.0/legalcode