Almost 2-SAT is Fixed-Parameter Tractable

Igor Razgon, Barry O'Sullivan

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…