On the Space Complexity of Parameterized Problems

Michael Elberfeld, Christoph Stockhusen, Till Tantau


Parameterized complexity theory measures the complexity of computational problems predominantly in terms of their parameterized time complexity. The purpose of the present paper is to demonstrate that the study of parameterized space complexity can give new insights into the complexity of well-studied parameterized problems like the feedback vertex set problem. We show that the undirected and the directed feedback vertex set problems have different parameterized space complexities, unless L = NL; which explains why the two problem variants seem to necessitate different algorithmic approaches even though their parameterized time complexity is the same. For a number of further natural parameterized problems, including the longest common subsequence problem and the acceptance problem for multi-head automata, we show that they lie in or are complete for different parameterized space classes; which explains why previous attempts at proving completeness of these problems for parameterized time classes have failed.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
EditorsDimitrios M. Thilikos, Gerhard J. Woeginger
Number of pages12
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Publication date09.2012
ISBN (Print)978-3-642-33292-0
ISBN (Electronic)978-3-642-33293-7
Publication statusPublished - 09.2012
Event7th International Symposium, IPEC 2012 - Ljubljana, Slovenia
Duration: 12.09.201214.09.2012


Dive into the research topics of 'On the Space Complexity of Parameterized Problems'. Together they form a unique fingerprint.

Cite this