zbMATH — the first resource for mathematics

Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. (English) Zbl 1051.68078
Summary: The maximum 2-satisfiability problem (MAX-2-SAT) is: given a Boolean formula in 2-CNF, find a truth assignment that satisfies the maximum possible number of its clauses. MAX-2-SAT is MAX-SNP-complete. Recently, this problem received much attention in the contexts of (polynomial-time) approximation algorithms and (exponential-time) exact algorithms. In this paper, we present an exact algorithm solving MAX-2-SAT in time poly\((L)\cdot 2^{K/5}\), where \(K\) is the number of clauses and \(L\) is their total length. In fact, the running time is only poly\((L)\cdot 2^{K_2/5}\), where \(K_2\) is the number of clauses containing two literals. This bound implies the bound poly\((L)\cdot 2^{L/10}\). Our results significantly improve previous bounds: poly\((L)\cdot 2^{K/2.88}\) [R. Niedermeier and P. Rossmanith, J. Algorithms 36, 63–88 (2000; Zbl 0959.68049)] and poly\((L)\cdot 2^{K/3.44}\) [implicit in N. Bansal and V. Raman, Lect. Notes Comput. Sci. 1741, 247–258 (1999; Zbl 0971.68069)].
As an application, we derive upper bounds for the (MAX-SNP-complete) maximum cut problem (MAX-CUT), showing that it can be solved in time poly\((M)\cdot 2^{M/3}\), where \(M\) is the number of edges in the graph. This is of special interest for graphs with low vertex degree.

