# zbMATH — the first resource for mathematics

A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between. (English) Zbl 1238.68066
Summary: In this paper we introduce “hybrid” Max 2-CSP formulas consisting of “simple clauses”, namely conjunctions and disjunctions of pairs of variables, and general 2-variable clauses, which can be any integer-valued functions of pairs of boolean variables. This allows an algorithm to use both efficient reductions specific to AND and OR clauses, and other powerful reductions that require the general CSP setting. We use new reductions introduced here, and recent reductions such as “clause-learning” and “2-reductions” generalized to our setting’s mixture of simple and general clauses. We parametrize a hybrid instance by the fraction $$p$$ of non-simple clauses. We give an exact, exponential-time but polynomial-space algorithm that is the fastest known for $$p=0$$, which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses; for an $$m$$-clause instance it runs in time $$O^{\star }({2}^{m/6.321})$$. The same algorithm is tied for fastest for general Max 2-CSP ($$p=1$$), with running time $$O^{\star }({2}^{m/5.263})$$. The algorithm is the only one to treat mixtures of AND, OR, and general integer-valued clauses more efficiently than the general case, with intermediate running time bounds depending on the value of $$p$$. Since even a pure Max 2-Sat input instance may be transformed to a hybrid instance in the course of solving it, the algorithm’s efficiency and generality go hand in hand. Our algorithm analysis and optimization use the familiar measure-and-conquer approach, but in a variation resulting in mathematical programs that are convex rather than quasi-convex, and can be solved efficiently and with a certificate of optimality. We produce a family of running-time upper-bound formulas, each optimized for instances with a particular value of $$p$$ but valid for all instances.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
MAX-2-SAT
Full Text:
##### References:
  Beigel, Richard; Eppstein, David, 3-coloring in time O($$1.3289^n$$), J. algorithms, 54, 2, 168-204, (2005) · Zbl 1101.68716  Bonsma, Paul; Lokshtanov, Daniel, Feedback vertex set in mixed graphs, (), 122-133 · Zbl 1342.05180  Bansal, Nikhil; Raman, Venkatesh, Upper bounds for maxsat: further improved, (), 247-258 · Zbl 0971.68069  Eppstein, David, Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms, ACM trans. algorithms, 2, 4, 492-509, (2006) · Zbl 1321.68558  Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter, A measure & conquer approach for the analysis of exact algorithms, J. ACM, 56, 5, 1-32, (2009) · Zbl 1325.68311  Gramm, Jens; Hirsch, Edward A.; Niedermeier, Rolf; Rossmanith, Peter, Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete appl. math., 130, 2, 139-155, (2003) · Zbl 1051.68078  Gaspers, Serge; Sorkin, Gregory B., A universally fastest algorithm for MAX 2-sat, MAX 2-CSP, and everything in between, (), 606-615 · Zbl 1238.68066  Hirsch, Edward A., A new algorithm for MAX-2-SAT, (), 65-73 · Zbl 0959.68047  Kojevnikov, Arist; Kulikov, Alexander S., A new approach to proving upper bounds for MAX-2-SAT, (), 11-17 · Zbl 1192.68368  Kulikov, Alexander S.; Kutzkov, Konstantin, New bounds for MAX-SAT by clause learning, (), 194-204 · Zbl 1188.68272  Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, (), 385-396 · Zbl 1171.05428  Koivisto, Mikko, Optimal 2-constraint satisfaction via sum-product algorithms, Inform. process. lett., 98, 1, 24-28, (2006) · Zbl 1186.68439  Joachim Kneis, Peter Rossmanith, A new satisfiability algorithm with applications to Max-Cut, Tech. Report AIB-2005-08, Department of Computer Science, RWTH Aachen, 2005.  Kullmann, Oliver, Worst-case analysis, 3-SAT decision and lower bounds: approaches for improved SAT algorithms, DIMACS ser. discrete math. theoret. comput. sci., vol. 35, (1997), American Mathematical Society, pp. 261-313 · Zbl 0889.03030  Kullmann, Oliver, New methods for 3-SAT decision and worst-case analysis, Theoret. comput. sci., 223, 1-2, 1-72, (1999) · Zbl 0930.68066  Niedermeier, Rolf; Rossmanith, Peter, New upper bounds for maximum satisfiability, J. algorithms, 36, 1, 63-88, (2000) · Zbl 0959.68049  Raible, Daniel; Fernau, Henning, A new upper bound for MAX-2-SAT: A graph-theoretic approach, (), 551-562 · Zbl 1173.68539  Scott, Alexander D.; Sorkin, Gregory B., Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances, (), 382-395 · Zbl 1279.68108  Alexander D. Scott, Gregory B. Sorkin, A faster exponential-time algorithm for Max 2-Sat, Max Cut, and Max k-Cut, Tech. Report RC23456 (W0412-001), IBM Research Report, December 2004, see http://domino.research.ibm.com/library/cyberdig.nsf.  Scott, Alexander D.; Sorkin, Gregory B., Linear-programming design and analysis of fast algorithms for MAX 2-CSP, Discrete optim., 4, 3-4, 260-287, (2007) · Zbl 1153.90505  Alexander D. Scott, Gregory B. Sorkin, Polynomial constraint satisfaction: A framework for counting and sampling CSPs and other problems, Tech. Report cs:DM/0604079v3, arxiv.org, February 2007, see http://arxiv.org/abs/cs.DM/0604079.  Wahlström, Magnus, Exact algorithms for finding minimum transversals in rank-3 hypergraphs, J. algorithms, 51, 2, 107-121, (2004) · Zbl 1091.68083  Williams, Ryan, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoret. comput. sci., 348, 2-3, 357-365, (2005) · Zbl 1081.68095
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.