The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Authors: 
Jin-Yi Cai, Ashwin MaranAuthors Info & Claims
Pages 1285 - 1297
Abstract
We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix H defining a graph homomorphism from all planar graphs G ↦ ZH(G), we completely classify the computational complexity of this problem according to the matrix H. We show that for every H, the problem is either polynomial time computable or #P-hard. The P-time computable cases consist of precisely those that are P-time computable for general graphs (a complete classification is known) or computable by Valiant’s holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.
References
[1]
Albert Atserias, Laura Mančinska, David E Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. 2019. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136 (2019), 289–328. https://doi.org/10.1016/j.jctb.2018.11.002
[2]
Miriam Backens. 2017. A New Holant Dichotomy Inspired by Quantum Computation. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland (LIPIcs, Vol. 80). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 16:1–16:14.
[3]
Miriam Backens. 2018. A Complete Dichotomy for Complex-Valued Holantĉ. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (LIPIcs, Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12:1–12:14.
[4]
Teodor Banica. 2005. Quantum automorphism groups of homogeneous graphs. Journal of Functional Analysis, 224, 2 (2005), 243–280. https://doi.org/10.1016/j.jfa.2004.11.002
[5]
Rajendra Bhatia. 2013. Matrix analysis. 169, Springer Science & Business Media.
[6]
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, and David Richerby. 2012. The complexity of weighted and unweighted # CSP. J. Comput. System Sci., 78, 2 (2012), 681–688. https://doi.org/10.1016/j.jcss.2011.12.002
[7]
Andrei Bulatov and Martin Grohe. 2005. The complexity of partition functions. Theoretical Computer Science, 348, 2-3 (2005), 148–186. https://doi.org/10.1016/j.tcs.2005.09.011
[8]
Andrei A Bulatov. 2002. A dichotomy theorem for constraints on a three-element set. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 649–658.
[9]
Andrei A Bulatov. 2013. The complexity of the counting constraint satisfaction problem. Journal of the ACM (JACM), 60, 5 (2013), 1–41. https://doi.org/10.1145/2528400
[10]
Jin-Yi Cai and Xi Chen. 2017. Complexity of counting CSP with complex weights. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (STOC) (2012), pp. 909–920 (Journal of the ACM, Vol. 64(3)). 1–39. https://doi.org/10.1145/2213977.2214059
[11]
Jin-Yi Cai, Xi Chen, and Pinyan Lu. 2013. Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput., 42, 3 (2013), 924–1029. https://doi.org/10.1137/110840194
[12]
Jin-Yi Cai, Xi Chen, and Pinyan Lu. 2016. Nonnegative weighted # CSP: an effective complexity dichotomy. SIAM J. Comput., 45, 6 (2016), 2177–2198. https://doi.org/10.1137/15M1032314
[13]
Jin-Yi Cai and Zhiguo Fu. 2019. Holographic algorithm with Matchgates is universal for planar # CSP over boolean domain. SIAM J. Comput., 51, 2 (2019), STOC17–50. https://doi.org/10.1137/17M1131672
[14]
Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. 2022. A Holant dichotomy: is the FKT algorithm universal? In IEEE 56th Annual Symposium on Foundations of Computer Science (2015), pp. 1259–1276 (“FKT is Not Universal – A Planar Holant Dichotomy for Symmetric Constraints", Theory of Computing Systems, Vol. 66(1)). 143–308. https://doi.org/10.1007/s00224-021-10032-1
[15]
Jin-Yi Cai, Heng Guo, and Tyson Williams. 2016. A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput., 45, 5 (2016), 1671–1728. https://doi.org/10.1137/15M1049798
[16]
Jin-Yi Cai, Pinyan Lu, and Mingji Xia. 2009. Holant problems and counting CSP. In Proceedings of the forty-first annual ACM symposium on Theory of computing. 715–724. https://doi.org/10.1145/1536414.1536511
[17]
Richard Cleve, Li Liu, and William Slofstra. 2017. Perfect commuting-operator strategies for linear system games. J. Math. Phys., 58, 1 (2017), 012202. https://doi.org/10.1063/1.4973422
[18]
Martin Dyer and Catherine Greenhill. 2000. The complexity of counting graph homomorphisms (extended abstract). In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA, David B. Shmoys (Ed.). ACM/SIAM, 246–255.
[19]
Martin E Dyer and David M Richerby. 2010. On the complexity of # CSP. In Proceedings of the forty-second ACM symposium on Theory of computing. 725–734. https://doi.org/10.1145/1806689.1806789
[20]
Martin E Dyer and David M Richerby. 2011. The # CSP Dichotomy is Decidable. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Thomas Schwentick and Christoph Dürr (Eds.). 9, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 261–272. https://doi.org/10.4230/LIPIcs.STACS.2011.261
[21]
Martin E Dyer and David M Richerby. 2013. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42, 3 (2013), 1245 – 1274. https://doi.org/10.1137/100811258
[22]
Michael Freedman, László Lovász, and Alexander Schrijver. 2007. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20, 1 (2007), 37–51. https://doi.org/10.1090/S0894-0347-06-00529-7
[23]
Zhiguo Fu and Fengqin Yang. 2014. Holographic algorithms on bases of rank 2. Inform. Process. Lett., 114, 11 (2014), 585–590. https://doi.org/10.1016/j.ipl.2014.06.006
[24]
Zhiguo Fu, Fengqin Yang, and Minghao Yin. 2019. On blockwise symmetric matchgate signatures and higher domain # CSP. Information and Computation, 264 (2019), 1–11.
[25]
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. 2010. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39, 7 (2010), 3336–3402. https://doi.org/10.1137/090757496
[26]
Artem Govorov, Jin-Yi Cai, and Martin Dyer. 2023. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. J. Comput. System Sci., 132 (2023), 1–15. https://doi.org/10.1016/j.jcss.2022.09.002
[27]
Heng Guo and Tyson Williams. 2020. The complexity of planar Boolean #CSP with complex weights. J. Comput. System Sci., 107 (2020), 1–27. https://doi.org/10.1016/j.jcss.2019.07.005
[28]
Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press.
[29]
N. Jacobson. 1985. Basic Algebra (Basic Algebra). W.H. Freeman. isbn:9780716719335 lccn:84025836 https://books.google.com/books?id=oNmDSAAACAAJ
[30]
Pieter Kasteleyn. 1967. Graph theory and crystal physics. Graph theory and theoretical physics, 43–110.
[31]
Pieter W Kasteleyn. 1961. The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice. Physica, 27, 12 (1961), 1209–1225. https://doi.org/10.1016/0031-8914(61)90063-5
[32]
Pieter W Kasteleyn. 1963. Dimer statistics and phase transitions. J. Math. Phys., 4, 2 (1963), 287–293. https://doi.org/10.1063/1.1703953
[33]
László Lovász. 1967. Operations with structures. Acta Math. Acad. Sci. Hungar, 18, 3-4 (1967), 321–328. https://doi.org/10.1007/BF02280291
[34]
László Lovász. 2012. Large networks and graph limits. 60, American Mathematical Soc. https://doi.org/10.1090/coll/060
[35]
Martino Lupini, Laura Mančinska, and David E Roberson. 2020. Nonlocal games and quantum permutation groups. Journal of Functional Analysis, 279, 5 (2020), 108592. https://doi.org/10.1016/j.jfa.2020.108592
[36]
Laura Mancinska and David Roberson. 2014. Graph homomorphisms for quantum players. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014).
[37]
Laura Mančinska and David E Roberson. 2020. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). 661–672. https://doi.org/10.1109/FOCS46700.2020.00067
[38]
Benjamin Musto, David Reutter, and Dominic Verdon. 2019. The Morita theory of quantum graph isomorphisms. Communications in Mathematical Physics, 365, 2 (2019), 797–845. https://doi.org/10.1007/s00220-018-3225-6
[39]
Harold NV Temperley and Michael E Fisher. 1961. Dimer problem in statistical mechanics-an exact result. Philos. Mag., 6, 68 (1961), 1061–1063. https://doi.org/10.1080/14786436108243366
[40]
Leslie G Valiant. 1979. The complexity of computing the permanent. Theoretical computer science, 8, 2 (1979), 189–201. https://doi.org/10.1016/0304-3975(79)90044-6
[41]
Leslie G Valiant. 2008. Holographic algorithms. SIAM J. Comput., 37, 5 (2008), 1565–1594. https://doi.org/10.1137/070682575
[42]
Dirk Vertigan. 2005. The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput., 35, 3 (2005), 690–712. https://doi.org/10.1137/S0097539704446797
[43]
Peng Yang and Zhiguo Fu. 2022. Local holographic transformations: tractability and hardness. Frontiers of Computer Science, 17, 2 (2022), 1–11. https://doi.org/10.1007/s11704-022-1231-5
Index Terms
- The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3
Recommendations
The Exponential-Time Complexity of Counting (Quantum) Graph Homomorphisms
Graph-Theoretic Concepts in Computer ScienceAbstractMany graph parameters can be expressed as homomorphism counts to fixed target graphs; this includes the number of independent sets and the number of k-colorings for any fixed k. Dyer and Greenhill (RSA 2000) gave a sweeping complexity dichotomy ...
Counting Homomorphisms to Trees Modulo a Prime
Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of #pHOMSTOH, the ...
The Complexity of Planar Counting Problems
We prove the #P-hardness of the counting problems associated with various satisfiability, graph, and combinatorial problems, when restricted to planar instances. These problems include 3Sat, 1-3Sat, 1-Ex3Sat, Minimum Vertex Cover, Minimum Dominating Set,...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2023
1926 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 June 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
STOC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 85Total Downloads
- Downloads (Last 12 months)26
- Downloads (Last 6 weeks)5
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in