Please use this identifier to cite or link to this item:
Title: Relaxations of graph isomorphism
Authors: Mančinska, Laura
Šámal, Robert
Severini, Simone
Varvitsiotis, Antonios
Roberson, David E.
Keywords: DRNTU::Science::Mathematics
Graph Isomorphism
Quantum Information
Issue Date: 2017
Source: Mancinska, L., Roberson, D. E., Samal, R., Severini, S., & Varvitsiotis, A. (2017). Relaxations of Graph Isomorphism. In LIPIcs-Leibniz International Proceedings in Informatics 80, 76-. doi: 10.4230/LIPIcs.ICALP.2017.76
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: We introduce a nonlocal game that captures and extends the notion of graph isomorphism. This game can be won in the classical case if and only if the two input graphs are isomorphic. Thus, by considering quantum strategies we are able to define the notion of quantum isomorphism. We also consider the case of more general non-signalling strategies, and show that such a strategy exists if and only if the graphs are fractionally isomorphic. We prove several necessary conditions for quantum isomorphism, including cospectrality, and provide a construction for producing pairs of non-isomorphic graphs that are quantum isomorphic. We then show that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively. This leads us to considering relaxations of (quantum) isomorphism arrived at by relaxing the cone to either the doubly nonnegative (DNN) or positive semidefinite (PSD) cones. We show that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomial-time decidable relation that is related to coherent algebras. We also show that PSD-isomorphism implies several types of cospectrality, and that it is equivalent to cospectrality for connected 1-walk-regular graphs. Finally, we show that all of the above mentioned relations form a strict hierarchy of weaker and weaker relations, with non-singalling/fractional isomorphism being the weakest. The techniques used are an interesting mix of algebra, combinatorics, and quantum information.
ISSN: 1868-8969
DOI: 10.4230/LIPIcs.ICALP.2017.76
Rights: © 2017 Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis; licensed under Creative Commons License CC-BY 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Editors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl; Article No. 76; pp. 76:1–76:14
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
Relaxations of Graph Isomorphism.pdf537.91 kBAdobe PDFThumbnail

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.