Document Open Access Logo

Monotone Arithmetic Complexity of Graph Homomorphism Polynomials

Authors Balagopal Komarath, Anurag Pandey, Chengot Sankaramenon Rahul

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.83.pdf
  • Filesize: 0.69 MB
  • 20 pages

Document Identifiers

Author Details

Balagopal Komarath
  • Indian Institute of Technology Gandhinagar, India
Anurag Pandey
  • Department of Computer Science, Universität des Saarlances, Saarland Informatics Campus, Saarbrücken, Germany
Chengot Sankaramenon Rahul
  • School of Mathematics and Computer Science, Indian Institute of Technology Goa, India

Acknowledgements

We thank Christian Engels and Marc Roth for bringing missing and incorrect references to our attention. We thank Markus Bläser for valuable discussions. We also thank anonymous reviewers for their valuable comments on the draft that helped improve the presentation of our results.

Cite AsGet BibTex

Balagopal Komarath, Anurag Pandey, and Chengot Sankaramenon Rahul. Monotone Arithmetic Complexity of Graph Homomorphism Polynomials. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.83

Abstract

We study homomorphism polynomials, which are polynomials that enumerate all homomorphisms from a pattern graph H to n-vertex graphs. These polynomials have received a lot of attention recently for their crucial role in several new algorithms for counting and detecting graph patterns, and also for obtaining natural polynomial families which are complete for algebraic complexity classes VBP, VP, and VNP. We discover that, in the monotone setting, the formula complexity, the ABP complexity, and the circuit complexity of such polynomial families are exactly characterized by the treedepth, the pathwidth, and the treewidth of the pattern graph respectively. Furthermore, we establish a single, unified framework, using our characterization, to collect several known results that were obtained independently via different methods. For instance, we attain superpolynomial separations between circuits, ABPs, and formulas in the monotone setting, where the polynomial families separating the classes all correspond to well-studied combinatorial problems. Moreover, our proofs rediscover fine-grained separations between these models for constant-degree polynomials.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Computational complexity and cryptography
  • Theory of computation → Circuit complexity
  • Theory of computation → Parameterized complexity and exact algorithms
  • Mathematics of computing → Graph algorithms
Keywords
  • Homomorphism polynomials
  • Monotone complexity
  • Algebraic complexity
  • Graph algorithms
  • Fine-grained complexity
  • Fixed-parameter algorithms and complexity
  • Treewidth
  • Pathwidth
  • Treedepth
  • Graph homomorphisms
  • Algebraic circuits
  • Algebraic branching programs
  • Algebraic formulas

Metrics

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

Related Versions

