Almost 2-SAT is fixed-parameter tractable |
| |
Authors: | Igor Razgon Barry O'Sullivan |
| |
Affiliation: | Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Ireland |
| |
Abstract: | We consider the following problem. Given a 2-cnf formula, is it possible to remove at most k clauses so that the resulting 2-cnf formula is satisfiable? This problem is known to different research communities in theoretical computer science under the names Almost 2-SAT, All-but-k 2-SAT, 2-cnf deletion, and 2-SAT deletion. The status of the fixed-parameter tractability of this problem is a long-standing open question in the area of parameterized complexity. We resolve this open question by proposing an algorithm that solves this problem in O(k15×k×m3) time showing that this problem is fixed-parameter tractable. |
| |
Keywords: | Fixed-parameter algorithms Satisfiability problems Separation problems |
本文献已被 ScienceDirect 等数据库收录! |