Partial Minimum Satisfiability: Fine-Grained Analysis

Abstract

There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or Max-SAT and run a SAT or a Max-SAT solver. This method is very efficient since SAT/Max-SAT solvers are extremely well-studied, as well as the complexity of these problems. At IJCAI-2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Min-SAT and using MinSatz is in some cases more efficient than reductions to SAT or Max-SAT. Since then many results connected to the Partial Min-SAT problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Min-SAT has not been studied up until now. Our goal is to fix the issue and show a O*((2 - ε)^m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.