Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT
cs.DS, cs.AI
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: Project folder with Lean verification: https://github.com/konstantinkutzkov/max-2-sat-arxiv
License: http://creativecommons.org/licenses/by/4.0/
The gist: We present deterministic polynomial-space algorithms that solve Max 2-SAT on n variables exactly in time (2(1-γ)n), for a fixed γ>0…
Terminology
Abstract
We present deterministic polynomial-space algorithms that solve Max 2-SAT on n variables exactly in time (2(1-γ)n), for a fixed γ>0, on several classes of instances whose clause density may grow with n. Our main tool extends the classic DPLL branching algorithm. When the search gives a variable its less promising value, comparing the two values of the variable yields a pruning constraint that is satisfied by some optimal assignment. Accumulating these constraints along each branch prunes all but an exponentially small fraction of the assignments. The classes are formulas with many biased variables, semirandom 2-CNF formulas, and Max-Cut on regular expander graphs and on graphs generated by a stochastic block model. In a semirandom formula, the pairs of variables that may share a clause are arbitrary, and the clauses on these pairs are random. For semirandom formulas and block-model graphs, the algorithms are still exact on every input, and the time bound holds with high probability over the input. To our knowledge, these are the first polynomial-space algorithms with such a running time for nontrivial classes of dense Max 2-SAT instances. Beyond these classes, the pruning constraints can be added to any branching algorithm for Max 2-SAT, and we expect them to be of practical relevance for general formulas, in particular for sparse ones, where each constraint involves only a few variables.
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time