Perfect code is W[1]-complete
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 of the parameterized problem WEIGHTED EXACT CNF SATISFIABILITY. (C) 2002 Elsevier Science B.V. All rights reserved.
perfect code w[1]-completeness satisfiability computational complexity parameterized computational complexity weighted exact conjunctive normal form