Document Open Access Logo

Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths

Authors Radu Curticapean , Holger Dell , Thore Husfeldt

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.34.pdf
  • Filesize: 0.86 MB
  • 17 pages

Document Identifiers

Author Details

Radu Curticapean
  • Basic Algorithm Research Copenhagen (BARC), IT University of Copenhagen, Denmark
Holger Dell
  • Goethe Universität Frankfurt, Germany
  • Basic Algorithm Research Copenhagen (BARC), IT University of Copenhagen, Denmark
Thore Husfeldt
  • Basic Algorithm Research Copenhagen (BARC), IT University of Copenhagen, Denmark
  • Lund University, Sweden

Funding

Supported by VILLUM Foundation grant 16582.

Cite AsGet BibTex

Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular Counting of Subgraphs: Matchings, Matching-Splittable Graphs, and Paths. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.34

Abstract

We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of k-matchings can be determined in polynomial time by a simple reduction to the determinant. We generalize this to an n^{f(t,s)}-time algorithm to compute modulo 2^t the number of subgraph occurrences of patterns that are s vertices away from being matchings. This shows that the known polynomial-time cases of subgraph detection (Jansen and Marx, SODA 2015) carry over into the setting of counting modulo 2^t. Complementing our algorithm, we also give a simple and self-contained proof that counting k-matchings modulo odd integers q is {Mod}_q W[1]-complete and prove that counting k-paths modulo 2 is ⊕W[1]-complete, answering an open question by Björklund, Dell, and Husfeldt (ICALP 2015).

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Counting complexity
  • matchings
  • paths
  • subgraphs
  • parameterized complexity

Metrics

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

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, 1997. URL: https://doi.org/10.1007/BF02523189.
  2. Vikraman Arvind and Venkatesh Raman. Approximation algorithms for some parameterized counting problems. In Prosenjit Bose and Pat Morin, editors, Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, volume 2518 of Lecture Notes in Computer Science, pages 453-464. Springer, 2002. URL: https://doi.org/10.1007/3-540-36136-7_40.
  3. Andreas Björklund, Holger Dell, and Thore Husfeldt. The parity of set systems under random restrictions with applications to exponential time problems. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 231-242. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47672-7_19.
  4. Andreas Björklund and Thore Husfeldt. The parity of directed Hamiltonian cycles. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 727-735. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.83.
  5. Hans L. Bodlaender. On linear time minor tests with depth-first search. Journal of Algorithms, 14(1):1-23, January 1993. URL: https://doi.org/10.1006/jagm.1993.1001.
  6. Yijia Chen, Martin Grohe, and Bingkai Lin. The hardness of embedding grids and walls. In Hans L. Bodlaender and Gerhard J. Woeginger, editors, Graph-Theoretic Concepts in Computer Science - 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, volume 10520 of Lecture Notes in Computer Science, pages 180-192. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-68705-6_14.
  7. Radu Curticapean. The simple, little and slow things count: on parameterized counting complexity. PhD thesis, Saarland University, 2015. URL: http://scidok.sulb.uni-saarland.de/volltexte/2015/6217/.
  8. 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.
  9. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 130-139. IEEE Computer Society, 2014. URL: https://doi.org/10.1109/FOCS.2014.22.
  10. Radu Curticapean and Dániel Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. CoRR, abs/1407.2929, 2014. URL: http://arxiv.org/abs/1407.2929.
  11. Radu Curticapean and Mingji Xia. Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 994-1009. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.65.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  13. 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.
  14. Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced subgraphs: An algebraic approach to #W[1]-hardness. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 26:1-26:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.26.
  15. John D. Faben. The complexity of counting solutions to generalised satisfiability problems modulo k. CoRR, abs/0809.1836, 2008. URL: http://arxiv.org/abs/0809.1836.
  16. John D. Faben and Mark Jerrum. The complexity of parity graph homomorphism: An initial investigation. Theory Comput., 11:35-57, 2015. URL: https://doi.org/10.4086/toc.2015.v011a002.
  17. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM J. Comput., 33(4):892-922, 2004. URL: https://doi.org/10.1137/S0097539703427203.
  18. Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Živný. Counting homomorphisms to K4-minor-free graphs, modulo 2. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2303-2314. Society for Industrial and Applied Mathematics, January 2021. URL: https://doi.org/10.1137/1.9781611976465.137.
  19. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, and B. V. Raghavendra Rao. Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci., 78(3):698-706, 2012. URL: https://doi.org/10.1016/j.jcss.2011.10.001.
  20. 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.
  21. 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.
  22. Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The complexity of weighted Boolean #CSP modulo k. In Thomas Schwentick and Christoph Dürr, editors, 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany, volume 9 of LIPIcs, pages 249-260. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.249.
  23. Hiroshi Hirai and Hiroyuki Namba. Shortest (a+b)-path packing via Hafnian. Algorithmica, 80(8):2478-2491, 2018. URL: https://doi.org/10.1007/s00453-017-0334-0.
  24. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(04):439-562, August 2006. URL: https://doi.org/10.1090/s0273-0979-06-01126-8.
  25. Bart M. P. Jansen and Dániel Marx. Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels. 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 616-629. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.42.
  26. Amirhossein Kazeminia and Andrei A. Bulatov. Counting homomorphisms modulo a prime number. In Peter Rossmanith, Pinar Heggernes, and Joost-Pieter Katoen, editors, 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 59:1-59:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.MFCS.2019.59.
  27. Jeong Han Kim, Benny Sudakov, and Van H. Vu. On the asymmetry of random regular graphs and random graphs. Random Struct. Algorithms, 21(3-4):216-224, 2002. URL: https://doi.org/10.1002/rsa.10054.
  28. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 575-586. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_47.
  29. Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and detecting small subgraphs via equations. SIAM J. Discret. Math., 27(2):892-909, 2013. URL: https://doi.org/10.1137/110859798.
  30. Bingkai Lin. The parameterized complexity of the k-biclique problem. J. ACM, 65(5):34:1-34:23, 2018. URL: https://doi.org/10.1145/3212622.
  31. Dániel Marx. Can you beat treewidth? Theory Comput., 6(1):85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  32. Burkhard Monien. How to find long paths efficiently. In Analysis and Design of Algorithms for Combinatorial Problems, pages 239-254. Elsevier, 1985. URL: https://doi.org/10.1016/s0304-0208(08)73110-4.
  33. Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (modular) counting and Cayley graph expanders. CoRR, abs/2104.14596, 2021. URL: http://arxiv.org/abs/2104.14596.
  34. Jürgen Plehn and Bernd Voigt. Finding minimally weighted subgraphs. In Rolf H. Möhring, editor, Graph-Theoretic Concepts in Computer Science, 16rd International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings, volume 484 of Lecture Notes in Computer Science, pages 18-29. Springer, 1990. URL: https://doi.org/10.1007/3-540-53832-1_28.
  35. Marc Roth. Counting restricted homomorphisms via Möbius inversion over matroid lattices. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, volume 87 of LIPIcs, pages 63:1-63:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.63.
  36. Marc Roth and Johannes Schmitt. Counting induced subgraphs: A topological approach to #W[1]-hardness. Algorithmica, 82(8):2267-2291, 2020. URL: https://doi.org/10.1007/s00453-020-00676-9.
  37. Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting small induced subgraphs satisfying monotone properties. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1356-1367. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00128.
  38. 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.
  39. 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.
  40. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831-854, 2013. URL: https://doi.org/10.1137/09076619X.
  41. Nicholas C. Wormald. Models of random regular graphs. London Mathematical Society Lecture Note Series, pages 239-298, 1999. Google Scholar
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