Document Open Access Logo

On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order

Authors J. A. Gregor Lagodzinski , Andreas Göbel , Katrin Casel , Tobias Friedrich

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.91.pdf
  • Filesize: 1.08 MB
  • 15 pages

Document Identifiers

Author Details

J. A. Gregor Lagodzinski
  • Hasso Plattner Institute, University of Potsdam, Germany
Andreas Göbel
  • Hasso Plattner Institute, University of Potsdam, Germany
Katrin Casel
  • Hasso Plattner Institute, University of Potsdam, Germany
Tobias Friedrich
  • Hasso Plattner Institute, University of Potsdam, Germany

Acknowledgements

The authors would like to thank Holger Dell for bringing [Hubie Chen et al., 2019] to their attention. Our gratitude also goes to Jacob Focke and Marc Roth for their valuable insights on partially surjective homomorphisms and for pointing out a mistake in a previous version.

Cite AsGet BibTex

J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.91

Abstract

We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph ̄{H} in any finite field of prime order ℤ_p. The subproblem with graph H was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph ̄{H} collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite (K_{3,3}$1{e}, {domino})-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with p = 2 this establishes new results.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Discrete mathematics
Keywords
  • Algorithms
  • Theory
  • Quantum Graphs
  • Bipartite Graphs
  • Graph Homomorphisms
  • Modular Counting
  • Complexity Dichotomy

Metrics

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

Related Versions

