1
$\begingroup$

a 2 sat instance which is unsatisfiable and an integer k are given, decision problem is that: is it possible to delete 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.

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
1
$\begingroup$

You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses $$ x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y, $$ where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.

Improve this answer
$\endgroup$
2
  • $\begingroup$ but in this form, won't all clauses be removed????, unless just especial literals for example those which are negative of variables corresponded to the edges in the independent set be removed!! then the rest cnf will be satisfiable?? Can U tell me I concluded correctly or not $\endgroup$
    – NedaHn
    Commented Oct 23, 2017 at 14:47
  • $\begingroup$ I think you should be able to complete the rest of the proof on your own without my intervention. $\endgroup$
    – Yuval Filmus
    Commented Oct 23, 2017 at 14:48
0
$\begingroup$

I think the easiest approach is to model this problem as a sat problem.

Let K(x) mean that x is kept. Let C(K) be the number of literal for which K is true. Then any clause (a V b) from your original formula can be modeled as (a V b V K(a) V K(b)). Apply a reduction from 4-sat to 3-sat. You now have a problem that is a max 3-sat problem where you need to maximize C(K).

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks for your answer but u mean at first I transfer 2 sat to 4 sat then from that have a reduction from 4 sat to 3 sat?? as far as I know when we want to show a problem is np-hard we should use another known problem and try to transfer an instance of it in polynomial time to an instance of unknown problem and think that unknown problem can be solved then from the result of it we conclude the result of known problem but I can't see these steps in your inference!?!!? $\endgroup$
    – NedaHn
    Commented Oct 23, 2017 at 18:17
  • 1
    $\begingroup$ We want a reduction showing that the problem is NP-hard. We are not interested in reductions going in the other direction. $\endgroup$
    – Yuval Filmus
    Commented Oct 23, 2017 at 19:04
-1
$\begingroup$

the problem which should be used is Odd Cycle Transversal

Improve this answer
$\endgroup$
1
  • $\begingroup$ If this is the answer you were looking for, could you elaborate? If nothing more could be done, accept your own answer afterwards. $\endgroup$
    – Evil
    Commented Oct 24, 2017 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.