# zbMATH — the first resource for mathematics

Solving sparse instances of Max SAT via width reduction and greedy restriction. (English) Zbl 1347.68312
Summary: We present a moderately exponential time and polynomial space algorithm for sparse instances of Max SAT. Our algorithms run in time of the form $$O\left (2^{(1-\mu (c))n}\right )$$ for instances with $$n$$ variables and cn clauses. Our deterministic and randomized algorithm achieve $$\mu (c) = {\varOmega }\left (\frac {1}{c^{2}\log ^{2} c}\right )$$ and $$\mu (c) = {\varOmega }\left (\frac {1}{c \log ^{3} c}\right )$$ respectively. Previously, an exponential space deterministic algorithm with $$\mu (c) = {\varOmega }\left (\frac {1}{c\log c}\right )$$ was shown by E. Dantsin and A. Wolpert [Lect. Notes Comput. Sci. 4121, 266–276 (2006; Zbl 1187.68258)] and a polynomial space deterministic algorithm with $$\mu (c) = {\varOmega }\left (\frac {1}{2^{O(c)}}\right )$$ was shown by A. S. Kulikov and K. Kutzkov [Lect. Notes Comput. Sci. 4649, 194–204 (2007; Zbl 1188.68272)]. Our algorithms have three new features. They can handle instances with (1) weights and (2) hard constraints, and also (3) they can solve counting versions of Max SAT. Our deterministic algorithm is based on the combination of two techniques, width reduction of Schuler and greedy restriction of Santhanam. Our randomized algorithm uses random restriction instead of greedy restriction.

##### MSC:
 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) 68Q25 Analysis of algorithms and problem complexity
MAX-2-SAT
Full Text:
##### References:
  Bansal, N., Raman, V.: Upper bounds for MaxSAT: Further improved. In: Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 1741, pp 247-258. Springer (1999) · Zbl 0971.68069  Binkele-Raible, D; Fernau, H, A new upper bound for MAX-2-SAT: a graph-theoretic approach, J. Discret. Algorithm., 8, 388-401, (2010) · Zbl 1203.90130  Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science, vol. 7535, pp 37-48. Springer (2012) · Zbl 1360.68494  Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), pp. 252-260 (2006) · Zbl 1286.68208  Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Revised Selected Papers from the 4th International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 5917, pp 75-85 (2009) · Zbl 1273.68159  Chen, J; Kanj, IA, Improved exact algorithms for MAX-SAT, Discret. Appl. Math., 142, 17-27, (2004) · Zbl 1077.68116  Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. Electronic Colloquium on Computational Complexity (ECCC) TR13-057 (2013). Also. In: Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC), pp. 262-273 (2014) · Zbl 1401.68116  Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in $$O$$(2\^{$$n$$}) time. In: Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing (SAT), Lecture Notes in Computer Science, vol. 4121, pp 266-276. Springer (2006) · Zbl 1187.68258  Gaspers, S; Sorkin, GB, A universally fastest algorithm for MAX 2-SAT, MAX 2-CSP, and everything in between, J. Comput. Syst. Sci., 78, 305-335, (2012) · Zbl 1238.68066  Gramm, J; Hirsch, EA; Niedermeier, R; Rossmanith, P, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discret. Appl. Math., 130, 139-155, (2003) · Zbl 1051.68078  Gramm, J., Niedermeier, R.: Faster exact solutions for MAX2SAT. In: Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science, vol. 1767, pp 174-186. Springer (2000) · Zbl 0971.68598  Gutin, G., Yeo, A.: Constraint satisfaction problems parameterized above or below tight bounds: A survey. In: The Multivariate Algorithmic Revolution and Beyond, Lecture Notes in Computer Science, vol. 7370, pp 257-286. Springer (2012) · Zbl 1358.68135  Håstad, J, The shrinkage exponent of De Morgan formulas is 2. SIAM, J. Comput., 27, 48-64, (1998) · Zbl 0907.68107  Hirsch, E.A.: A new algorithm for MAX-2-SAT. In: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 1770, pp 65-73. Springer (2000) · Zbl 0959.68047  Hirsch, EA, Worst-case study of local search for MAX-k-SAT, Discret. Appl. Math., 130, 173-184, (2003) · Zbl 1051.68079  Horowitz, E; Sahni, S, Computing partitions with applications to the knapsack problem, J. ACM, 21, 277-292, (1974) · Zbl 0329.90046  Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC\^{0}. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 961-972 (2012) · Zbl 1423.68583  Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 479-488 (2013)  Kneis, J., Mölle, D., Richter, S., Rossmanith, P.: On the parameterized complexity of exact satisfiability problems. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 3618, pp 568-579. Springer (2005) · Zbl 1156.68404  Kneis, J; Mölle, D; Richter, S; Rossmanith, P, A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM, J. Discret. Math, 23, 407-427, (2009) · Zbl 1219.05187  Koivisto, M, Optimal 2-constraint satisfaction via sum-product algorithms, Inf. Process. Lett., 98, 24-28, (2006) · Zbl 1186.68439  Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11-17 (2006) · Zbl 1192.68368  Kulikov, A.S.: Automated generation of simplification rules for SAT and MAXSAT. In: Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing (SAT), Lecture Notes in Computer Science, vol. 3569, pp 430-436. Springer (2005) · Zbl 1128.68469  Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: Proceedings of the 8th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science, vol. 4649, pp 194-204. Springer (2007) · Zbl 1188.68272  Mahajan, M; Raman, V, Parameterizing above guaranteed values: maxsat and maxcut, J. Algorithm., 31, 335-354, (1999) · Zbl 0921.68052  Niedermeier, R; Rossmanith, P, New upper bounds for maximum satisfiability, J. Algorithm., 36, 63-88, (2000) · Zbl 0959.68049  Santhanam, R.: Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In: Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 183-192 (2010) · Zbl 1186.68439  Schuler, R, An algorithm for the satisfiability problem of formulas in conjunctive normal form, J. Algorithm., 54, 40-44, (2005) · Zbl 1090.68052  Scott, A.D., Sorkin, G.B.: Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 7th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science, vol. 2764, pp 382-395. Springer (2003) · Zbl 1279.68108  Scott, AD; Sorkin, GB, Linear-programming design and analysis of fast algorithms for MAX 2-CSP, Discret. Optim., 4, 260-287, (2007) · Zbl 1153.90505  Seto, K; Tamaki, S, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, Comput. Complex., 22, 245-274, (2013) · Zbl 1286.68208  Williams, R, A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci., 348, 357-365, (2005) · Zbl 1081.68095  Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1, 2), 1-32 (2014) · Zbl 1295.68117
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.