Abstract
This paper introduces the first exact inference-based algorithm for MinSAT, the problem of finding a truth assignment that falsifies the maximum number of clauses in a logical formula. By adapting resolution rules originally designed for MaxSAT and employing a novel saturation strategy, the authors provide a complete theoretical framework. A key contribution is the "Pure Literal Rule" for MinSAT, which significantly enhances solver efficiency by reducing both execution time and search space.
Introduction
In Boolean Satisfiability (SAT), the traditional goal is to find an assignment that satisfies a formula. MaxSAT extends this by seeking to minimize the number of falsified clauses. Conversely, MinSAT focuses on maximizing the number of falsified clauses. While they appear symmetric, MinSAT and MaxSAT are computationally distinct. MinSAT is particularly relevant for problems like combinatorial auctions and finding the Maximum Clique in a graph, where it often offers more efficient encodings than MaxSAT. Despite its utility, MinSAT research has historically relied on search-based techniques, lacking the formal inference schemes developed for MaxSAT. This work bridges that gap.
Methodology
The proposed approach leverages the MaxSAT resolution rule, which preserves the total count of falsified clauses by replacing original clauses with a specific set of conclusions. The authors introduce three primary technical innovations:
- Saturation Strategy: Unlike MaxSAT, which seeks to minimize empty clauses (contradictions), the MinSAT scheme transforms the formula to derive the maximum possible number of empty clauses.
- MinSAT Pure Literal Rule (PLR): In standard SAT, a pure literal (a variable appearing only in one polarity) can be set to satisfy its clauses. The authors prove that in MinSAT, clauses containing a pure literal can be deleted without affecting the maximum falsification count, providing a powerful simplification step.
- Optimal Assignment Backtracking: The algorithm includes a mechanism to reconstruct the specific variable assignments required to achieve the maximum falsification count.
Results and Discussion
The effectiveness of the inference scheme and the Pure Literal Rule was evaluated using random Min-2SAT instances with varying clause-to-variable ratios ($r$).
Efficiency and Performance
The introduction of the Pure Literal Rule led to substantial practical improvements. Empirical tests demonstrated a significant reduction in execution time across all tested ratios, as shown in the figure below.
Proof Tree Reduction
Beyond raw speed, the PLR drastically reduced the complexity of the problem by shrinking the proof tree size. This reduction in the number of nodes the solver must explore highlights the rule's ability to simplify the logical structure of the formula before or during the inference process.
The results reinforce the idea that MinSAT and MaxSAT are complementary. Problems that are computationally expensive for one are often more tractable for the other due to differences in constraint encoding.
Conclusion
This paper establishes the first formal proof that an inference-based algorithm can exactly solve MinSAT. While inference can sometimes introduce overhead compared to pure search, the proposed rules—especially the Pure Literal Rule—provide a robust foundation for future hybrid solvers. Future work will explore extending these rules to finite-domain variables and developing dynamic solvers that select the optimal inference scheme based on problem structure.
Summary updated