On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness

Michael Elberfeld, Christoph Stockhusen*, Till Tantau

*Corresponding author for this work
8 Citations (Scopus)

Abstract

The parameterized complexity of a problem is generally considered “settled” once it has been shown to be fixed-parameter tractable or to be complete for a class in a parameterized hierarchy such as the weft hierarchy. Several natural parameterized problems have, however, resisted such a classification. In the present paper we argue that, in some cases, this is due to the fact that the parameterized complexity of these problems can be better understood in terms of their parameterized space or parameterized circuit complexity. This includes well-studied, natural problems like the feedback vertex set problem, the associative generability problem, or the longest common subsequence problem. We show that these problems lie in and may even be complete for different parameterized space classes, leading to new insights into the problems’ complexity. The classes we study are defined in terms of different forms of bounded nondeterminism and simultaneous time–space bounds.

Original languageEnglish
JournalAlgorithmica
Volume71
Issue number3
Pages (from-to)661-701
Number of pages41
ISSN0178-4617
DOIs
Publication statusPublished - 16.10.2014

Fingerprint

Dive into the research topics of 'On the Space and Circuit Complexity of Parameterized Problems: Classes and Completeness'. Together they form a unique fingerprint.

Cite this