ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-150 | 28th November 2012 11:23

On the Space Complexity of Parameterized Problems

RSS-Feed




Revision #1
Authors: Michael Elberfeld, Christoph Stockhusen, Till Tantau
Accepted on: 28th November 2012 11:23
Downloads: 690
Keywords: 


Abstract:

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$. For a number of further natural parameterized problems, including the longest common subsequence problem, the acceptance problem for multi-head automata, and the associative generability problem we show that they lie in or are complete for different parameterized space classes. Our results explain why previous attempts at proving completeness of different problems for parameterized time classes have failed.



Changes to previous version:

1. Added reference to a paper from Guillemot concerning a completeness result for the longest common subsequence problem.
2. Fixed a little error in the proof for p-AGEN where we forgot to discuss the error element.


Paper:

TR12-150 | 1st November 2012 14:15

On the Space Complexity of Parameterized Problems


Abstract:

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$. For a number of further natural parameterized problems, including the longest common subsequence problem, the acceptance problem for multi-head automata, and the associative generability problem we show that they lie in or are complete for different parameterized space classes. Our results explain why previous attempts at proving completeness of different problems for parameterized time classes have failed.



ISSN 1433-8092 | Imprint