Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable
(2004)
Journal Article
Szeider, S. (2004). Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable. Journal of Computer and System Sciences, 69(4), 656-674. https://doi.org/10.1016/j.jcss.2004.04.009
Recognition of minimal unsatisfiable CNF formulas (unsatisfiable CNF formulas which become satisfiable if any clause is removed) is a classical DP-complete problem. It was shown recently that minimal unsatisfiable formulas with n variables and n+k cl... Read More about Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable.