2016/01/19 by Bonnet, Édouard, Egri, László, Lin, Bingkai +1 · 3 citations
#68Q17 #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1601.04935
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 Γ of constraints, we denote by MinCSP(Γ) the restriction of the problem where each constraint is from Γ. The polynomial-time solvability and the polynomial-time approximability of MinCSP(Γ) 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)nO(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 Γ, either we exhibit a constant-factor FP-approximation for MinCSP(Γ); or we prove that MinCSP(Γ) 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.