  The minimum unsatisfiability version of a constraint satisfaction problem
(MinCSP) asks for an assignment where the number of unsatisfied constraints is
minimum possible, or equivalently, asks for a minimum-size set of constraints
whose deletion makes the instance satisfiable. For a finite set $\Gamma$ of
constraints, we denote by MinCSP($\Gamma$) the restriction of the problem where
each constraint is from $\Gamma$. The polynomial-time solvability and the
polynomial-time approximability of MinCSP($\Gamma$) were fully characterized by
Khanna et al. [Siam J. Comput. '00]. Here we study the fixed-parameter (FP-)
approximability of the problem: given an instance and an integer $k$, one has
to find a solution of size at most $g(k)$ in time $f(k)n^{O(1)}$ if a solution
of size at most $k$ exists. We especially focus on the case of constant-factor
FP-approximability. We show the following dichotomy: for each finite constraint
language $\Gamma$, either we exhibit a constant-factor FP-approximation for
MinCSP($\Gamma$); or we prove that MinCSP($\Gamma$) has no constant-factor
FP-approximation unless FPT$=$W[1]. In particular, we show that approximating
the so-called Nearest Codeword within some constant factor is W[1]-hard.
Recently, Arnab et al. [ICALP '18] showed that such a W[1]-hardness of
approximation implies that Even Set is W[1]-hard under randomized reductions.
Combining our results, we therefore settle the parameterized complexity of Even
Set, a famous open question in the field.