References

  1. Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and Süleyman Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. In Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada, July 19-23, 2008, pages 241-249, 2008. URL: https://doi.org/10.1093/bioinformatics/btn163.
  2. Walter Baur and Volker Strassen. The complexity of partial derivatives. Theor. Comput. Sci., 22:317-330, 1983. URL: https://doi.org/10.1016/0304-3975(83)90110-X.
  3. Markus Bläser, Balagopal Komarath, and Karteek Sreenivasaiah. Graph pattern polynomials. In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 18:1-18:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.18.
  4. C. Borgelt and M. R. Berthold. Mining molecular fragments: finding relevant substructures of molecules. In 2002 IEEE International Conference on Data Mining, 2002. Proceedings., pages 51-58, 2002. Google Scholar
  5. 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. Springer, 2006. Google Scholar
  6. Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman. Monotone circuit lower bounds from robust sunflowers. In LATIN 2020: Theoretical Informatics: 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, pages 311-322, 2021. URL: https://doi.org/10.1007/978-3-030-61792-9_25.
  7. Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. Negations provide strongly exponential savings. Electron. Colloquium Comput. Complex., page 191, 2020. URL: https://eccc.weizmann.ac.il/report/2020/191.
  8. Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay. Lower Bounds for Monotone Arithmetic Circuits via Communication Complexity, pages 786-799. Association for Computing Machinery, New York, NY, USA, 2021. URL: https://doi.org/10.1145/3406325.3451069.
  9. Prasad Chaugule, Nutan Limaye, and Aditya Varre. Variants of homomorphism polynomials complete for algebraic complexity classes. In Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings, volume 11653 of Lecture Notes in Computer Science, pages 90-102. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_8.
  10. F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs. Combinatorica, 9(4):345-362, 1989. URL: https://doi.org/10.1007/BF02125347.
  11. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 210-223. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055502.
  12. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. Theoret. Comput. Sci., 329(1-3):315-323, 2004. URL: https://doi.org/10.1016/j.tcs.2004.08.008.
  13. Josep Díaz, Maria J. Serna, and Dimitrios M. Thilikos. Counting h-colorings of partial k-trees. Theor. Comput. Sci., 281(1-2):291-309, 2002. URL: https://doi.org/10.1016/S0304-3975(02)00017-8.
  14. R. Diestel. Graph Theory. Electronic library of mathematics. Springer, 2006. URL: https://books.google.de/books?id=aR2TMYQr2CMC.
  15. Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, and Nitin Saurabh. Homomorphism polynomials complete for VP. Chic. J. Theor. Comput. Sci., 2016, 2016. URL: http://cjtcs.cs.uchicago.edu/articles/2016/3/contents.html.
  16. Christian Engels. Dichotomy theorems for homomorphism polynomials of graph classes. Journal of Graph Algorithms and Applications, 20(1):3-22, 2016. URL: https://doi.org/10.7155/jgaa.00382.
  17. Peter Floderus, Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Detecting and counting small pattern graphs. SIAM J. Discrete Math., 29(3):1322-1339, 2015. URL: https://doi.org/10.1137/140978211.
  18. Hervé Fournier, Guillaume Malod, Maud Szusterman, and Sébastien Tavenas. Nonnegative Rank Measures and Monotone Algebraic Branching Programs. In Arkadev Chattopadhyay and Paul Gastin, editors, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1-15:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.15.
  19. Bruno Grenet. An upper bound for the permanent versus determinant problem, 2012. Google Scholar
  20. Pavel Hrubes and Amir Yehudayoff. On isoperimetric profiles and computational complexity. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 89:1-89:12, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.89.
  21. Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semirings. J. ACM, 29(3):874-897, July 1982. URL: https://doi.org/10.1145/322326.322341.
  22. Stasys Jukna. Lower bounds for monotone counting circuits. Discrete Applied Mathematics, 213:139-152, 2016. Google Scholar
  23. Ton Kloks, Dieter Kratsch, and Haiko Müller. Finding and counting small induced subgraphs efficiently. Inf. Process. Lett., 74(3-4):115-121, 2000. URL: https://doi.org/10.1016/S0020-0190(00)00047-8.
  24. Xiangnan Kong, Jiawei Zhang, and Philip S. Yu. Inferring anchor links across multiple heterogeneous social networks. In Proceedings of the 22nd ACM International Conference on Information & Knowledge Management, CIKM '13, pages 179-188, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2505515.2505531.
  25. Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and detecting small subgraphs via equations. SIAM J. Discrete Math., 27(2):892-909, 2013. URL: https://doi.org/10.1137/110859798.
  26. Deepanshu Kush and Benjamin Rossman. Tree-depth and the formula complexity of subgraph isomorphism. CoRR, abs/2004.13302, 2020. URL: http://arxiv.org/abs/2004.13302.
  27. Yuan Li, Alexander A. Razborov, and Benjamin Rossman. On the ac^0 complexity of subgraph isomorphism. SIAM J. Comput., 46(3):936-971, 2017. URL: https://doi.org/10.1137/14099721X.
  28. Xin Liu, Haojie Pan, Mutian He, Yangqiu Song, Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pages 1959-1969, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3394486.3403247.
  29. László Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012. URL: https://doi.org/10.1090/coll/060.
  30. László Lovász and Vera T. Sós. Generalized quasirandom graphs. J. Combin. Theory Ser. B, 98(1):146-163, 2008. URL: https://doi.org/10.1016/j.jctb.2007.06.005.
  31. Meena Mahajan and Nitin Saurabh. Some complete and intermediate polynomials in algebraic complexity theory. Theory Comput. Syst., 62(3):622-652, 2018. URL: https://doi.org/10.1007/s00224-016-9740-y.
  32. Dániel Marx. Can you beat treewidth? Theory Comput., 6:85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  33. Dániel Marx and Michal Pilipczuk. Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In Ernst W. Mayr and Natacha Portier, editors, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), STACS 2014, March 5-8, 2014, Lyon, France, volume 25 of LIPIcs, pages 542-553. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014. URL: https://doi.org/10.4230/LIPIcs.STACS.2014.542.
  34. R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824-827, 2002. URL: https://doi.org/10.1126/science.298.5594.824.
  35. Jaroslav Nešetřil and Svatopluk Poljak. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae, 026(2):415-419, 1985. URL: http://eudml.org/doc/17394.
  36. Noam Nisan. Lower bounds for non-commutative computation. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC '91, pages 410-418, New York, NY, USA, 1991. Association for Computing Machinery. URL: https://doi.org/10.1145/103418.103462.
  37. Ran Raz and Amir Yehudayoff. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. System Sci., 77(1):167-190, 2011. URL: https://doi.org/10.1016/j.jcss.2010.06.013.
  38. Benjamin Rossman. Lower bounds for subgraph isomorphism. In Proceedings of the International Congress of Mathematicians - Rio de Janeiro 2018. Vol. IV. Invited lectures, pages 3425-3446. World Sci. Publ., Hackensack, NJ, 2018. Google Scholar
  39. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. Google Scholar
  40. C.P. Schnorr. A lower bound on the number of additions in monotone computations. Theoretical Computer Science, 2(3):305-315, 1976. URL: https://doi.org/10.1016/0304-3975(76)90083-9.
  41. Marc Snir. On the size complexity of monotone formulas. In Jaco de Bakker and Jan van Leeuwen, editors, Automata, Languages and Programming, pages 621-631, Berlin, Heidelberg, 1980. Springer Berlin Heidelberg. Google Scholar
  42. Srikanth Srinivasan. Strongly exponential separation between monotone vp and monotone vnp. ACM Trans. Comput. Theory, 12(4), September 2020. URL: https://doi.org/10.1145/3417758.
  43. Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2 edition, September 2000. Google Scholar
  44. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1671-1680. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.111.
  45. Amir Yehudayoff. Separating monotone vp and vnp. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 425-429, New York, NY, USA, 2019. Association for Computing Machinery. URL: https://doi.org/10.1145/3313276.3316311.
  46. J. Zhang and G. Wu. Targeting social advertising to friends of users who have interacted with an object associated with the advertising, Dec. 15 2010. US Patent App. 12/968,786. Google Scholar
  47. Huan Zhao, Quanming Yao, Jianda Li, Yangqiu Song, and Dik Lun Lee. Meta-graph based recommendation fusion over heterogeneous information networks. In KDD, pages 635-644, 2017. URL: https://doi.org/10.1145/3097983.3098063.
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