Solving MAX-r-SAT Above a Tight Lower Bound

Details Solving MAX-r-SAT Above a Tight Lower Bound Solving MAX-r-SAT Above a Tight Lower Bound

2009-07-27

arxiv.org/abs/0907.4573v4

Computer Science

Data Structures and Algorithms

Scientific paper

We present an exact algorithm that decides, for every fixed $r \geq 2$ in time $O(m) + 2^{O(k^2)}$ whether a given multiset of $m$ clauses of size $r$ admits a truth assignment that satisfies at least $((2^r-1)m+k)/2^r$ clauses. Thus \textsc{Max-$r$-Sat} is fixed-parameter tractable when parameterized by the number of satisfied clauses above the tight lower bound $(1-2^{-r})m$. This solves an open problem of Mahajan et al. (J. Comput. System Sci., 75, 2009). Our algorithm is based on a polynomial-time data reduction procedure that reduces a problem instance to an equivalent algebraically represented problem with $O(k^2)$ variables. This is done by representing the instance as an appropriate polynomial, and by applying a probabilistic argument combined with some simple tools from Harmonic analysis to show that if the polynomial cannot be reduced to one of size $O(k^2)$, then there is a truth assignment satisfying the required number of clauses. We introduce a new notion of bikernelization from a parameterized problem to another one and apply it to prove that the above-mentioned parameterized \textsc{Max-$r$-Sat} admits a polynomial-size kernel. Combining another probabilistic argument with tools from graph matching theory and signed graphs, we show that if an instance of \textsc{Max-2-Sat} with $m$ clauses has at least $3k$ variables after application of certain polynomial time reduction rules to it, then there is a truth assignment that satisfies at least $(3m+k)/4$ clauses. We also outline how the fixed-parameter tractability and polynomial-size kernel results on \textsc{Max-$r$-Sat} can be extended to more general families of Boolean Constraint Satisfaction Problems.

Affiliated with

Also associated with

No associations

Rating

Solving MAX-r-SAT Above a Tight Lower Bound does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solving MAX-r-SAT Above a Tight Lower Bound, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving MAX-r-SAT Above a Tight Lower Bound will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-245733