Fixed-parameter Approximability of Boolean MinCSPs

DOI10.4230/LIPICS.ESA.2016.18zbMATH Open1397.68090arXiv1601.04935OpenAlexW2962826665MaRDI QIDQ4606287FDOQ4606287

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

Publication date: 2 March 2018

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.

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

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

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)

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
• Title not available (Why is that?)

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)