Document Open Access Logo

Parameterised and Fine-Grained Subgraph Counting, Modulo 2

Authors Leslie Ann Goldberg, Marc Roth

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.68.pdf
  • Filesize: 0.81 MB
  • 17 pages

Document Identifiers

Author Details

Leslie Ann Goldberg
  • Department of Computer Science, University of Oxford, UK
Marc Roth
  • Department of Computer Science, University of Oxford, UK

Acknowledgements

We want to thank Radu Curticapean, Holger Dell and Thore Husfeldt for insightful discussions on an early draft of this work.

Cite As Get BibTex

Leslie Ann Goldberg and Marc Roth. Parameterised and Fine-Grained Subgraph Counting, Modulo 2. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 68:1-68:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.68

Abstract

Given a class of graphs ℋ, the problem ⊕Sub(ℋ) is defined as follows. The input is a graph H ∈ ℋ together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes ℋ the problem ⊕Sub(ℋ) is fixed-parameter tractable (FPT), i.e., solvable in time f(|H|)⋅|G|^O(1).
Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that ⊕Sub(ℋ) is FPT if and only if the class of allowed patterns ℋ is matching splittable, which means that for some fixed B, every H ∈ ℋ can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. 
Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes ℋ, and (II) all tree pattern classes, i.e., all classes ℋ such that every H ∈ ℋ is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Mathematics of computing → Discrete mathematics
Keywords
  • modular counting
  • parameterised complexity
  • fine-grained complexity
  • subgraph counting

Metrics

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

Related Versions

References

  1. Amir Abboud, Shon Feller, and Oren Weimann. On the fine-grained complexity of parity problems. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 5:1-5:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.5.
  2. Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S. Cenk Sahinalp. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24(13):i241-i249, 2008. URL: https://doi.org/10.1093/bioinformatics/btn163.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  4. Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, and Asaf Shapira. Counting subgraphs in degenerate graphs. J. ACM, 69(3):23:1-23:21, 2022. URL: https://doi.org/10.1145/3520240.
  5. 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.
  6. Marco Bressan. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica, 83(8):2578-2605, 2021. URL: https://doi.org/10.1007/s00453-021-00811-0.
  7. Andrei A. Bulatov and Amirhossein Kazeminia. Complexity classification of counting graph homomorphisms modulo a prime number. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1024-1037. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520075.
  8. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput., 201(2):216-231, 2005. URL: https://doi.org/10.1016/j.ic.2005.05.001.
  9. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci., 72(8):1346-1367, 2006. URL: https://doi.org/10.1016/j.jcss.2006.04.007.
  10. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), pages 587-596. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_48.
  11. Radu Curticapean. Counting matchings of size k is w[1]-hard. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 352-363. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-39206-1_30.
  12. Radu Curticapean, Holger Dell, and Thore Husfeldt. Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 34:1-34:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.34.
  13. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 210-223. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055502.
  14. 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.
  15. 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.
  16. 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.
  17. Julian Dörfler, Marc Roth, Johannes Schmitt, and Philip Wellnitz. Counting induced subgraphs: An algebraic approach to #W[1]-hardness. Algorithmica, 84(2):379-404, 2022. URL: https://doi.org/10.1007/s00453-021-00894-9.
  18. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  19. 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.
  20. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. URL: https://doi.org/10.1007/3-540-29953-X.
  21. Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B, 99(1):218-228, 2009. URL: https://doi.org/10.1016/j.jctb.2008.06.004.
  22. Daniel J. Harvey and David R. Wood. The treewidth of line graphs. J. Comb. Theory, Ser. B, 132:157-179, 2018. URL: https://doi.org/10.1016/j.jctb.2018.03.007.
  23. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  24. 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.
  25. Oleksii Kuchaiev, Tijana Milenković, Vesna Memišević, Wayne Hayes, and Nataša Pržulj. Topological network alignment uncovers biological function and phylogeny. Journal of the Royal Society Interface, 7(50):1341-1354, 2010. URL: https://doi.org/10.1098/rsif.2010.0063.
  26. 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.
  27. Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. Superfamilies of evolved and designed networks. Science, 303(5663):1538-1542, 2004. URL: https://doi.org/10.1126/science.1089167.
  28. Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, and Alina Vdovina. Parameterized (modular) counting and cayley graph expanders. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia, volume 202 of LIPIcs, pages 84:1-84:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.84.
  29. Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina, and Philip Wellnitz. Parameterized Counting and Cayley Graph Expanders. SIAM J. Discrete Math., to appear. Google Scholar
  30. Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. StreaM - A Stream-Based Algorithm for Counting Motifs in Dynamic Graphs. In Proceedings of the 2nd International Conference on Algorithms for Computational Biology (AlCoB), pages 53-67. Springer International Publishing, 2015. URL: https://doi.org/10.1007/978-3-319-21233-3_5.
  31. 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.
  32. Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. Counting motifs in the human interactome. Nature communications, 4(1):1-8, 2013. URL: https://doi.org/10.1038/ncomms3241.
  33. Charalampos E. Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. Scalable motif-aware graph clustering. In Proceedings of the 26th International Conference on World Wide Web (WWW), pages 1451-1460, 2017. URL: https://doi.org/10.1145/3038912.3052653.
  34. 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.
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 About DROPS Imprint Privacy Contact