Document Open Access Logo

Parameterised Counting in Logspace

Authors Anselm Haak , Arne Meier , Om Prakash, Raghavendra Rao B. V.

PDF
Thumbnail PDF

File

LIPIcs.STACS.2021.40.pdf
  • Filesize: 0.86 MB
  • 17 pages

Document Identifiers

Author Details

Anselm Haak
  • Institut für Theoretische Informatik, Leibniz Universität Hannover, Germany
Arne Meier
  • Institut für Theoretische Informatik, Leibniz Universität Hannover, Germany
Om Prakash
  • Department of Computer Science and Engineering, IIT Madras, Chennai, India
Raghavendra Rao B. V.
  • Department of Computer Science and Engineering, IIT Madras, Chennai, India

Funding

Indo-German co-operation grant: DAAD (57388253), DST (INT/FRG/DAAD/P-19/2018).
  • Meier, Arne: Funded by the German Research Foundation (DFG), project ME4279/1-2.

Acknowledgements

The authors thank the anonymous referees for their valuable feedback.

Cite AsGet BibTex

Anselm Haak, Arne Meier, Om Prakash, and Raghavendra Rao B. V.. Parameterised Counting in Logspace. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.40

Abstract

Logarithmic space bounded complexity classes such as L and NL play a central role in space bounded computation. The study of counting versions of these complexity classes have lead to several interesting insights into the structure of computational problems such as computing the determinant and counting paths in directed acyclic graphs. Though parameterised complexity theory was initiated roughly three decades ago by Downey and Fellows, a satisfactory study of parameterised logarithmic space bounded computation was developed only in the last decade by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau (IPEC 2013, Algorithmica 2015). They defined the operators para_W and para_β for parameterised space complexity classes by allowing bounded nondeterminism with multiple-read and read-once access, respectively. Using these operators, they characterised the parameterised complexity of natural problems on graphs. In the spirit of the operators para_W and para_β by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, para_{W[1]} and para_{βtail}. Then, we consider counting versions of all four operators applied to logspace and obtain several natural complete problems for the resulting classes: counting of paths in digraphs, counting first-order models for formulas, and counting graph homomorphisms. Furthermore, we show that the complexity of a parameterised variant of the determinant function for (0,1)-matrices is #para_{βtail} L-hard and can be written as the difference of two functions in #para_{βtail} L. These problems exhibit the richness of the introduced counting classes. Our results further indicate interesting structural characteristics of these classes. For example, we show that the closure of #para_{βtail} L under parameterised logspace parsimonious reductions coincides with #para_β L, that is, modulo parameterised reductions, tail-nondeterminism with read-once access is the same as read-once nondeterminism. Initiating the study of closure properties of these parameterised logspace counting classes, we show that all introduced classes are closed under addition and multiplication, and those without tail-nondeterminism are closed under parameterised logspace parsimonious reductions. Also, we show that the counting classes defined can naturally be characterised by parameterised variants of classes based on branching programs in analogy to the classical counting classes. Finally, we underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Parameterized Complexity
  • Counting Complexity
  • Logspace

Metrics

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

Related Versions

