Graph isomorphism: physical resources, optimization models, and algebraic characterizations. (English) Zbl 1536.05323
Summary: In the \((G, H)\)-isomorphism game, a verifier interacts with two non-communicating players (called provers), by privately sending each of them a random vertex from either \(G\) or \(H\). The goal of the players is to convince the verifier that the graphs \(G\) and \(H\) are isomorphic. In recent work along with A. Atserias et al. [J. Comb. Theory, Ser. B 136, 289–328 (2019; Zbl 1414.05197)] we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In this paper we model classical and quantum graph isomorphism by linear constraints over certain complicated convex cones, which we then relax to a pair of tractable convex models (semidefinite programs). Our main result is a complete algebraic characterization of the corresponding equivalence relations on graphs in terms of appropriate matrix algebras. Our techniques are an interesting mix of algebra, combinatorics, optimization, and quantum information.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 91A43 | Games involving graphs |
| 91A05 | 2-person games |
| 81P45 | Quantum information, communication, networks (quantum-theoretic aspects) |
| 90C22 | Semidefinite programming |
| 90C25 | Convex programming |
Citations:
Zbl 1414.05197References:
| [1] | Atserias, A.; Mančinska, L.; Roberson, DE; Šámal, R.; Varvitsiotis, A., Quantum and non-signalling graph isomorphisms, J. Comb. Theory Ser. B, 136, 89-328, 2019 · Zbl 1414.05197 · doi:10.1016/j.jctb.2018.11.002 |
| [2] | Brouwer, AE; Cohen, AM; Neumaier, A., Distance-Regular Graphs, 1989, Berlin: Springer, Berlin · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [3] | Brouwer, AE; Haemers, WH, Spectra of Graphs, 2011, Berlin: Springer, Berlin |
| [4] | Brown, NP; Ozawa, N., C*-Algebras and Finite-Dimensional Approximations, 2008, London: American Mathematical Society, London · Zbl 1160.46001 · doi:10.1090/gsm/088 |
| [5] | Burer, S., On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495, 2009 · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z |
| [6] | Choi, M-D, Completely positive linear maps on complex matrices, Linear Algebra Appl., 10, 3, 285-290, 1975 · Zbl 0327.15018 · doi:10.1016/0024-3795(75)90075-0 |
| [7] | de Klerk, E.; Pasechnik, D., Approximation of the stability number of a graph via copositive programming, SIAM J. Optim., 12, 4, 875-892, 2002 · Zbl 1035.90058 · doi:10.1137/S1052623401383248 |
| [8] | Dukanovic, I.; Rendl, F., Copositive programming motivated bounds on the stability and the chromatic numbers, Math. Program., 121, 2, 249-268, 2010 · Zbl 1194.90109 · doi:10.1007/s10107-008-0233-x |
| [9] | Friedland, S., Coherent algebras and the graph isomorphism problem, Discrete Appl. Math., 25, 1-2, 73-98, 1989 · Zbl 0704.05023 · doi:10.1016/0166-218X(89)90047-4 |
| [10] | Gärtner, B.; Matousek, J., Approximation Algorithms and Semidefinite Programming, 2012, Berlin: Springer, Berlin · Zbl 1257.90001 · doi:10.1007/978-3-642-22015-9 |
| [11] | Gijben, L.: On approximations, complexity, and applications for copositive programming. Ph.D. thesis, University of Groningen (2015) |
| [12] | Hoffman, AJ, On the polynomial of a graph, Am. Math. Mon., 70, 1, 30-36, 1963 · Zbl 0112.14901 · doi:10.1080/00029890.1963.11990038 |
| [13] | Imrich, W.; Hammack, RH; Klavžar, S., Handbook of Product Graphs, 2011, Boca Raton: CRC Press, Boca Raton · Zbl 1283.05001 |
| [14] | Kozen, D., A clique problem equivalent to graph isomorphism, ACM SIGACT News, 10, 50-52, 1978 · Zbl 0395.68056 · doi:10.1145/990524.990529 |
| [15] | Lasserre, JB, Moments, Positive Polynomials and Their Applications, 2009, Singapore: World Scientific, Singapore · doi:10.1142/p665 |
| [16] | Laurent, M.; Piovesan, T., Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone, SIAM J. Optim., 25, 4, 2461-2493, 2015 · Zbl 1329.15066 · doi:10.1137/14097865X |
| [17] | Mančinska, L., Roberson, D.E.: Note on the correspondence between quantum correlations and the completely positive semidefinite cone (2014). http://quantuminfo.quantumlah.org/memberpages/laura/corr.pdf |
| [18] | Mančinska, L., Roberson, D.E.: Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs (2019). arXiv:1910.06958 |
| [19] | Nielsen, MA; Chuang, IL, Quantum Computation and Quantum Information, 2010, Cambridge: Cambridge University Press, Cambridge · Zbl 1288.81001 |
| [20] | Ortiz, CM; Paulsen, VI, Quantum graph homomorphisms via operator systems, Linear Algebra Appl., 497, 23-43, 2016 · Zbl 1353.46041 · doi:10.1016/j.laa.2016.02.019 |
| [21] | Roberson, D.E.: Variations on a theme: graph homomorphisms. Ph.D. thesis, University of Waterloo (2013) |
| [22] | Roberson, DE, Conic formulations of graph homomorphisms, J. Algebr. Combin., 43, 4, 877-913, 2016 · Zbl 1339.05401 · doi:10.1007/s10801-016-0665-y |
| [23] | Schrijver, A., A comparison of the Delsarte and Lovász bounds, IEEE Trans. Inf. Theory, 25, 425-429, 1979 · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072 |
| [24] | Sikora, J.; Varvitsiotis, A., Linear conic formulations for two-party correlations and values of nonlocal games, Math. Program., 162, 1-2, 431-463, 2017 · Zbl 1358.90091 · doi:10.1007/s10107-016-1049-8 |
| [25] | Slofstra, W.: The set of quantum correlations is not closed. In: Forum of Mathematics, Pi, vol. 7 (2019) · Zbl 1405.81021 |
| [26] | Watrous, J., The Theory of Quantum Information, 2018, Cambridge: Cambridge University Press, Cambridge · Zbl 1393.81004 · doi:10.1017/9781316848142 |
| [27] | Weisfeiler, B.: On construction and identification of graphs, volume 558 of Lecture Notes in Mathematics. Springer (1976). With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler · Zbl 0366.05019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
