zbMATH — the first resource for mathematics

A new algorithm for MAX-2-SAT. (English) Zbl 0959.68047
Reichel, Horst (ed.) et al., STACS 2000. 17th annual symposium on Theoretical aspects of computer science. Lille, France, February 17-19, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1770, 65-73 (2000).
Summary: Recently there was a significant progress in proving (exponential-time) worst-case upper bounds for the propositional SATisfiability problem (SAT) and related problems. In particular, for MAX-2-SAT Niedermeier and Rossmanith recently presented an algorithm with worst-case upper bound $$O(K\cdot 2^{K/2.88\dots})$$, and the bound $$O(K\cdot 2^{K/3.44\dots})$$ is implicit from the paper by Bansal and Raman ($$K$$ is the number of clauses). In this paper we improve this bound to $$p(K)2^{K_2/4}$$, where $$K_2$$ is the number of 2-clauses, and $$p$$ is a polynomial. In addition, our algorithm and the proof are much simpler than the previous ones. The key ideas are to use the symmetric flow algorithm of Yannakakis and to count only 2-clauses (and not 1-clauses).
For the entire collection see [Zbl 0933.00044].

MSC:
 68Q25 Analysis of algorithms and problem complexity 03D15 Complexity of computation (including implicit computational complexity)
Keywords:
satisfiability problem
MAX-2-SAT