Parameterised counting in logspace

DOI10.1007/S00453-023-01114-2MaRDI QIDQ6093373zbMATH OpenWikidataFDO

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

Publication date 6 October 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1904.12156

zbMATH Keywords

parameterized complexitycounting complexitylogspace

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (05Cxx)

Abstract: 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 paraBeta 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 paraBeta by Stockhusen and Tantau, we introduce variants based on tail-nondeterminism, paraW[1] and paraBeta-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 #paraBeta-Tail-L-hard and can be written as the difference of two functions in #paraBetaTail-L. For example, we show that the closure of #paraBetaTail-L under parameterised logspace parsimonious reductions coincides with #paraBeta-L, that is, modulo parameterised reductions, tail-nondeterminism with read-once access is the same as read-once nondeterminism. 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 underline the significance of this topic by providing a promising outlook showing several open problems and options for further directions of research.

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 1929968 (Why is no real title available?)
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• scientific article; zbMATH DE number 1405642 (Why is no real title available?)
• scientific article; zbMATH DE number 7075922 (Why is no real title available?)
• scientific article; zbMATH DE number 7378390 (Why is no real title available?)
• A complexity theory for feasible closure properties
• Approximate Counting CSP Seen from the Other Side
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Circuits over PP and PL
• Color-coding
• Completeness results for parameterized space classes
• Computational Complexity
• Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
• Counting matchings of size \(k\) is \#W[1]-hard
• Counting problems in parameterized complexity
• Describing parameterized complexity classes
• Extensor-coding
• Fast parallel fixed-parameter algorithms via color coding
• Gap-definable counting classes
• Homomorphisms are a good basis for counting small subgraphs
• Machine-based methods in parameterized complexity theory
• Nondeterministic \(NC^1\) computation
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• On the space and circuit complexity of parameterized problems: classes and completeness
• PP is as Hard as the Polynomial-Time Hierarchy
• Parameterized (Modular) Counting and Cayley Graph Expanders
• Parameterized analogues of probabilistic computation
• Parameterized counting of trees, forests and matroid bases
• Parametrized complexity theory.
• Query evaluation via tree-decompositions
• Relationships among $PL$, $\#L$, and the determinant
• Relativization and interactive proof systems in parameterized complexity theory
• Relativized alternation and space-bounded computation
• Some lower bounds in parameterized \(\mathrm{AC}^0\)
• Structural tractability of counting of solutions to conjunctive queries
• Subtractive reductions and complete problems for counting complexity classes
• The PL Hierarchy Collapses
• The Parameterized Complexity of Counting Problems
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The complexity of computing the permanent
• The complexity of counting homomorphisms seen from the other side
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of matrix rank and feasible systems of linear equations
• The fine classification of conjunctive queries and parameterized logarithmic space
• The parameterised complexity of counting even and odd induced subgraphs

Cited in

(1)

• scientific article; zbMATH DE number 5763313 (Why is no real title available?)

This page was built for publication: Parameterised counting in logspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093373)