Fixed-parameter Approximability of Boolean MinCSPs

DOI10.4230/LIPICS.ESA.2016.18MaRDI QIDQ4606287zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, László Egri, Dániel Marx

Publication date 2 March 2018

Full work available at URL https://arxiv.org/abs/1601.04935

zbMATH Keywords

constraint satisfaction problemsfixed-parameter tractabilityapproximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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.

Recommendations

• On approximability of Boolean formula minimization
• On approximation algorithms for the minimum satisfiability problem
• Towards a characterization of constant-factor approximable min CSPs
• scientific article; zbMATH DE number 1432158
• Optimization, randomized approximability, and Boolean constraint satisfaction problems
• scientific article; zbMATH DE number 3867065
• The Parameterized Complexity of Maximality and Minimality Problems
• The parameterized complexity of maximality and minimality problems
• The complexity of Boolean formula minimization

Cited in

(8)

• Complexity and approximability of parameterized MAX-CSPs
• Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
• (In)approximability of maximum minimal FVS
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• The complexity of valued CSPs
• Towards a characterization of constant-factor approximable min CSPs
• Fixed-parameter tractability of almost CSP problem with decisive relations
• scientific article; zbMATH DE number 7561552 (Why is no real title available?)

This page was built for publication: Fixed-parameter Approximability of Boolean MinCSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606287)