A new approach to proving upper bounds for MAX-2-SAT

ABSTRACT

In this paper we present a new approach to proving upper bounds for the maximum 2-satisfiability problem (MAX-2-SAT). We present a new 2^K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2^N/6 bound, where N is the number of variables in an input formula, for a particular case of MAX-2-SAT, where each variable appears in at most three 2-clauses. This immediately implies a 2^N/6 bound, where N is the number of vertices in an input graph, for the independent set problem on 3-regular graphs. The key point of our improvement is a combined complexity measure for estimating the running time of an algorithm. By using a new complexity measure we are able to provide a much simpler proof of new upper bounds for MAX-2-SAT than proofs of previously known bounds.

REFERENCES

• 1: Patrizia Asirelli , Michele De Santis , Maurizio Martelli, Integrity constraints in logic databases, Journal of Logic Programming, v.2 n.3, p.221-232, Oct. 1985 [doi>10.1016/0743-1066(85)90020-2]
• 2: Nikhil Bansal , Venkatesh Raman, Upper Bounds for MaxSat: Further Improved, Proceedings of the 10th International Symposium on Algorithms and Computation, p.247-258, December 16-18, 1999
• 3: Jianer Chen , Iyad Kanj, Improved Exact Algorithms for MAX-SAT, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.341-355, April 03-06, 2002
• 4: S. S. Fedin and A. S. Kulikov. Automated proofs of upper bounds on the running time of splitting algorithms. Zapiski nauchnykh seminarov POMI, 316:111--128, 2004.
• 5: F. V. Fomin and K. Høie. Pathwidth of cubic graphs and exact algorithms. Information Processing Letters, 2005. To appear.
• 6: Herve Gallaire , Jack Minker , Jean-Marie Nicolas, Logic and Databases: A Deductive Approach, ACM Computing Surveys (CSUR), v.16 n.2, p.153-185, June 1984 [doi>10.1145/356924.356929]
• 7: Jens Gramm , Edward A. Hirsch , Rolf Niedermeier , Peter Rossmanith, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete Applied Mathematics, v.130 n.2, p.139-155, 15 August 2003 [doi>10.1016/S0166-218X(02)00402-X]
• 8: J. Kneis, D. MD. Mölle, S. Richter, and P. Rossmanith. Pathwidth of cubic graphs and exact algorithms. In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, 2005. To appear.
• 9: J. Kneis and P. Rossmanith. A new satisfiability algorithm with applications to Max-Cut. Technical Report AIB-2005-08, Department of Computer Science, RWTH Aachen University, April 2005.
• 10: A. S. Kulikov. Automated generation of simplification rules for SAT and MAXSAT. In Proceedings of the Eighth International Conference on Theory and Applications of Satisfiability Testing (SAT 2005), volume 3569 of LNCS, pages 430--436. Springer Verlag, 2005.
• 11: O. Kullmann, New methods for 3-SAT decision and worst-case analysis, Theoretical Computer Science, v.223 n.1-2, p.1-72, July 28, 1999 [doi>10.1016/S0304-3975(98)00017-6]
• 12: O. Kullmann and H. Luckhardt. Algorithms for SAT/TAUT decision based on various measures. Preprint, 1999.
• 13: R. Paturi , P. Pudlák , M. E. Saks , F. Zane, An Improved Exponential-Time Algorithm for k-SAT, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.628, November 08-11, 1998
• 14: S. Poljak and Z. Tuza. Maximum cuts and largest bipartite subgraphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20:181--244, 1995.
• 15: Venkatesh Raman , B. Ravikumar , S. Srinivasa Rao, A simplified NP-complete MAXSAT problem, Information Processing Letters, v.65 n.1, p.1-6, Jan 1, 1998 [doi>10.1016/S0020-0190(97)00223-8]
• 16: R. Williams. A new algorithm for optimal constraint satisfaction and its implications. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of LNCS, pages 1227--1237. Springer Verlag, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory