M. Cesati, Perfect Code is W[1]-complete (Information Processing Letters (81)3 (2002) pp. 163- 168)

We show that the parameterized problem Perfect Code belongs to W[1]. This result closes an old open question, because it was often conjectured that Perfect Code could be a natural problem having complexity degree intermediate between W[1] and W[2]. This result also shows W[1]-membership for the parameterized problem Weighted Exact CNF Satisfiability.

Back to the Marco Cesati's research page.