Fast Algorithms for SAT with Bounded Occurrences of Variables

Junqiang Peng, Mingyu XiaoIJCAI 2023 · DOI

TL;DR

This paper presents new, faster algorithms for solving the Boolean Satisfiability Problem (SAT) when variables appear a limited number of times. Specifically, they achieve significant improvements for the cases where variables occur 3 or 4 times, breaking long-standing records and offering a slight improvement for higher occurrence bounds.

What Problem Does This Paper Address?

The Boolean Satisfiability Problem (SAT) is a fundamental problem in computer science: given a logical formula in conjunctive normal form (CNF), can we find an assignment of truth values to its variables that makes the entire formula true? While SAT is NP-complete, researchers have explored faster algorithms for specific, restricted versions of the problem. One such restriction is bounding the maximum number of times any variable appears in the formula. This is particularly interesting because algorithms for these restricted cases often serve as building blocks for more general SAT solvers. Previous work had established certain running time bounds for SAT with bounded variable occurrences, but the cases for 3 and 4 occurrences had remained challenging bottlenecks for nearly two decades. This paper aims to break these bottlenecks and improve the state-of-the-art for these specific scenarios.

Methods

The authors employ a branch-and-search approach, a common paradigm for exact algorithms in SAT. This involves:

  • Reduction Rules: A set of rules is applied to simplify the input formula without changing its satisfiability. These rules aim to eliminate variables or clauses, making the problem smaller. The paper introduces several new reduction rules (R-Rules 8-14) to handle specific clause structures and variable relationships more efficiently.
  • Branching Strategy: When reduction rules can no longer simplify the formula, the algorithm "branches" by picking a variable and exploring two possibilities: assigning it true or assigning it false. This creates a search tree.
  • Measure and Conquer: To analyze the algorithm's efficiency, the authors use a "measure" that quantifies the "size" of the problem instance. This measure is a weighted sum of variables, where the weights depend on the variables' degrees (number of occurrences). A tunable parameter ($\lambda$) is introduced into these weights, allowing for flexible analysis and optimization for different ranges of variable occurrences.
  • Worst-Case Analysis: The core of the analysis lies in identifying the "worst-case branching vector" at each step. This vector represents the decrease in the problem's measure when branching. The algorithm's overall running time is determined by the largest branching factor across all steps. The paper meticulously analyzes various branching scenarios, leveraging lemmas about reduced formulas and variable degrees to bound the measure reduction.

The key novelty lies in the specific combination of new reduction rules and a refined analysis of branching strategies, particularly for variables with degrees 3 and 4. They also introduce a technique to replace some degree-4 variables with degree-3 variables, simplifying the analysis.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Breaking Bottlenecks: The most significant insight is that by carefully designing new reduction rules and analyzing specific branching scenarios, the long-standing bottlenecks for SAT with 3 and 4 variable occurrences can be overcome.
  • Tunable Parameter for Analysis: The introduction of a tunable parameter ($\lambda$) in the variable weights is a powerful analytical tool. It allows the same algorithmic framework to yield different, optimized running-time bounds for different ranges of variable occurrences (e.g., better for $d=3,4$ vs. better for $d \ge 5$).
  • Interplay of Reduction and Branching: The paper highlights how new reduction rules can simplify the analysis of branching steps, leading to improved bounds. For instance, R-Rules 8-14 are crucial for handling specific clause configurations that were previously problematic.
  • "Good" N-monotone Clauses: The analysis of N-monotone 2-clauses (clauses with only negative literals) is broken down into "good" and "not good" cases, with specific branching strategies tailored to each. This detailed case analysis is key to achieving tight bounds.

Key Results

The paper presents improved worst-case running-time bounds for SAT with bounded variable occurrences:

  • For $d=3$ (maximum 3 occurrences per variable): The new bound is $O^*(1.1238^n)$, an improvement over the previous $O^*(1.1279^n)$.
  • For $d=4$ (maximum 4 occurrences per variable): The new bound is $O^*(1.2628^n)$, an improvement over the previous $O^*(1.2721^n)$.
  • For $d \ge 5$: The new bound is $O^*(1.0641^d n)$, which is a slight improvement over the previous $O^*(1.0646^d n)$. This also translates to $O^*(1.0641^L)$ with respect to formula length $L$.

These results are achieved using the measure-and-conquer technique with a tunable parameter $\lambda$.

Limitations and Future Work

  • Theoretical Focus: The paper presents theoretical worst-case bounds. The practical performance of these algorithms on real-world SAT instances is not discussed.
  • Complexity of New Rules: While the new reduction rules are effective theoretically, their implementation complexity and impact on practical solvers are not analyzed.
  • Generalization: The authors suggest that the analytical framework, particularly the use of tunable parameters in variable weights, could be applied to other SAT variants or related NP-complete problems. This opens avenues for future research in developing more efficient algorithms for a broader range of problems.

Summary updated

BibTeX
@inproceedings{peng2023fast,
  author = {Junqiang Peng and Mingyu Xiao},
  title = {{Fast Algorithms for SAT with Bounded Occurrences of Variables}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/223},
}
Figure