| Abstract |
|---|
| In the Parameterized Complexity setting we investigate which problemsdo admit efficient fixed parameter parallel algorithms. We introducetwo classes of efficiently parallelizable parameterized problems,PNC and FPP, and sketch both some FPP-algorithms solving naturalparameterized problems and a useful tool for provingmembership to FPP based on treewidth. We prove that anecessary condition for a parameterized problem to be complete for theclass of fixed parameter tractable problems (with respectto reductions preserving membership to PNC) is that it is not in NCfor some fixed value of the parameter (unless P=NC). We givetwo characterizations of PNC and FPP and prove the PNC-completenessof two natural parameterized problems. |
| Contact |
| Marco Cesati c/o Prof. Daniel P. Bovet,Dep. of Computer Science, Systems and Industrial Engineering,Univ. of Rome "Tor Vergata",via di Tor Vergata, I-00156 Rome, Italy cesati@uniroma2.it |