Gutin, Gregory ;
Yeo, Anders
Parameterized Constraint Satisfaction Problems: a Survey
Abstract
We consider constraint satisfaction problems parameterized above or below guaranteed values. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2 + k clauses, where k is the parameter. Among other problems we deal with are MaxLin2AA (given a system of linear equations over F_2 in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), MaxrLin2AA (the same as MaxLin2AA, but each equation has at most r variables, where r is a constant) and MaxrSatAA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least sum_{i=1}^m (12^{r_i})+k clauses, where k is the parameter, r_i is the number of literals in clause i, and r is a constant). We also consider MaxrCSPAA, a natural generalization of both MaxrLin2AA and MaxrSatAA, order (or, permutation) constraint satisfaction problems parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.
BibTeX  Entry
@InCollection{gutin_et_al:DFU:2017:6964,
author = {Gregory Gutin and Anders Yeo},
title = {{Parameterized Constraint Satisfaction Problems: a Survey}},
booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability},
pages = {179203},
series = {Dagstuhl FollowUps},
ISBN = {9783959770033},
ISSN = {18688977},
year = {2017},
volume = {7},
editor = {Andrei Krokhin and Stanislav Zivny},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/6964},
URN = {urn:nbn:de:0030drops69641},
doi = {10.4230/DFU.Vol7.15301.179},
annote = {Keywords: Constraint satisfaction problems, Fixedparameter tractability}
}
21.02.2017
Keywords: 

Constraint satisfaction problems, Fixedparameter tractability 
Seminar: 

The Constraint Satisfaction Problem: Complexity and Approximability

Issue date: 

2017 
Date of publication: 

21.02.2017 