Counting Connected Subgraphs with Maximum-Degree-Aware Sieving

Authors Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.17.pdf
  • Filesize: 383 kB
  • 12 pages

Document Identifiers

Author Details

Andreas Björklund
  • Department of Computer Science, Lund University, Sweden
Thore Husfeldt
  • BARC, IT University of Copenhagen, Denmark and Lund University, Sweden
Petteri Kaski
  • Department of Computer Science, Aalto University, Finland
Mikko Koivisto
  • Department of Computer Science, University of Helsinki, Finland

Cite AsGet BibTex

Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Connected Subgraphs with Maximum-Degree-Aware Sieving. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.17

Abstract

We study the problem of counting the isomorphic occurrences of a k-vertex pattern graph P as a subgraph in an n-vertex host graph G. Our specific interest is on algorithms for subgraph counting that are sensitive to the maximum degree Delta of the host graph. Assuming that the pattern graph P is connected and admits a vertex balancer of size b, we present an algorithm that counts the occurrences of P in G in O ((2 Delta-2)^{(k+b)/2} 2^{-b} n/(Delta) k^2 log n) time. We define a balancer as a vertex separator of P that can be represented as an intersection of two equal-size vertex subsets, the union of which is the vertex set of P, and both of which induce connected subgraphs of P. A corollary of our main result is that we can count the number of k-vertex paths in an n-vertex graph in O((2 Delta-2)^{floor[k/2]} n k^2 log n) time, which for all moderately dense graphs with Delta <= n^{1/3} improves on the recent breakthrough work of Curticapean, Dell, and Marx [STOC 2017], who show how to count the isomorphic occurrences of a q-edge pattern graph as a subgraph in an n-vertex host graph in time O(q^q n^{0.17q}) for all large enough q. Another recent result of Brand, Dell, and Husfeldt [STOC 2018] shows that k-vertex paths in a bounded-degree graph can be approximately counted in O(4^kn) time. Our result shows that the exact count can be recovered at least as fast for Delta<10. Our algorithm is based on the principle of inclusion and exclusion, and can be viewed as a sparsity-sensitive version of the "counting in halves"-approach explored by Björklund, Husfeldt, Kaski, and Koivisto [ESA 2009].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • graph embedding
  • k-path
  • subgraph counting
  • maximum degree

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the Current Clique Algorithms are Optimal, So is Valiant’s Parser. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pages 98-117, 2015. Google Scholar
  2. Noga Alon and Shai Gutner. Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms, 6(3):54:1-54:12, 2010. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and Counting Given Length Cycles. Algorithmica, 17(3):209-223, 1997. Google Scholar
  4. Omid Amini, Fedor V. Fomin, and Saket Saurabh. Counting Subgraphs via Homomorphisms. SIAM J. Discrete Math., 26(2):695-717, 2012. Google Scholar
  5. Per Austrin, Petteri Kaski, and Kaie Kubjas. Tensor network complexity of multilinear maps. CoRR, abs/1712.09630, 2017. Google Scholar
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Paths and Packings in Halves. In Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, pages 578-586, 2009. Google Scholar
  7. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 594-603, 2014. Google Scholar
  8. Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-Coding. In STOC '18: Symposium on Theory of Computing, June 23-27, 2018, Los Angeles, CA, USA, page 14. ACM, New York, NY, USA, 2018. Google Scholar
  9. Yijia Chen and Jörg Flum. On Parameterized Path and Chordless Path Problems. In 22nd Annual IEEE Conference on Computational Complexity (CCC), pages 250-263, 2007. Google Scholar
  10. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Track A, pages 587-596, 2008. Google Scholar
  11. Radu Curticapean. Counting Matchings of Size k Is #W[1]-Hard. In Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 352-363, 2013. Google Scholar
  12. 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, 2017. Google Scholar
  13. 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, pages 130-139, 2014. Google Scholar
  14. Friedrich Eisenbrand and Fabrizio Grandoni. On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci., 326(1-3):57-67, 2004. Google Scholar
  15. 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. Google Scholar
  16. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, page 538, 2002. Google Scholar
  17. 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. Google Scholar
  18. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  19. Alon Itai and Michael Rodeh. Finding a Minimum Circuit in a Graph. SIAM J. Comput., 7(4):413-423, 1978. Google Scholar
  20. Mark Jerrum and Kitty Meeks. Some Hard Families of Parameterized Counting Problems. TOCT, 7(3):11:1-11:18, 2015. Google Scholar
  21. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci., 81(4):702-716, 2015. Google Scholar
  22. Ton Kloks, Dieter Kratsch, and Haiko Müller. Finding and counting small induced subgraphs efficiently. Inf. Process. Lett., 74(3-4):115-121, 2000. Google Scholar
  23. Christian Komusiewicz and Manuel Sorge. An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems. Discrete Applied Mathematics, 193:145-161, 2015. Google Scholar
  24. François Le Gall. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation, ISSAC, pages 296-303, 2014. Google Scholar
  25. L. Lovász. Operations with structures. Acta Math. Acad. Sci. Hungar., 18:321-328, 1967. Google Scholar
  26. Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198:170-194, 2016. Google Scholar
  27. J. Nešetřil and S. Poljak. On the complexity of the subgraph problem. Comment. Math. Univ. Carolin., 26(2):415-419, 1985. Google Scholar
  28. Stephan Olariu. Paw-Free Graphs. Inf. Process. Lett., 28(1):53-54, 1988. Google Scholar
  29. Viresh Patel and Guus Regts. Computing the number of induced copies of a fixed graph in a bounded degree graph. CoRR, abs/1707.05186, 2017. Google Scholar
  30. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC, pages 887-898, 2012. Google Scholar
  31. Virginia Vassilevska Williams, Joshua R. Wang, Richard 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 2015, pages 1671-1680, 2015. Google Scholar
  32. Virginia Vassilevska Williams and Ryan Williams. Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput., 42(3):831-854, 2013. Google Scholar
  33. Meirav Zehavi. Mixing Color Coding-Related Techniques. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 1037-1049, 2015. 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