Loading [MathJax]/extensions/tex2jax.js

Parameterised Counting in Logspace

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Autorschaft

  • Anselm Haak
  • Arne Meier
  • Om Prakash
  • B. V. Raghavendra Rao

Details

OriginalspracheEnglisch
Titel des Sammelwerks38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
Herausgeber/-innenMarkus Blaser, Benjamin Monmege
Seiten1-17
Seitenumfang17
ISBN (elektronisch)9783959771801
PublikationsstatusVeröffentlicht - 2021
Veranstaltung38th International Symposium on Theoretical Aspects of Computer Science - Saarbrücken, Deutschland
Dauer: 16 März 202119 März 2021
Konferenznummer: 38
https://stacs2021.saarland-informatics-campus.de

Publikationsreihe

NameLeibniz International Proceedings in Informatics, LIPIcs
Band187
ISSN (Print)1868-8969

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 paraW 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 paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[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β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, that is, modulo parameterised reductions, tailnondeterminism 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.

ASJC Scopus Sachgebiete

Zitieren

Parameterised Counting in Logspace. / Haak, Anselm; Meier, Arne; Prakash, Om et al.
38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. Hrsg. / Markus Blaser; Benjamin Monmege. 2021. S. 1-17 40 (Leibniz International Proceedings in Informatics, LIPIcs; Band 187).

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Haak, A, Meier, A, Prakash, O & Rao, BVR 2021, Parameterised Counting in Logspace. in M Blaser & B Monmege (Hrsg.), 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021., 40, Leibniz International Proceedings in Informatics, LIPIcs, Bd. 187, S. 1-17, 38th International Symposium on Theoretical Aspects of Computer Science, Saarbrücken, Deutschland, 16 März 2021. https://doi.org/10.48550/arXiv.1904.12156, https://doi.org/10.4230/LIPICS.STACS.2021.40
Haak, A., Meier, A., Prakash, O., & Rao, B. V. R. (2021). Parameterised Counting in Logspace. In M. Blaser, & B. Monmege (Hrsg.), 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021 (S. 1-17). Artikel 40 (Leibniz International Proceedings in Informatics, LIPIcs; Band 187). https://doi.org/10.48550/arXiv.1904.12156, https://doi.org/10.4230/LIPICS.STACS.2021.40
Haak A, Meier A, Prakash O, Rao BVR. Parameterised Counting in Logspace. in Blaser M, Monmege B, Hrsg., 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. 2021. S. 1-17. 40. (Leibniz International Proceedings in Informatics, LIPIcs). Epub 2019. doi: 10.48550/arXiv.1904.12156, 10.4230/LIPICS.STACS.2021.40
Haak, Anselm ; Meier, Arne ; Prakash, Om et al. / Parameterised Counting in Logspace. 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. Hrsg. / Markus Blaser ; Benjamin Monmege. 2021. S. 1-17 (Leibniz International Proceedings in Informatics, LIPIcs).
Download
@inproceedings{3707f17590334baab10aa44c254dce14,
title = "Parameterised Counting in Logspace",
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 paraW 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 paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[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β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, that is, modulo parameterised reductions, tailnondeterminism 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.",
keywords = "Counting Complexity, Logspace, Parameterized Complexity",
author = "Anselm Haak and Arne Meier and Om Prakash and Rao, {B. V. Raghavendra}",
note = "Funding Information: Funding Indo-German co-operation grant: DAAD (57388253), DST (INT/FRG/DAAD/P-19/2018). Arne Meier: Funded by the German Research Foundation (DFG), project ME4279/1-2.; 38th International Symposium on Theoretical Aspects of Computer Science, STACS2021 ; Conference date: 16-03-2021 Through 19-03-2021",
year = "2021",
doi = "10.48550/arXiv.1904.12156",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "1--17",
editor = "Markus Blaser and Benjamin Monmege",
booktitle = "38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021",
url = "https://stacs2021.saarland-informatics-campus.de",

}

Download

TY - GEN

T1 - Parameterised Counting in Logspace

AU - Haak, Anselm

AU - Meier, Arne

AU - Prakash, Om

AU - Rao, B. V. Raghavendra

N1 - Conference code: 38

PY - 2021

Y1 - 2021

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 (IPEC 2013, Algorithmica 2015). They defined the operators paraW 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 paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[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β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, that is, modulo parameterised reductions, tailnondeterminism 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.

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 (IPEC 2013, Algorithmica 2015). They defined the operators paraW 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 paraW and paraβ by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[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β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, that is, modulo parameterised reductions, tailnondeterminism 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.

KW - Counting Complexity

KW - Logspace

KW - Parameterized Complexity

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

U2 - 10.48550/arXiv.1904.12156

DO - 10.48550/arXiv.1904.12156

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 17

BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021

A2 - Blaser, Markus

A2 - Monmege, Benjamin

T2 - 38th International Symposium on Theoretical Aspects of Computer Science

Y2 - 16 March 2021 through 19 March 2021

ER -

Von denselben Autoren