Document Open Access Logo

Finding and Counting Patterns in Sparse Graphs

Authors Balagopal Komarath, Anant Kumar, Suchismita Mishra, Aditi Sethia

PDF
Thumbnail PDF

File

LIPIcs.STACS.2023.40.pdf
  • Filesize: 0.71 MB
  • 20 pages

Document Identifiers

Author Details

Balagopal Komarath
  • IIT Gandhinagar, India
Anant Kumar
  • IIT Gandhinagar, India
Suchismita Mishra
  • Universidad Andrés Bello, Santiago, Chile
Aditi Sethia
  • IIT Gandhinagar, India

Acknowledgements

The research work of S. Mishra is partially funded by Fondecyt Postdoctoral grant 3220618 of Agencia National de Investigatión y Desarrollo (ANID), Chile.

Cite AsGet BibTex

Balagopal Komarath, Anant Kumar, Suchismita Mishra, and Aditi Sethia. Finding and Counting Patterns in Sparse Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.STACS.2023.40

Abstract

We consider algorithms for finding and counting small, fixed graphs in sparse host graphs. In the non-sparse setting, the parameters treedepth and treewidth play a crucial role in fast, constant-space and polynomial-space algorithms respectively. We discover two new parameters that we call matched treedepth and matched treewidth. We show that finding and counting patterns with low matched treedepth and low matched treewidth can be done asymptotically faster than the existing algorithms when the host graphs are sparse for many patterns. As an application to finding and counting fixed-size patterns, we discover Õ(m³)-time, constant-space algorithms for cycles of length at most 11 and Õ(m²)-time, polynomial-space algorithms for paths of length at most 10.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Subgraph Detection and Counting
  • Homomorphism Polynomials
  • Treewidth and Treedepth
  • Matchings

Metrics

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

Related Versions

Supplementary Materials

References

  1. N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, March 1997. URL: https://doi.org/10.1007/BF02523189.
  2. 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.
  3. Marco Bressan and Marc Roth. Exact and approximate pattern counting in degenerate graphs: New algorithms, hardness results, and complexity dichotomies. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 276-285, 2022. URL: https://doi.org/10.1109/FOCS52979.2021.00036.
  4. 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 2017, pages 210-223, New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3055399.3055502.
  5. 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.
  6. Josep Díaz, Maria J. Serna, and Dimitrios M. Thilikos. Counting h-colorings of partial k-trees. In Proceedings of the 7th Annual International Conference on Computing and Combinatorics, COCOON '01, pages 298-307, Berlin, Heidelberg, 2001. Springer-Verlag. Google Scholar
  7. 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.
  8. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science, 326:57-67, October 2004. URL: https://doi.org/10.1016/j.tcs.2004.05.009.
  9. Peter Floderus, Mirosław Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Induced subgraph isomorphism: Are some patterns substantially easier than others? In Joachim Gudmundsson, Julián Mestre, and Taso Viglas, editors, Computing and Combinatorics, pages 37-48, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  10. Jacob Focke and Marc Roth. Counting small induced subgraphs with hereditary properties. 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 1543-1551. ACM, 2022. URL: https://doi.org/10.1145/3519935.3520008.
  11. 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.
  12. 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.
  13. Balagopal Komarath, Anurag Pandey, and C. S. Rahul. Graph homomorphism polynomials: Algorithms and complexity. CoRR, abs/2011.04778, 2020. URL: http://arxiv.org/abs/2011.04778.
  14. Ioannis Koutis. Faster algebraic algorithms for path and packing problems. In International Colloquium on Automata, Languages, and Programming, pages 575-586. Springer, 2008. Google Scholar
  15. Miroslaw Kowaluk, Andrzej Lingas, and Eva-Marta Lundell. Counting and detecting small subgraphs via equations. SIAM J. Discret. Math., 27:892-909, 2013. Google Scholar
  16. 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.
  17. Marc Roth, Johannes Schmitt, and Philip Wellnitz. Detecting and Counting Small Subgraphs, and Evaluating a Parameterized Tutte Polynomial: Lower Bounds via Toroidal Grids and Cayley Graph Expanders. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 108:1-108:16, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.108.
  18. Virginia Vassilevska. Efficient Algorithms for Path Problems in Weighted Graphs. PhD thesis, Carnegie Mellon University, Pittsburgh, PA 15213, 2008. Google Scholar
  19. Douglas B. West. Introduction to Graph Theory. Prentice Hall, September 2000. Google Scholar
  20. Ryan Williams. Maximum two-satisfiability. Encyclopedia of Algorithms, pages 507-510, 2008. URL: https://doi.org/10.1007/978-0-387-30162-4_227.
  21. Ryan Williams. Finding paths of length k in o*(2k) time. Inf. Process. Lett., 109(6):315-318, February 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
  22. Virginia Vassilevska Williams, Joshua R. Wang, Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, pages 1671-1680, USA, 2015. Society for Industrial and Applied Mathematics. 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