Parameterised counting in logspace

DOI10.1007/S00453-023-01114-2arXiv1904.12156WikidataQ123269459 ScholiaQ123269459MaRDI QIDQ6093373FDOQ6093373

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

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

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.

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)