2026-08-11T07:52:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6369 2024-03-06T10:38:05Z ddc:004 open_access

Fixed-Parameter Approximability of Boolean MinCSPs Bonnet, Édouard Egri, László Marx, Dániel constraint satisfaction problems approximability fixed-parameter tractability The minimum unsatisfiability version of a constraint satisfaction problem (CSP) 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 CSP(Gamma) the restriction of the problem where each constraint is from Gamma. The polynomial-time solvability and the polynomial-time approximability of CSP(Gamma) were fully characterized by [Khanna et al. SICOMP 2000]. 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. Our main result classifies each finite constraint language Gamma into one of three classes: (1) CSP(Gamma) has a constant-factor FP-approximation; (2) CSP(Gamma) has a (constant-factor) FP-approximation if and only if Nearest Codeword has a (constant-factor) FP-approximation; (3) CSP(Gamma) has no FP-approximation, unless FPT=W[P]. We show that problems in the second class do not have constant-factor FP-approximations if both the Exponential-Time Hypothesis (ETH) and the Linear PCP Conjecture (LPC) hold. We also show that such an approximation would imply the existence of an FP-approximation for the k-Densest Subgraph problem with ratio 1-epsilon for any epsilon>0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and László Egri and Dániel Marx 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.18 urn:nbn:de:0030-drops-63694 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.18 eng https://creativecommons.org/licenses/by/3.0/legalcode