Skip to main content
2 of 4
edited tags
NedaHn
  • 135
  • 1
  • 8

NP-hardness of minimum variable removal in 2-sat

a 2-sat instance which is unsatisfiable and an integer k is given, decision problem is that: is it possible to remove k variables, also remove clauses contain them, in order to satisfy the 2-sat instance?? and optimization problem is that: find the minimum number of variables to remove to make the 2-sat instance satisfiable. I want to use reduction to show this problem is np-hard but I don't know which np-hard problem should be used. I appreciate if anyone could help me by the reduction or introduce me a reference (I searched but maybe I don't know the name of problem exactly)

please notice that this problem is different from maximum 2-sat, in this problem each clause can even contain one literal and we reduce 3-sat to show it is np-hard.

NedaHn
  • 135
  • 1
  • 8