68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] S. Arora, C. Lund, Hardness of approximation, in: D. Hochbaum (Ed.), Approximation Algorithms for NP-Hard Problems, Chapter 10, PWS Publishing Company, Boston, 1997, pp. 399-446.
[2] T. Asano, D.P. Williamson, Improved approximation algorithms for MAX SAT, in: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’00, 2000, pp. 96-105. · Zbl 0952.90019
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi. Complexity and Approximation—Combinatorial Optimization Problems and their Approximability Properties, Springer, Berlin, 1999. · Zbl 0937.68002
[4] N. Bansal, V. Raman, Upper bounds for MaxSat: further improved, in: A. Aggarwal, C. Pandu Rangan (Eds.), Proceedings of the 10th Annual Conference on Algorithms and Computation, ISAAC’99, Lecture Notes in Computer Science, Vol. 174, Springer, Berlin, 1999, pp. 247-258. · Zbl 0971.68069
[5] R. Beigel, Finding maximum independent sets in sparse and general graphs, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’99, 1999, pp. 856-857. · Zbl 0938.68073
[6] P. Berman, M. Karpinski, On some tighter inapproximability results, in: Proceedings of the 26th International Colloquium on Automata, Languages and Programming, ICALP’99, Lecture Notes in Computer Science, Vol. 1644, Springer, Berlin, 1999, pp. 200-209.
[7] Borchers, B.; Furman, J., A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems, J. combin. optim., 2, 4, 299-306, (1999) · Zbl 0954.90026
[8] Cai, L.; Chen, J., On fixed-parameter tractability and approximability of NP optimization problems, J. comput. system sci., 54, 465-474, (1997) · Zbl 0882.68064
[9] Cheriyan, J.; Cunningham, W.H.; Tunçel, L.; Wang, Y., A linear programming and rounding approach to MAX 2-sat, DIMACS ser. discrete math. theoret. comput. sci., 26, 395-414, (1996) · Zbl 0864.90102
[10] E. Dantsin, Two propositional proof systems based on the splitting method, Zapiski Nauchnykh Seminarov LOMI, 105 (1981) 24-44 (in Russian). English translation: J. Soviet Math. 22 (3) (1983) 1293-1305 .
[11] Dantsin, E.; Gavrilovich, M.; Hirsch, E.A.; Konev, B., MAX SAT approximation beyond the limits of polynomial-time approximation, Ann. pure appl. logic, 113, 81-94, (2001) · Zbl 0990.03006
[12] E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, U. Schöning, A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search, Theoret. Comput. Sci. (2002), to appear. · Zbl 1061.68071
[13] E. Dantsin, A. Goerdt, E.A. Hirsch, U. Schöning, Deterministic algorithms for k-SAT based on covering codes and local search, in: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, ICALP’00, Lecture Notes in Computer Science, Vol. 1853, Springer, Berlin, 2000, pp. 236-243. · Zbl 0973.68253
[14] Davis, M.; Logemann, G.; Loveland, D., A machine program for theorem-proving, Comm. ACM, 5, 7, 394-397, (1962) · Zbl 0217.54002
[15] Davis, M.; Putnam, H., A computing procedure for quantification theory, J. ACM, 7, 3, 201-215, (1960) · Zbl 0212.34203
[16] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer-Verlag Berlin
[17] U. Feige, M.X. Goemans, Approximating the value of two proper proof systems, with applications to MAX-2SAT and MAX-DICUT, in: Proceedings of the Third Israel Symposium on Theory and Computing Systems, 1995, pp. 182-189.
[18] J. Gramm, Exact algorithms for Max2Sat and their applications, Diploma thesis, WSI für Informatik, Universität Tübingen, October 1999, available from http://www-fs.informatik.uni-tuebingen.de/ gramm/publications/.
[19] J. Gramm, R. Niedermeier, Faster exact solutions for Max-2-Sat, in: Proceedings of the Fourth Italian Conference on Algorithms and Complexity, CIAC 2000, Lecture Notes in Computer Science, Vol. 1767, Springer, Berlin, 2000, pp. 174-186. · Zbl 0971.68598
[20] J. Håstad, Some optimal inapproximability results, in: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC’97, Journal of the ACT 48 (2001) 798-859. · Zbl 1127.68405
[21] E.A. Hirsch, A 2^K/4-time algorithm for MAX-2-SAT: Corrected version, Technical Report 99-036, Revision 02, Electronic Colloquim on Computational Complexity, February 2000, electronic address: ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/1999/TR99-036/revisn02.ps.
[22] E.A. Hirsch, A new algorithm for MAX-2-SAT, in: Proceedings of the 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lecture Notes in Computer Science, Vol. 1770, Springer-Verlag, Berlin, February 2000, pp. 65-73 (contains an error, fixed in [21]). · Zbl 0959.68047
[23] Hirsch, E.A., New worst-case upper bounds for SAT, J. automat. reason., 24, 4, 397-420, (2000) · Zbl 0960.03009
[24] E.A. Hirsch, Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search, in: Proceedings of RANDOM 2000, ICALP Workshops 2000, Proceedings in Informatics, Vol. 8, 2000, pp. 69-76.
[25] H. Karloff, U. Zwick, A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 406-415.
[26] Kullmann, O., New methods for 3-SAT decision and worst-case analysis, Theoret. comput. sci., 223, 1-2, 1-72, (1999) · Zbl 0930.68066
[27] O. Kullmann, H. Luckhardt, Algorithms for SAT/TAUT decision based on various measures. preprint, 71 pages, available from http://www.cs.toronto.edu/ kullmann February 1999.
[28] Mahajan, M.; Raman, V., Parameterizing above guaranteed valuesmaxsat and maxcut, J. algorithms, 31, 335-354, (1999) · Zbl 0921.68052
[29] Monien, B.; Speckenmeyer, E., Solving satisfiability in less then 2^n steps, Discrete appl. math., 10, 287-295, (1985) · Zbl 0603.68092
[30] Niedermeier, R.; Rossmanith, P., New upper bounds for maxsat, J. algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[31] Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033
[32] R. Paturi, P. Pudlák, M.E. Saks, F. Zane, An improved exponential-time algorithm for k-SAT, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS’98, 1998, pp. 628-637. · Zbl 1297.68217
[33] Poljak, S.; Tuza, Z., Maximum cuts and large bipartite subgraphs, DIMACS ser. discrete math. theoret. comput. sci., 20, 181-244, (1995) · Zbl 0834.05001
[34] Raman, V.; Ravikumar, B.; Srinivasa Rao, S., A simplified NP-complete MAXSAT problem, Inform. process. lett., 65, 1, 1-6, (1998) · Zbl 1339.68122
[35] Robinson, J.A., Generalized resolution principle, Mac. intell., 3, 77-94, (1968) · Zbl 0195.31102
[36] U. Schöning, A probabilistic algorithm for k-SAT and constraint satisfaction problems, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, FOCS’99, 1999, pp. 410-414.
[37] R. Schuler, U. Schöning, O. Watnabe, T. Hofemister, A probabilistic 3-SAT algorithm further improved, Proceedings of 19th International Symposium on Theoretical Aspects of Computer Science, STACS 2002, Lecture Notes in Computer Science, 2285, Springer, 2002, 192-202.
[38] Yannakakis, M., On the approximation of maximum satisfiability, J. algorithms, 17, 3, 457-502, (1994) · Zbl 0820.68056
[39] U. Zwick, personal communication, 2000.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.