Bonnet, Édouard ;
Egri, László ;
Marx, Dániel
FixedParameter Approximability of Boolean MinCSPs
Abstract
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 minimumsize 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 polynomialtime solvability and the polynomialtime approximability of CSP(Gamma) were fully characterized by [Khanna et al. SICOMP 2000]. Here we study the fixedparameter (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 constantfactor FPapproximability. Our main result classifies each finite constraint language Gamma into one of three classes: (1) CSP(Gamma) has a constantfactor FPapproximation; (2) CSP(Gamma) has a (constantfactor) FPapproximation if and only if Nearest Codeword has a (constantfactor) FPapproximation; (3) CSP(Gamma) has no FPapproximation, unless FPT=W[P]. We show that problems in the second class do not have constantfactor FPapproximations if both the ExponentialTime Hypothesis (ETH) and the Linear PCP Conjecture (LPC) hold. We also show that such an approximation would imply the existence of an FPapproximation for the kDensest Subgraph problem with ratio 1epsilon for any epsilon>0.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2016:6369,
author = {{\'E}douard Bonnet and L{\'a}szl{\'o} Egri and D{\'a}niel Marx},
title = {{FixedParameter Approximability of Boolean MinCSPs}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {18:118:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6369},
URN = {urn:nbn:de:0030drops63694},
doi = {10.4230/LIPIcs.ESA.2016.18},
annote = {Keywords: constraint satisfaction problems, approximability, fixedparameter tractability}
}
18.08.2016
Keywords: 

constraint satisfaction problems, approximability, fixedparameter tractability 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

18.08.2016 