Improved Parameterized Algorithms for Constraint Satisfaction
arXiv:1008.0213
Abstract
For many constraint satisfaction problems, the algorithm which chooses a random assignment achieves the best possible approximation ratio. For instance, a simple random assignment for {\sc Max-E3-Sat} allows 7/8-approximation and for every $\eps >0$ there is no polynomial-time ($7/8+\eps$)-approximation unless P=NP. Another example is the {\sc Permutation CSP} of bounded arity. Given the expected fraction of the constraints satisfied by a random assignment (i.e. permutation), there is no $(ρ+\eps)$-approximation algorithm for every $\eps >0$, assuming the Unique Games Conjecture (UGC). In this work, we consider the following parameterization of constraint satisfaction problems. Given a set of constraints of constant arity, can we satisfy at least constraint, where is the expected fraction of constraints satisfied by a random assignment? {\sc Constraint Satisfaction Problems above Average} have been posed in different forms in the literature \cite{Niedermeier2006,MahajanRamanSikdar09}. We present a faster parameterized algorithm for deciding whether equations can be simultaneously satisfied over . As a consequence, we obtain -variable bikernels for {\sc boolean CSPs} of arity for every fixed , and for {\sc permutation CSPs} of arity 3. This implies linear bikernels for many problems under the "above average" parameterization, such as {\sc Max--Sat}, {\sc Set-Splitting}, {\sc Betweenness} and {\sc Max Acyclic Subgraph}. As a result, all the parameterized problems we consider in this paper admit -time algorithms. We also obtain non-trivial hybrid algorithms for every Max -CSP: for every instance , we can either approximate beyond the random assignment threshold in polynomial time, or we can find an optimal solution to in subexponential time.
A preliminary version of this paper has been accepted for IPEC 2011