skip to main content
10.5555/1109557.1109559acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

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

Published: 22 January 2006 Publication History

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 2K/5.5-time algorithm for MAX-2-SAT, where K is the number of clauses in an input formula. We also obtain a 2N/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 2N/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]
P. Asirelli, M. De Santis, and M. Martelli. Integrity constraints in logic databases. Journal of Logic Programming, 3:221--232, 1985.]]
[2]
N. Bansal and V. Raman. Upper bounds for MaxSat: Further improved. In Proceedings of ISAAC'99, pages 247--258, 1999.]]
[3]
J. Chen and I. Kanj. Improved exact algorithms for MAX-SAT. In Proceedings of the 5th LATIN, volume 2286 of LNCS, pages 341--355, 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]
H. Gallaire, J. Minker, and J.-M. Nicolas. Logic and databases: A deductive approach. ACM Computing Surveys, 16(2):153--185, June 1984.]]
[7]
J. Gramm, E. A. Hirsch, R. Niedermeier, and P. Rossmanith. Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics, 130(2):139--155, 2003.]]
[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, 223:1--72, 1997.]]
[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, and F. Zane. An improved exponential-time algorithm for k-SAT. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science. (FOCS-98), pages 628--637, Palo Alto, CA, November 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]
V. Raman, B. Ravikumar, and S. Srinivasa Rao. A simplified NP-complete MAXSAT problem. Information Processing Letters, 65(1):1--6, 1998.]]
[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.]]

Cited By

View all
  • (2014)New exact algorithms for the 2-constraint satisfaction problemTheoretical Computer Science10.1016/j.tcs.2014.01.010526(18-27)Online publication date: 1-Mar-2014
  • (2011)New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degreeProceedings of the 6th international conference on Parameterized and Exact Computation10.1007/978-3-642-28050-4_9(106-117)Online publication date: 6-Sep-2011
  • (2010)Maximum independent set in graphs of average degree at most three in O(1.08537n)Proceedings of the 7th annual conference on Theory and Applications of Models of Computation10.1007/978-3-642-13562-0_34(373-384)Online publication date: 7-Jun-2010
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm
January 2006
1261 pages
ISBN:0898716055

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 22 January 2006

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)1
Reflects downloads up to 13 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2014)New exact algorithms for the 2-constraint satisfaction problemTheoretical Computer Science10.1016/j.tcs.2014.01.010526(18-27)Online publication date: 1-Mar-2014
  • (2011)New upper bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the average variable degreeProceedings of the 6th international conference on Parameterized and Exact Computation10.1007/978-3-642-28050-4_9(106-117)Online publication date: 6-Sep-2011
  • (2010)Maximum independent set in graphs of average degree at most three in O(1.08537n)Proceedings of the 7th annual conference on Theory and Applications of Models of Computation10.1007/978-3-642-13562-0_34(373-384)Online publication date: 7-Jun-2010
  • (2009)A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in betweenProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496837(606-615)Online publication date: 4-Jan-2009
  • (2009)A measure & conquer approach for the analysis of exact algorithmsJournal of the ACM10.1145/1552285.155228656:5(1-32)Online publication date: 21-Aug-2009
  • (2009)Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3Journal of Discrete Algorithms10.1016/j.jda.2008.09.0047:2(191-212)Online publication date: 1-Jun-2009
  • (2008)Applying practice to theoryACM SIGACT News10.1145/1466390.146640139:4(37-52)Online publication date: 30-Nov-2008
  • (2008)A New Upper Bound for Max-2-SATProceedings of the 33rd international symposium on Mathematical Foundations of Computer Science10.1007/978-3-540-85238-4_45(551-562)Online publication date: 25-Aug-2008
  • (2007)New bounds for MAX-SAT by clause learningProceedings of the Second international conference on Computer Science: theory and applications10.5555/2391910.2391931(194-204)Online publication date: 3-Sep-2007
  • (2007)Exact Max 2-SatProceedings of the 33rd conference on Current Trends in Theory and Practice of Computer Science10.1007/978-3-540-69507-3_22(272-283)Online publication date: 20-Jan-2007

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media