New Algorithms for #2-SAT and #3-SAT

Junqiang Peng, Zimo Sheng, Mingyu XiaoIJCAI 2025 · DOI

TL;DR

This paper introduces novel algorithms for counting satisfying assignments of Boolean formulas, specifically for the #2-SAT and #3-SAT problems. The authors achieve significant improvements in runtime by developing new reduction rules and leveraging path decompositions on graph representations of the formulas, leading to faster algorithms for weighted and unweighted versions of these problems.

What Problem Does This Paper Address?

The paper tackles the problem of Weighted Model Counting (WMC), which is the task of calculating the sum of weights of all satisfying assignments for a given Boolean formula with weighted literals. This is a generalization of the well-known #SAT problem, where all literals have equal weights. Specifically, the authors focus on the restricted cases of WMC for 2-Conjunctive Normal Form (2-CNF) and 3-CNF formulas, known as weighted #2-SAT and weighted #3-SAT.

Counting satisfying assignments is a computationally challenging problem, fundamental to areas like artificial intelligence (probabilistic inference) and computer science (complexity theory). While algorithms exist for SAT (determining if any satisfying assignment exists), counting all of them is significantly harder, belonging to the #P-complete complexity class. Previous state-of-the-art algorithms for weighted #2-SAT and #3-SAT had certain runtime complexities. This paper aims to improve these bounds, particularly when the complexity is parameterized by the number of clauses ($m$), pushing the boundaries of what's computationally feasible for these problems.

Methods

The core of the paper lies in developing new algorithms, Alg2CNF for #2-SAT and Alg3CNF for #3-SAT, that improve upon existing runtime bounds. These algorithms follow a general framework:

  1. Reduction Rules: A set of novel reduction rules are introduced to simplify the input formula without changing the WMC value. These rules are designed to handle various structural properties of the formula, including eliminating redundant clauses, tautologies, and simplifying clauses with repeated or complementary literals. Some rules are specifically designed to handle low-degree variables or to partition the problem into smaller subproblems.
  2. Branching: When reduction rules can no longer simplify the formula, the algorithms employ a branch-and-search strategy. This involves selecting a variable and recursively solving the problem for both possible assignments (true and false) to that variable. The analysis of these branching operations is crucial for determining the overall runtime.
  3. Path Decomposition and Dynamic Programming: A key innovation is the use of path decompositions on the primal and dual graphs of the formula. These graphs represent structural relationships between variables and clauses. By transforming these graphs into a path-like structure, the authors can leverage dynamic programming techniques (specifically, algorithms based on pathwidth) to efficiently solve the problem when the formula has certain structural properties (e.g., low pathwidth). This is particularly effective for handling cases where variables have low degrees after the initial reduction phase.

The algorithms are designed to first aggressively reduce the problem using the new rules, then branch on high-degree variables, and finally, when the remaining structure is amenable, use path decomposition-based methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis for arbitrary CNF formulas, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Path Decomposition for Low-Degree Cases: The most significant insight is the effective use of path decompositions on primal and dual graphs to handle low-degree variable cases. This departs from traditional branching strategies that often struggle with such variables.
  • Novel Reduction Rules: The introduction of new reduction rules is critical for simplifying the formulas before branching or applying path decomposition, leading to more efficient processing.
  • Parameterization by Clauses ($m$): The paper demonstrates that significant improvements can be made by parameterizing the runtime by the number of clauses ($m$), rather than solely by the number of variables ($n$). This is a crucial distinction for certain classes of problems.
  • Combining Techniques: The algorithms elegantly combine reduction rules, branching, and structural decomposition (pathwidth) to achieve their improved bounds, showcasing a powerful hybrid approach.

Key Results

The paper presents two main algorithmic contributions:

  • Weighted #2-SAT: An algorithm, Alg2CNF, that solves weighted #2-SAT in O*(1.1082m) time, where $m$ is the number of clauses. This is a substantial improvement over previous results.
  • Weighted #3-SAT: An algorithm, Alg3CNF, that solves weighted #3-SAT in O*(1.4423m) time, where $m$ is the number of clauses. This also represents a significant improvement.

These results directly apply to the unweighted versions of #2-SAT and #3-SAT as well. The analysis involves deriving complex branching vectors and leveraging pathwidth bounds derived from graph theory.

Limitations and Future Work

  • Open Question for $c < 2$: The authors note that it remains an open question whether a running time bound of $O^*(cm)$ with a constant $c < 2$ can be achieved for WMC on $k$-CNF formulas for any constant $k$.
  • Practicality of Path Decomposition: While the algorithms are theoretically efficient, the practical performance of path decomposition-based methods in model counters is an area for further investigation. The authors suggest that their approach holds promise for practical applications.
  • Generalization: The paper focuses on #2-SAT and #3-SAT. Extending these techniques to general $k$-SAT or other related counting problems could be a future direction.

Summary updated

BibTeX
@inproceedings{peng2025new,
  author = {Junqiang Peng and Zimo Sheng and Mingyu Xiao},
  title = {{New Algorithms for \#2-SAT and \#3-SAT}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/297},
}
Figure