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].

68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)