Polynomial-space algorithms solve dense Max 2-SAT classes exactly
Original title: Accumulating Pruning Constraints: New Exact Polynomial-Space Algorithms for Max 2-SAT
Branching records pruning constraints that discard all but an exponentially small fraction of assignments on several dense instance classes.
The paper gives deterministic polynomial-space algorithms that solve Max 2-SAT on n variables exactly in time O*(2^{(1-γ)n}) for a fixed γ>0 on several classes whose clause density may grow with n. The method extends DPLL: assigning a variable its less promising value yields a pruning constraint satisfied by some optimal assignment. Classes include formulas with many biased variables, semirandom 2-CNF formulas, and Max-Cut on regular expanders and stochastic block-model graphs. For semirandom formulas and block-model graphs the algorithms stay exact on every input, while the time bound holds with high probability over the input.
Unconfirmed: The claim that these are the first such polynomial-space algorithms is the authors' assessment.
- Pruning constraints can be added to any Max 2-SAT branching algorithm.
- Semirandom formulas allow arbitrary variable pairs, with random clauses on those pairs.
- Authors expect the constraints to help sparse formulas, where each involves few variables.
- Time bounds for semirandom and block-model inputs hold with high probability.
From the original article
1 min read at arxiv.orgWe present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(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.
By Konstantin Kutzkov · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.