Improved MaxSAT Algorithms for Instances of Degree 3
Additional Document Info
Springer International Publishing Switzerland 2015. The degree of a variable xi in a MaxSAT instance is the number of times xi and xi appearing in the given formula. The degree of a MaxSAT instance is equal to the largest variable degree in the instance. In this paper, we study techniques for solving the MaxSAT problem on instances of degree 3 (briefly, (n, 3)-MaxSAT), which is NP-hard. Two new non-trivial reduction rules are introduced based on the resolution principle. As applications, we present two algorithms for the (n, 3)-MaxSAT problem: a parameterized algorithm of time O(1.194k), and an exact algorithm of time O(1.237n), improving the previous best upper bounds O(1.2721k) and O(1.2600n), respectively.
name of conference
Combinatorial Optimization and Applications - 9th International Conference, COCOA 2015, Houston, TX, USA, December 18-20, 2015, Proceedings