Document Open Access Logo

Relaxations of Graph Isomorphism

Authors Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, Antonios Varvitsiotis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.76.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Laura Mancinska
David E. Roberson
Robert Samal
Simone Severini
Antonios Varvitsiotis

Cite As Get BibTex

Laura Mancinska, David E. Roberson, Robert Samal, Simone Severini, and Antonios Varvitsiotis. Relaxations of Graph Isomorphism. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 76:1-76:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.76

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.

Subject Classification

Keywords
  • graph isomorphism
  • quantum information
  • semidefinite programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alex Arkhipov. Extending and characterizing quantum magic games, 2012. URL: http://arxiv.org/abs/1209.3819.
  2. Albert Atserias, Andrei Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666-1683, 2009. A preliminary version appeared in ICALP 2007. URL: http://dx.doi.org/10.1016/j.tcs.2008.12.049.
  3. Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms, 2016. URL: https://arxiv.org/abs/1611.09837, URL: http://arxiv.org/abs/1611.09837.
  4. László Babai. Automorphism groups, isomorphism, reconstruction. In Handbook of Combinatorics (Vol. 2), pages 1447-1540. MIT Press, 1995. URL: http://dx.doi.org/233228.233236.
  5. László Babai. Graph isomorphism in quasipolynomial time, 2015. URL: http://arxiv.org/abs/1512.03547.
  6. László Babai, Paul Erdős, and Stanley M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9(3):628-635, 1980. URL: http://dx.doi.org/10.1137/0209047.
  7. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. URL: http://dx.doi.org/10.1007/BF01305232.
  8. Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph. Electronic Journal of Combinatorics, 14(1), 2007. URL: http://arxiv.org/abs/quant-ph/0608016.
  9. Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, ICALP'14, pages 320-331. Springer, 2014. URL: http://arxiv.org/abs/1209.2729.
  10. Uriel Feige, Shafi Goldwasser, László Lovász, S. Safra, and M. Szegedy. Approximating clique is almost NP-complete (preliminary version). In Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, SFCS'91, pages 2-12, 1991. URL: http://dx.doi.org/10.1109/SFCS.1991.185341.
  11. Luuk Gijben. On approximations, complexity, and applications for copositive programming. PhD thesis, 2015. Google Scholar
  12. Martin Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Draft manuscript, 2013. URL: https://www.lii.rwth-aachen.de/en/13-mitarbeiter/professoren/39-book-descriptive-complexity.html.
  13. Monique Laurent and Teresa Piovesan. Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. SIAM Journal on Optimization, 25(4):2461-2493, 2015. URL: http://dx.doi.org/10.1137/14097865X.
  14. Laura Mančinska and David E. Roberson. Quantum homomorphisms. Journal of Combinatorial Theory, Series B, 118:228-267, 2016. URL: http://arxiv.org/abs/1212.1724.
  15. Laura Mančinska, David E. Roberson, and Antonios Varvisotis. On deciding the existence of perfect entangled strategies for nonlocal games. Chicago Journal of Theoretical Computer Science, 2016(5), 2016. URL: http://arxiv.org/abs/1506.07429.
  16. Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. Semidefinite relaxations of (quantum) graph isomorphism. https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnxkYXZpZGVyb2JlcnNvbnxneDo1OGUyM2ZlMDQ1YTZlNTI3, 2017.
  17. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. Journal of Symbolic Computation, 60:94-112, 2014. URL: http://arxiv.org/abs/1301.1493.
  18. Benjamin Musto and Jamie Vicary. Quantum Latin squares and unitary error bases, 2015. URL: http://arxiv.org/abs/1504.02715.
  19. Ryan O'Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of Robust Graph Isomorphism,Lasserre Gaps, and Asymmetry of Random Graphs, pages 1659-1677. ACM/SIAM, 2014. http://arxiv.org/abs/1401.2436, URL: http://dx.doi.org/10.1137/1.9781611973402.120.
  20. Carlos M. Ortiz and Vern I. Paulsen. Quantum graph homomorphisms via operator systems. Linear Algebra and its Applications, 497:23-43, 2016. URL: http://arxiv.org/abs/1505.00483.
  21. Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, and Andreas Winter. Estimating quantum chromatic numbers. Journal of Functional Analysis, 270(6):2188-2222, 2016. URL: http://arxiv.org/abs/1407.6918.
  22. Motakuri V. Ramana, Edward R. Scheinerman, and Daniel Ullman. Fractional isomorphism of graphs. Discrete Mathematics, 132(1):247-265, 1994. URL: http://dx.doi.org/10.1016/0012-365X(94)90241-0.
  23. David E. Roberson. Variations on a Theme: Graph Homomorphisms. PhD thesis, University of Waterloo, 2013. Google Scholar
  24. David E. Roberson. Conic formulations of graph homomorphisms. Journal of Algebraic Combinatorics, pages 1-37, 2016. http://arxiv.org/abs/1411.6723, URL: http://dx.doi.org/10.1007/s10801-016-0665-y.
  25. Jamie Sikora and Antonios Varvitsiotis. Linear conic formulations for two-party correlations and values of nonlocal games. Mathematical Programming, pages 1-33, 2015. URL: http://arxiv.org/abs/1506.07297.
  26. Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241-272, 2003. URL: http://dx.doi.org/10.1016/S0024-3795(03)00483-X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact