Completeness Results for Parameterized Space Classes

Christoph Stockhusen, Till Tantau

Abstract

The parameterized complexity of a problem is generally considered ``settled'' once it has been shown to lie in FPT or to be complete for a class in the W-hierarchy or a similar parameterized hierarchy. Several natural parameterized problems have, however, resisted such a classification. At least in some cases, the reason is that upper and lower bounds for their parameterized space complexity have recently been obtained that rule out completeness results for parameterized time classes. In this paper, we make progress in this direction by proving that the associative generability problem and the longest common subsequence problem are complete for parameterized space classes. These classes are defined in terms of different forms of bounded nondeterminism and in terms of simultaneous time--space bounds. As a technical tool we introduce a ``union operation'' that translates between problems complete for classical complexity classes and for W-classes.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
EditorsGregory Gutin, Stefan Szeider
Number of pages13
Volume8246
Place of PublicationCham
PublisherSpringer International Publishing
Publication date2013
Pages335-347
ISBN (Print)978-3-319-03897-1
ISBN (Electronic)978-3-319-03898-8
DOIs
Publication statusPublished - 2013
Event8th International Symposium, IPEC 2013 - Sophia Antipolis, France
Duration: 04.09.201306.09.2013

Cite this