Abstract:
We consider the framework of Parameterized Complexity, and we investigate the issue of which problems do admit efficient fixed parameter parallel algorithms by introducing two different degrees of efficiently parallelizable parameterized problems, PNC and FPP. We sketch both some FPP-algorithms solving natural parameterized problems and a useful tool for proving membership to FPP based on the concept of treewidth. We then focus our attention on parameterized parallel intractability and prove that a necessary condition for a parameterized problem to be complete for the class of sequentially fixed parameter tractable problems is that it is not in NC for some fixed value of the parameter (unless P = NC). Finally, we give two alternative characterizations of both PNC and FPP, and we use them to prove the PNC-completeness of two natural parameterized problems.

Comment #1 to TR97-006 | 27th April 1997 08:16

A correction to Parameterized Parallel Complexity Comment on: TR97-006

Abstract:
A reduction presented in the paper is wrong. We show a computational problem that replaces the original one.