A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application

Details A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application

2011-04-14

arxiv.org/abs/1104.2818v2

Computer Science

Discrete Mathematics

Scientific paper

Let $F$ be a CNF formula with $n$ variables and $m$ clauses. $F$ is $t$-satisfiable if for any $t$ clauses in $F$, there is a truth assignment which satisfies all of them. Lieberherr and Specker (1982) and, later, Yannakakis (1994) proved that in each 3-satisfiable CNF formula at least 2/3 of its clauses can be satisfied by a truth assignment. Yannakakis's proof utilizes the fact that 2/3 m$ is a lower bound on the expected number of clauses satisfied by a random truth assignment over a certain distribution. A CNF formula $F$ is called \emph{expanding} if for every subset $X$ of the variables of $F$, the number of clauses containing variables of $X$ is not smaller than $|X|.$ In this paper we strengthen the 2/3 m bound by showing that, for every expanding 3-satisfiable CNF formula $F$, at least 2/3 m + \rho n$ clauses of $F$ can be satisfied by a truth assignment, where $\rho(>0.0019)$ is a constant. Our proof uses the probabilistic method with a sophisticated distribution for truth values. We use the bound 2/3 m + \rho n$ and results on matching autarkies to obtain a new lower bound on the maximum number of clauses that can be satisfied by a truth assignment in any 3-satisfiable CNF formula. We apply our results above to show that the following parameterized problem is fixed-parameter tractable and, moreover, has a kernel with a linear number of variables. In {\sc 3-Sat-SAT-AE}, we are given a 3-satisfiable CNF formula $F$ with $m$ clauses and asked to determine whether there is an assignment which satisfies at least 2/3}m + k$ clauses, where $k$ is the parameter.

Affiliated with

Also associated with

No associations

Rating

A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application 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 A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A New Bound for 3-Satisfiable MaxSat and its Algorithmic Application will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-167052