TY - JOUR

T1 - Parameterised Counting in Logspace

AU - Haak, Anselm

AU - Meier, Arne

AU - Prakash, Om

AU - Rao, B. V. Raghavendra

N1 - Open Access funding enabled and organized by Projekt DEAL. The project is supported by an Indo-German co-operation Grant: DAAD (57388253), DST (INT/FRG/DAAD/P-19/2018). The second author is partially funded by the German Research Foundation (DFG) under the project number ME4279/1-2.

PY - 2023/10

Y1 - 2023/10

N2 - 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. 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 and apply them to the class L. We 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 β tailL-hard and can be written as the difference of two functions in # para β tailL. 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 β tailL under parameterised logspace parsimonious reductions coincides with # para βL. In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. 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. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.

AB - 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. 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 and apply them to the class L. We 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 β tailL-hard and can be written as the difference of two functions in # para β tailL. 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 β tailL under parameterised logspace parsimonious reductions coincides with # para βL. In other words, in the setting of read-once access to nondeterministic bits, tail-nondeterminism coincides with unbounded nondeterminism modulo parameterised reductions. 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. Finally, we want to emphasise the significance of this topic by providing a promising outlook highlighting several open problems and directions for further research.

KW - Counting complexity

KW - Logspace

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=85153060200&partnerID=8YFLogxK

U2 - 10.1007/s00453-023-01114-2

DO - 10.1007/s00453-023-01114-2

M3 - Article

AN - SCOPUS:85153060200

VL - 85

SP - 2923

EP - 2961

JO - ALGORITHMICA

JF - ALGORITHMICA

SN - 0178-4617

IS - 10

M1 - 10

ER -