Document Open Access Logo

Approximate Counting of k-Paths: Deterministic and in Polynomial Space

Authors Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2019.24.pdf
  • Filesize: 0.63 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • parameterized complexity
  • approximate counting
  • { k}-Path

Metrics

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

Abstract

A few years ago, Alon et al. [ISMB 2008] gave a simple randomized O((2e)^km epsilon^{-2})-time exponential-space algorithm to approximately compute the number of paths on k vertices in a graph G up to a multiplicative error of 1 +/- epsilon. Shortly afterwards, Alon and Gutner [IWPEC 2009, TALG 2010] gave a deterministic exponential-space algorithm with running time (2e)^{k+O(log^3k)}m log n whenever epsilon^{-1}=k^{O(1)}. Recently, Brand et al. [STOC 2018] provided a speed-up at the cost of reintroducing randomization. Specifically, they gave a randomized O(4^km epsilon^{-2})-time exponential-space algorithm. In this article, we revisit the algorithm by Alon and Gutner. We modify the foundation of their work, and with a novel twist, obtain the following results. 
- We present a deterministic 4^{k+O(sqrt{k}(log^2k+log^2 epsilon^{-1}))}m log n-time polynomial-space algorithm. This matches the running time of the best known deterministic polynomial-space algorithm for deciding whether a given graph G has a path on k vertices. 
- Additionally, we present a randomized 4^{k+O(log k(log k + log epsilon^{-1}))}m log n-time polynomial-space algorithm. While Brand et al. make non-trivial use of exterior algebra, our algorithm is very simple; we only make elementary use of the probabilistic method. 
 Thus, the algorithm by Brand et al. runs in time 4^{k+o(k)}m whenever epsilon^{-1}=2^{o(k)}, while our deterministic and randomized algorithms run in time 4^{k+o(k)}m log n whenever epsilon^{-1}=2^{o(k^{1/4})} and epsilon^{-1}=2^{o(k/(log k))}, respectively. Prior to our work, no 2^{O(k)}n^{O(1)}-time polynomial-space algorithm was known. Additionally, our approach is embeddable in the classic framework of divide-and-color, hence it immediately extends to approximate counting of graphs of bounded treewidth; in comparison, Brand et al. note that their approach is limited to graphs of bounded pathwidth.

Cite As Get BibTex

Andreas Björklund, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Approximate Counting of k-Paths: Deterministic and in Polynomial Space. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.24

Author Details

Andreas Björklund
  • Lund University, Lund, Sweden
Daniel Lokshtanov
  • University of California, Bergen, Santa Barbara, USA
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India
Meirav Zehavi
  • Ben-Gurion University, Beersheba, Israel

Funding

  • Saurabh, Saket: This work is supported by the European Research Council (ERC) via grant LOPPRE, reference 819416.
  • Zehavi, Meirav: This work is supported by the Israel Science Foundation individual research grant no. 1176/18.

