A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between.

*(English)*Zbl 1238.68066Summary: 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.) |

##### Keywords:

exponential-time algorithm; polynomial space; satisfiability; constraint satisfaction; hybrid instances; measure and conquer; convex programming##### Software:

MAX-2-SAT
PDF
BibTeX
XML
Cite

\textit{S. Gaspers} and \textit{G. B. Sorkin}, J. Comput. Syst. Sci. 78, No. 1, 305--335 (2012; Zbl 1238.68066)

Full Text:
DOI

##### References:

[1] | Beigel, Richard; Eppstein, David, 3-coloring in time O(\(1.3289^n\)), J. algorithms, 54, 2, 168-204, (2005) · Zbl 1101.68716 |

[2] | Bonsma, Paul; Lokshtanov, Daniel, Feedback vertex set in mixed graphs, (), 122-133 · Zbl 1342.05180 |

[3] | Bansal, Nikhil; Raman, Venkatesh, Upper bounds for maxsat: further improved, (), 247-258 · Zbl 0971.68069 |

[4] | Eppstein, David, Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms, ACM trans. algorithms, 2, 4, 492-509, (2006) · Zbl 1321.68558 |

[5] | 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 |

[6] | 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 |

[7] | 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 |

[8] | Hirsch, Edward A., A new algorithm for MAX-2-SAT, (), 65-73 · Zbl 0959.68047 |

[9] | Kojevnikov, Arist; Kulikov, Alexander S., A new approach to proving upper bounds for MAX-2-SAT, (), 11-17 · Zbl 1192.68368 |

[10] | Kulikov, Alexander S.; Kutzkov, Konstantin, New bounds for MAX-SAT by clause learning, (), 194-204 · Zbl 1188.68272 |

[11] | Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, (), 385-396 · Zbl 1171.05428 |

[12] | Koivisto, Mikko, Optimal 2-constraint satisfaction via sum-product algorithms, Inform. process. lett., 98, 1, 24-28, (2006) · Zbl 1186.68439 |

[13] | 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. |

[14] | 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 |

[15] | Kullmann, Oliver, New methods for 3-SAT decision and worst-case analysis, Theoret. comput. sci., 223, 1-2, 1-72, (1999) · Zbl 0930.68066 |

[16] | Niedermeier, Rolf; Rossmanith, Peter, New upper bounds for maximum satisfiability, J. algorithms, 36, 1, 63-88, (2000) · Zbl 0959.68049 |

[17] | Raible, Daniel; Fernau, Henning, A new upper bound for MAX-2-SAT: A graph-theoretic approach, (), 551-562 · Zbl 1173.68539 |

[18] | 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 |

[19] | 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. |

[20] | 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 |

[21] | 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. |

[22] | Wahlström, Magnus, Exact algorithms for finding minimum transversals in rank-3 hypergraphs, J. algorithms, 51, 2, 107-121, (2004) · Zbl 1091.68083 |

[23] | 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.