TL;DR
This paper investigates the worst-case complexity of the Partial Minimum Satisfiability (PARTIAL MIN-SAT) problem, a variant of SAT used for reducing NP-hard problems. The authors establish a strong lower bound, showing that PARTIAL MIN-SAT is likely as hard as SAT itself under the Strong Exponential Time Hypothesis (SETH), and present several new algorithms for specific cases of the problem.
What Problem Does This Paper Address?
Many computationally hard problems are tackled in practice by reducing them to SAT (Satisfiability) or MAX-SAT solvers. This approach leverages the extensive research and highly optimized solvers available for these well-studied problems. At AAAI 2011, a new target problem, PARTIAL MIN-SAT, was proposed as an alternative reduction target. PARTIAL MIN-SAT involves satisfying all "hard" clauses in a formula while minimizing the number of unsatisfied "soft" clauses. While practical solvers for PARTIAL MIN-SAT exist and the problem has been linked to various classical NP-hard problems, its fundamental worst-case complexity remained largely unexplored. This paper aims to fill that gap by analyzing the theoretical limits and developing new algorithmic approaches for PARTIAL MIN-SAT.
Methods
The paper employs a combination of theoretical analysis and algorithmic development.
- Lower Bounds: The authors establish lower bounds on the running time of algorithms for PARTIAL MIN-SAT. This is primarily achieved through reductions from known hard problems, particularly a variant of the HITTING SET problem. The core of this analysis relies on the Strong Exponential Time Hypothesis (SETH), a widely accepted conjecture about the limits of SAT solving. They also introduce a connection to the MULTICOLORED MINIMUM UNION problem, which helps in proving these lower bounds.
- Algorithmic Development: The paper presents several new algorithms for PARTIAL MIN-SAT, focusing on specific cases and parameterizations. These include algorithms that exploit properties like clause length (e.g., hard clauses of length at most 2), the number of non-trivial variables (variables appearing both positively and negatively), and the number of soft clauses. Techniques used include branching rules, reduction rules, and leveraging existing algorithms for related problems like VERTEX COVER and MAXIMUM CUT.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic design rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- SETH Implication: The most significant finding is that PARTIAL MIN-SAT is likely as hard as SAT itself in terms of the number of clauses and variables, under the SETH. This means that significantly faster-than-exponential algorithms are unlikely.
- Divergence from SAT/MAX-SAT: Unlike SAT, where pure literal elimination is a standard optimization, this rule is not directly applicable to PARTIAL MIN-SAT because it could undesirably satisfy soft clauses. Similarly, standard resolution rules are also restricted.
- Connection to Set Problems: The paper highlights a strong connection between PARTIAL MIN-SAT and set-theoretic problems like MULTICOLORED MINIMUM UNION and HITTING SET. This connection is crucial for both proving lower bounds and developing algorithms.
- Parameterized Complexity: The authors explore parameterized complexity, showing that PARTIAL MIN-SAT is W[1]-hard with respect to the number of clauses to satisfy (h+k), suggesting that algorithms parameterized by this value are unlikely to be FPT unless W[1] = FPT.
- Algorithmic Progress in Special Cases: Despite the general hardness, the paper demonstrates that specific, restricted versions of PARTIAL MIN-SAT can be solved much more efficiently than the general case, often by leveraging existing algorithms for problems like VERTEX COVER.
Key Results
- Lower Bound: Unless SETH fails, there is no algorithm for PARTIAL MIN-SAT with running time $O^*((2-\epsilon)^m)$ or $O^*((2-\epsilon)^n)$ for any $\epsilon > 0$, where $m$ is the number of clauses and $n$ is the number of variables.
- Parameterized Hardness: PARTIAL MIN-SAT is W[1]-hard with respect to the parameter $h+k$ (number of hard and soft clauses).
- Algorithmic Results:
- PARTIAL MIN-SAT with hard clauses of length at most 2 can be solved in $O^*(1.1996^m)$ time (by reducing to VERTEX COVER).
- PARTIAL MIN-SAT for formulas in 2-CNF has an $O^*(2^{\omega n/3})$ running time algorithm, where $\omega$ is the matrix multiplication exponent.
- An algorithm with running time $O^*(1.6181^h \cdot (2-\epsilon)^n)$ exists for $q \ge 3$, where $q$ is the maximum length of hard clauses.
- A general algorithm with running time $O^*(1.755^n)$ is presented.
Limitations and Future Work
- SETH Dependence: The primary lower bound is contingent on the SETH. If SETH were false, faster algorithms might exist.
- General Case Complexity: While significant progress is made, the general case of PARTIAL MIN-SAT still exhibits exponential complexity, albeit with improved constants in some algorithms.
- Future Work: The paper suggests exploring further algorithmic improvements for specific cases and parameterizations. The authors also hint at the possibility of obtaining algorithms faster than $2^m$ for certain parameter combinations, particularly when $n$ and $m$ are comparable. The connection to set problems and the development of new reduction techniques are likely avenues for future research.
Summary updated