References

  1. Manindra Agrawal, Eric Allender, and Samir Datta. On TC⁰, AC⁰, and arithmetic circuits. J. Comput. Syst. Sci., 60(2):395-421, 2000. Google Scholar
  2. Eric Allender, Robert Beals, and Mitsunori Ogihara. The complexity of matrix rank and feasible systems of linear equations. Computational Complexity, 8(2):99-126, 1999. Google Scholar
  3. Eric Allender and Mitsunori Ogihara. Relationships among PL, #L, and the determinant. ITA, 30(1):1-21, 1996. Google Scholar
  4. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  5. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  6. Max Bannach, Christoph Stockhusen, and Till Tantau. Fast parallel fixed-parameter algorithms via color coding. In IPEC, volume 43 of LIPIcs, pages 224-235. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  7. Richard Beigel and Bin Fu. Circuits over PP and PL. J. Comput. Syst. Sci., 60(2):422-441, 2000. Google Scholar
  8. Ralph Bottesch. Relativization and interactive proof systems in parameterized complexity theory. In IPEC, volume 89 of LIPIcs, pages 9:1-9:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  9. Ralph Christian Bottesch. On W[1]-hardness as evidence for intractability. In MFCS, volume 117 of LIPIcs, pages 73:1-73:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  10. Cornelius Brand and Marc Roth. Parameterized counting of trees, forests and matroid bases. In CSR, volume 10304 of Lecture Notes in Computer Science, pages 85-98. Springer, 2017. Google Scholar
  11. Jonathan F. Buss. Relativized alternation and space-bounded computation. J. Comput. Syst. Sci., 36(3):351-378, 1988. Google Scholar
  12. Hervé Caussinus, Pierre McKenzie, Denis Thérien, and Heribert Vollmer. Nondeterministic NC^1 computation. J. Comput. Syst. Sci., 57(2):200-212, 1998. Google Scholar
  13. Ankit Chauhan and B. V. Raghavendra Rao. Parameterized analogues of probabilistic computation. In CALDAM, volume 8959 of Lecture Notes in Computer Science, pages 181-192. Springer, 2015. Google Scholar
  14. Hubie Chen and Moritz Müller. The fine classification of conjunctive queries and parameterized logarithmic space. TOCT, 7(2):7:1-7:27, 2015. Google Scholar
  15. Yijia Chen and Jörg Flum. Some lower bounds in parameterized AC^0. In MFCS, volume 58 of LIPIcs, pages 27:1-27:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  16. Yijia Chen and Jörg Flum. Some lower bounds in parameterized AC^0. CoRR, abs/1606.08014, 2016. URL: http://arxiv.org/abs/1606.08014.
  17. Yijia Chen, Jörg Flum, and Martin Grohe. Bounded nondeterminism and alternation in parameterized complexity theory. In Computational Complexity Conference, pages 13-29. IEEE Computer Society, 2003. Google Scholar
  18. Radu Curticapean. Counting matchings of size k is W[1]-hard. In ICALP (1), volume 7965 of Lecture Notes in Computer Science, pages 352-363. Springer, 2013. Google Scholar
  19. Radu Curticapean. The simple, little and slow things count: on parameterized counting complexity. PhD thesis, Saarland University, 2015. Google Scholar
  20. Radu Curticapean. Block interpolation: A framework for tight exponential-time counting complexity. Inf. Comput., 261(Part):265-280, 2018. Google Scholar
  21. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In STOC, pages 210-223. ACM, 2017. Google Scholar
  22. 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. Google Scholar
  23. Carsten Damm. DET = L^#L? Technical report, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universitlt zu Berlin, 1991. Google Scholar
  24. Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas, and Heribert Vollmer. Counting classes and the fine structure between NC^1 and L. Theor. Comput. Sci., 417:36-49, 2012. Google Scholar
  25. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. Google Scholar
  26. Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms, 17(3-4):260-289, 2000. Google Scholar
  27. Heinz-Dieter Ebbinghaus, Jörg Flum, and Wolfgang Thomas. Mathematical logic (2. ed.). Undergraduate texts in mathematics. Springer, 1994. Google Scholar
  28. Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica, 71(3):661-701, 2015. Google Scholar
  29. Stephen A. Fenner, Lance Fortnow, and Stuart A. Kurtz. Gap-definable counting classes. J. Comput. Syst. Sci., 48(1):116-148, 1994. Google Scholar
  30. Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions. J. ACM, 49(6):716-752, 2002. Google Scholar
  31. Jörg Flum and Martin Grohe. Describing parameterized complexity classes. Inf. Comput., 187(2):291-319, 2003. Google Scholar
  32. Jörg Flum and Martin Grohe. The parameterized complexity of counting problems. SIAM J. Comput., 33(4):892-922, 2004. Google Scholar
  33. Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. Google Scholar
  34. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM, 54(1):1:1-1:24, 2007. Google Scholar
  35. Anselm Haak, Juha Kontinen, Fabian Müller, Heribert Vollmer, and Fan Yang. Counting of teams in first-order team logics. In MFCS, volume 138 of LIPIcs, pages 19:1-19:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  36. Anselm Haak, Arne Meier, Om Prakash, and B. V. Raghavendra Rao. Parameterised counting in logspace. CoRR, abs/1904.12156, 2019. URL: http://arxiv.org/abs/1904.12156.
  37. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. Combinatorica, 37(5):965-990, 2017. Google Scholar
  38. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. Google Scholar
  39. Catherine McCartin. Parameterized counting problems. In MFCS, volume 2420 of Lecture Notes in Computer Science, pages 556-567. Springer, 2002. Google Scholar
  40. Mitsunori Ogihara. The PL hierarchy collapses. SIAM J. Comput., 27(5):1430-1437, 1998. Google Scholar
  41. Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997. Google Scholar
  42. Christoph Stockhusen. On the space and circuit complexity of parameterized problems. PhD thesis, University of Lübeck, Germany, 2017. URL: http://www.zhb.uni-luebeck.de/epubs/ediss1780.pdf.
  43. Christoph Stockhusen and Till Tantau. Completeness results for parameterized space classes. In IPEC, volume 8246 of Lecture Notes in Computer Science, pages 335-347. Springer, 2013. Google Scholar
  44. Seinosuke Toda. Counting problems computationally equivalent to the determinant. Technical Report CSIM 91-07, Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo, 1991. URL: http://perso.ens-lyon.fr/natacha.portier/papers/toda91.pdf.
  45. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. Google Scholar
  46. Leslie G. Valiant. The complexity of computing the permanent. Theor. Comput. Sci., 8:189-201, 1979. Google Scholar
  47. V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of 6th Structure in Complexity Theory Conference, pages 270-284, 1991. 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