References

  1. Randomization in Parameterized Complexity. URL: https://www.dagstuhl.de/de/programm/kalender/semhp/?semnr=17041.
  2. 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: http://dx.doi.org/10.1093/bioinformatics/btn163.
  3. Noga Alon and Shai Gutner. Balanced Hashing, Color Coding and Approximate Counting. In Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, pages 1-16, 2009. URL: http://dx.doi.org/10.1007/978-3-642-11269-0_1.
  4. Noga Alon and Shai Gutner. Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms, 6(3):54:1-54:12, 2010. URL: http://dx.doi.org/10.1145/1798596.1798607.
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. URL: http://dx.doi.org/10.1145/210332.210337.
  6. Vikraman Arvind and Venkatesh Raman. Approximation Algorithms for Some Parameterized Counting Problems. In Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings, pages 453-464, 2002. URL: http://dx.doi.org/10.1007/3-540-36136-7_40.
  7. André Berger, László Kozma, Matthias Mnich, and Roland Vincze. A time- and space-optimal algorithm for the many-visits TSP. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1770-1782, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.106.
  8. Andreas Björklund. Determinant Sums for Undirected Hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: http://dx.doi.org/10.1137/110839229.
  9. 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. URL: http://dx.doi.org/10.1007/978-3-642-04128-0_52.
  10. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Narrow sieves for parameterized paths and packings. J. Comput. Syst. Sci., 87:119-139, 2017. URL: http://dx.doi.org/10.1016/j.jcss.2017.03.003.
  11. Andreas Björklund, Vikram Kamat, Lukasz Kowalik, and Meirav Zehavi. Spotting Trees with Few Leaves. SIAM J. Discrete Math., 31(2):687-713, 2017. URL: http://dx.doi.org/10.1137/15M1048975.
  12. Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time. ACM Trans. Algorithms, 13(4):48:1-48:26, 2017. URL: http://dx.doi.org/10.1145/3125500.
  13. Cornelius Brand, Holger Dell, and Thore Husfeldt. Extensor-coding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 151-164, 2018. URL: http://dx.doi.org/10.1145/3188745.3188902.
  14. J. Chen, J. Kneis, S. Lu, D. Mölle, S. Richter, P. Rossmanith, S. Sze, and F. Zhang. Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms. SIAM Journal on Computing, 38(6):2526-2547, 2009. Google Scholar
  15. 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. ACM. URL: http://dx.doi.org/10.1145/3055399.3055502.
  16. 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, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.22.
  17. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3.
  18. Banu Dost, Tomer Shlomi, Nitin Gupta, Eytan Ruppin, Vineet Bafna, and Roded Sharan. QNet: A Tool for Querying Protein Interaction Networks. Journal of Computational Biology, 15(7):913-925, 2008. URL: http://dx.doi.org/10.1089/cmb.2007.0172.
  19. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. SIAM J. Comput., 33(4):892-922, 2004. Google Scholar
  20. Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 494-505, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_40.
  21. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: http://dx.doi.org/10.1145/2886094.
  22. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press, 2018. Google Scholar
  23. Gregory Z. Gutin, Felix Reidl, Magnus Wahlström, and Meirav Zehavi. Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. J. Comput. Syst. Sci., 95:69-85, 2018. URL: http://dx.doi.org/10.1016/j.jcss.2018.01.004.
  24. Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica, 52(2):114-132, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9008-7.
  25. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. Springer Publishing Company, Incorporated, 1st edition, 2010. Google Scholar
  26. Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. In 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, pages 575-586, 2008. URL: http://dx.doi.org/10.1007/978-3-540-70575-8_47.
  27. Ioannis Koutis and Ryan Williams. Algebraic fingerprints for faster algorithms. Commun. ACM, 59(1):98-105, 2016. URL: http://dx.doi.org/10.1145/2742544.
  28. Ioannis Koutis and Ryan Williams. LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algorithms, 12(3):31:1-31:18, 2016. URL: http://dx.doi.org/10.1145/2885499.
  29. Daniel Lokshtanov, Matthias Mnich, and Saket Saurabh. Planar k-Path in Subexponential Time and Polynomial Space. In Graph-Theoretic Concepts in Computer Science - 37th International Workshop, WG 2011, Teplá Monastery, Czech Republic, June 21-24, 2011. Revised Papers, pages 262-270, 2011. URL: http://dx.doi.org/10.1007/978-3-642-25870-1_24.
  30. Daniel Lokshtanov and Jesper Nederlof. Saving space by algebraization. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 321-330, 2010. URL: http://dx.doi.org/10.1145/1806689.1806735.
  31. 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: http://dx.doi.org/10.1126/science.298.5594.824.
  32. Michael Mitzenmacher and Eli Upfal. Probability and computing - randomized algorithms and probabilistic analysis. Cambridge University Press, 2005. Google Scholar
  33. Moni Naor, Leonard J. Schulman, and Aravind Srinivasan. Splitters and Near-Optimal Derandomization. In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995, pages 182-191, 1995. URL: http://dx.doi.org/10.1109/SFCS.1995.492475.
  34. Jacob Scott, Trey Ideker, Richard M. Karp, and Roded Sharan. Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. Journal of Computational Biology, 13(2):133-144, 2006. URL: http://dx.doi.org/10.1089/cmb.2006.13.133.
  35. Hadas Shachnai and Meirav Zehavi. Representative families: A unified tradeoff-based approach. J. Comput. Syst. Sci., 82(3):488-502, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2015.11.008.
  36. Roded Sharan and Trey Ideker. Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24, 427-433. Nature biotechnology, 24:427-33, May 2006. Google Scholar
  37. Tomer Shlomi, Daniel Segal, Eytan Ruppin, and Roded Sharan. QPath: a method for querying pathways in a protein-protein interaction network. BMC Bioinformatics, 7:199, 2006. URL: http://dx.doi.org/10.1186/1471-2105-7-199.
  38. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. URL: http://dx.doi.org/10.1016/j.ipl.2008.11.004.
  39. Virginia Vassilevska Williams and Ryan Williams. Finding, Minimizing, and Counting Weighted Subgraphs. SIAM J. Comput., 42(3):831-854, 2013. URL: http://dx.doi.org/10.1137/09076619X.
  40. 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. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_86.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact