TY - CHAP
T1 - Constraint satisfaction problems parameterized above or below tight bounds
T2 - A survey
AU - Gutin, Gregory
AU - Yeo, Anders
PY - 2012
Y1 - 2012
N2 - We consider constraint satisfaction problems parameterized above or below tight bounds. 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 MaxLin2-AA (given a system of linear equations over F 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), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (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 ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 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.
AB - We consider constraint satisfaction problems parameterized above or below tight bounds. 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 MaxLin2-AA (given a system of linear equations over F 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), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (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 ∑ m i=1 (1-2 r i clauses, where k is the parameter, r i is the number of literals in Clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 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.
UR - https://www.scopus.com/pages/publications/84864135167
U2 - 10.1007/978-3-642-30891-8_14
DO - 10.1007/978-3-642-30891-8_14
M3 - Chapter
AN - SCOPUS:84864135167
SN - 9783642308901
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 257
EP - 286
BT - The Multivariate Algorithmic Revolution and Beyond
A2 - Hans, Bodlaender
A2 - Rod, Downey
A2 - Fedor, Fomin
A2 - Daniel, Marx
ER -