Dealing With 4-Variables by Resolution: An Improved MaxSAT Algorithm

Abstract

We study techniques for solving the Maximum Satisfiability problem (MaxSAT). Our focus is on variables of degree 4. We identify cases for degree-4 variables and show how the resolution principle and the kernelization techniques can be nicely integrated to achieve more efficient algorithms for the MaxSAT problem. As a result, we present an algorithm of time $O^{\ast }(1.3248^k)$ for the MaxSAT problem, improving the previous best upper bound $O^{\ast }(1.358^k)$ by Ivan Bliznets and Alexander.