References

  1. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Counting subgraphs via homomorphisms. SIAM J. Discret. Math., 26(2):695-717, 2012. URL: https://doi.org/10.1137/100789403.
  2. Christian Borgs, Jennifer Chayes, László Lovász, Vera T. Sós, and Katalin Vesztergombi. Counting graph homomorphisms. In Topics in Discrete Mathematics, pages 315-371, 2006. URL: https://doi.org/10.1007/3-540-33700-8_18.
  3. Christian Borgs, Jennifer T. Chayes, Jeff Kahn, and László Lovász. Left and right convergence of graphs with bounded degree. Random Structures and Algorithms, 42(1):1-28, 2013. URL: https://doi.org/10.1002/rsa.20414.
  4. Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, and Katalin Vesztergombi. Graph limits and parameter testing. In Proceedings of STOC 2006, pages 261-270, 2006. URL: https://doi.org/10.1145/1132516.1132556.
  5. Graham R. Brightwell and Peter Winkler. Graph homomorphisms and phase transitions. J. Comb. Theory, Ser. B, 77(2):221-262, 1999. URL: https://doi.org/10.1006/jctb.1999.1899.
  6. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1-34:41, 2013. URL: https://doi.org/10.1145/2528400.
  7. Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148-186, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.011.
  8. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1-19:39, 2017. URL: https://doi.org/10.1145/2822891.
  9. Jin-Yi Cai, Xi Chen, and Pinyan Lu. Graph homomorphisms with complex values: A dichotomy theorem. SIAM J. Comput., 42(3):924-1029, 2013. URL: https://doi.org/10.1137/110840194.
  10. Jin-Yi Cai and Artem Govorov. Perfect matchings, rank of connection tensors and graph homomorphisms. In Proceedings of SODA 2019, pages 476-495, 2019. URL: https://doi.org/10.1137/1.9781611975482.30.
  11. Ashok K. Chandra and Philip M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of STOC 1977, pages 77-90, 1977. URL: https://doi.org/10.1145/800105.803397.
  12. Hubie Chen, Radu Curticapean, and Holger Dell. The exponential-time complexity of counting (quantum) graph homomorphisms. In Proceedings of WG 2019, pages 364-378, 2019. URL: https://doi.org/10.1007/978-3-030-30786-8_28.
  13. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of STOC 2017, page 210–223, 2017. URL: https://doi.org/10.1145/3055399.3055502.
  14. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci., 329(1-3):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  15. Martin E. Dyer, Leslie Ann Goldberg, and Mike Paterson. On counting homomorphisms to directed acyclic graphs. J. ACM, 54(6):27, 2007. URL: https://doi.org/10.1145/1314690.1314691.
  16. Martin E. Dyer and Catherine Greenhill. The complexity of counting graph homomorphisms. Random Structures and Algorithms, 17(3-4):260-289, 2000. URL: https://doi.org/10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO;2-W.
  17. Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245-1274, 2013. URL: https://doi.org/10.1137/100811258.
  18. Josep Díaz, Maria Serna, and Dimitrios M. Thilikos. Counting H-colorings of partial k-trees. Theor. Comput. Sci., 281(1):291-309, 2002. Selected Papers in honour of Maurice Nivat. URL: https://doi.org/10.1016/S0304-3975(02)00017-8.
  19. Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. Beyond triangles: A distributed framework for estimating 3-profiles of large graphs. In Proceedings of KDD 2015, pages 229-238, 2015. URL: https://doi.org/10.1145/2783258.2783413.
  20. Ethan R. Elenberg, Karthikeyan Shanmugam, Michael Borokhovich, and Alexandros G. Dimakis. Distributed estimation of graph 4-profiles. In Proceedings of WWW 2016, pages 483-493, 2016. URL: https://doi.org/10.1145/2872427.2883082.
  21. John Faben and Mark Jerrum. The complexity of parity graph homomorphism: An initial investigation. Theory of Computing, 11:35-57, 2015. URL: https://doi.org/10.4086/toc.2015.v011a002.
  22. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  23. Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Zivný. Counting homomorphisms to K_4-minor-free graphs, modulo 2. In Proceedings of SODA 2021, pages 2303-2314, 2021. URL: https://doi.org/10.1137/1.9781611976465.137.
  24. Jacob Focke, Leslie Ann Goldberg, and Stanislav Zivný. The complexity of counting surjective homomorphisms and compactions. SIAM J. Discret. Math., 33(2):1006-1043, 2019. URL: https://doi.org/10.1137/17M1153182.
  25. Andreas Galanis, Leslie Ann Goldberg, and Mark Jerrum. Approximately counting H-colorings is #BIS-hard. SIAM J. Comput., 45(3):680-711, 2016. URL: https://doi.org/10.1137/15M1020551.
  26. Andreas Göbel, Leslie Ann Goldberg, and David Richerby. The complexity of counting homomorphisms to cactus graphs modulo 2. ACM Trans. Comput. Theory, 6(4):17:1-17:29, 2014. URL: https://doi.org/10.1145/2635825.
  27. Andreas Göbel, Leslie Ann Goldberg, and David Richerby. Counting homomorphisms to square-free graphs, modulo 2. ACM Trans. Comput. Theory, 8(3):12:1-12:29, 2016. URL: https://doi.org/10.1145/2898441.
  28. Andreas Göbel, J. A. Gregor Lagodzinski, and Karen Seidel. Counting homomorphisms to trees modulo a prime. In Proceedings of MFCS 2018, pages 49:1-49:13, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.49.
  29. Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley. A complexity dichotomy for partition functions with mixed signs. SIAM J. Comput., 39(7):3336-3402, 2010. URL: https://doi.org/10.1137/090757496.
  30. Leslie Ann Goldberg and Mark Jerrum. The complexity of approximately counting tree homomorphisms. ACM Trans. Comput. Theory, 6(2):8:1-8:31, 2014. URL: https://doi.org/10.1145/2600917.
  31. Artem Govorov, Jin-Yi Cai, and Martin E. Dyer. A dichotomy for bounded degree graph homomorphisms with nonnegative weights. In Proceedings of ICALP 2020, pages 66:1-66:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.66.
  32. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1-1:24, 2007. URL: https://doi.org/10.1145/1206035.1206036.
  33. Martin Grohe, Thomas Schwentick, and Luc Segoufin. When is the evaluation of conjunctive queries tractable? In Proceedings of STOC 2001, pages 657-666, 2001. URL: https://doi.org/10.1145/380752.380867.
  34. Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The complexity of weighted boolean #csp modulo k. In Proceedings of STACS 2011, pages 249-260, 2011. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.249.
  35. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: https://doi.org/10.1016/0095-8956(90)90132-J.
  36. Amirhossein Kazeminia and Andrei A. Bulatov. Counting homomorphisms modulo a prime number. In Proceedings of MFCS 2019, pages 59:1-59:13, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.59.
  37. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975. URL: https://doi.org/10.1145/321864.321877.
  38. László Lovász. Large Networks and Graph Limits, volume 60 of Colloquium Publications. AMS, 2012. URL: http://www.ams.org/bookstore-getitem/item=COLL-60.
  39. Benjamin Rossman. Homomorphism preservation theorems. J. ACM, 55(3):15:1-15:53, 2008. URL: https://doi.org/10.1145/1379759.1379763.
  40. Benjamin Rossman. An improved homomorphism preservation theorem from lower bounds in circuit complexity. In Proceedings of ITCS 2017, pages 27:1-27:17, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.27.
  41. Marc Roth and Philip Wellnitz. Counting and finding homomorphisms is universal for parameterized complexity theory. In Proceedings of SODA 2020, pages 2161-2180, 2020. URL: https://doi.org/10.1137/1.9781611975994.133.
  42. Shahab Shams, Nicholas Ruozzi, and Peter Csikvári. Counting homomorphisms in bipartite graphs. In Proceedings of ISIT 2019, pages 1487-1491, 2019. URL: https://doi.org/10.1109/ISIT.2019.8849389.
  43. Alexander F. Sidorenko. Inequalities for functionals generated by bipartite graphs. (Russian) Diskret. Mat, 3(3):50-65, 1991. Google Scholar
  44. Alexander F. Sidorenko. A correlation inequality for bipartite graphs. Graphs and Combin., 9(2-4):201-204, 1993. URL: https://doi.org/10.1007/BF02988307.
  45. Miklós Simonovits. Extremal graph problems, degenerate extremal problems,and supersaturated graphs. Progress in Graph Theory, page 419–437, 1984. Google Scholar
  46. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: https://doi.org/10.1137/0220053.
  47. Johan Ugander, Lars Backstrom, and Jon M. Kleinberg. Subgraph frequencies: mapping the empirical and extremal geography of large graph collections. In Proceedings of WWW 2013, pages 1307-1318, 2013. URL: https://doi.org/10.1145/2488388.2488502.
  48. Leslie G. Valiant. Accidental algorithms. In Proceedings of FOCS 2006, pages 509-517, 2006. URL: https://doi.org/10.1109/FOCS.2006.7.
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 Imprint Privacy Contact