Partial Minimum Satisfiability: Fine-Grained Analysis
Journal of Artificial Intelligence Research · 19.04.2026 · 85
DOI: 10.1613/jair.1.19378 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Artificial Intelligence Research, online erschienen am 19.04.2026. Verfasst von Ivan Bliznets und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Bliznets, I., Sagunov, D., & Simonov, K. (2026). Partial Minimum Satisfiability: Fine-Grained Analysis. Journal of Artificial Intelligence Research, 85. https://doi.org/10.1613/jair.1.19378
Vancouver
Bliznets I, Sagunov D, Simonov K. Partial Minimum Satisfiability: Fine-Grained Analysis. Journal of Artificial Intelligence Research. 2026;85. doi:10.1613/jair.1.19378
BibTeX
@article{Bliznets2026,
author = {Bliznets, Ivan and Sagunov, Danil and Simonov, Kirill},
title = {Partial Minimum Satisfiability: Fine-Grained Analysis},
journal = {Journal of Artificial Intelligence Research},
year = {2026},
volume = {85},
doi = {10.1613/jair.1.19378}
}
EUVIMED