On the Parameterized Complexity Of Exact Satisfiability Problems
Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith · 2005
For many problems, the investigation of their parameterized complexity provides an interesting and useful point of view. The most obvious natural parameterization for the maximum satisfiability problem---the number of satisfiable clauses---makes little sense, because at least half of the clauses can be satisfied in any formula. We look at two optimization variants of the exact satisfiability problem, where a clause is only said to be fulfilled iff exactly one of its literals is set to true. Interestingly, these variants behave quite di#erently. In the case of ResMaxExactSAT, where over-satisfied clauses are entirely forbidden, we show fixed parameter tractability. On the other hand, if we choose to ignore over-satisfied clauses, the MaxExactSAT problem is obtained. Surprisingly,