Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

DOI10.1007/978-3-642-30891-8_14zbMATH Open1358.68135arXiv1108.4803OpenAlexW1622068963MaRDI QIDQ2908541

Author name not available (Why is that?)

Publication date: 5 September 2012

Published in: (Search for Journal in Brave)

Abstract: 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 $mathbb{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), 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 $su{m}_{i=1}^m(1-2^{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 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.

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

Mathematics Subject Classification ID

No records found.

This page was built for publication: Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey

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