1
$\begingroup$

In order to show that a problem is NP hard one must provide a reduction from a known NP hard problem to this problem. My question is how to reduce 3SAT to INDEPENDENT-SET?

3SAT is a satisfiable 3 literals in a clause Boolean conjunctive normal formula. INDEPENDENT-SET is a set of vertices in a graph, no two of which are adjacent. I do know how to reduce 3SAT to a Clique, would that help?

$\endgroup$
  • 1
    $\begingroup$ Try to reduce the maximum clique problem to the independent set problem. Hint: look at the what happens to a clique in the complement of the graph. $\endgroup$ – Discrete lizard Jan 8 '18 at 14:04
  • $\begingroup$ Thank you, in order to turn a graph into it's complement(?), it would take more than a polynomial time. Assuming we agree a co-graph is where there is an edge there isn't one and vice versa. And I forgot to mention that I need the reduction to be in polynomial time. $\endgroup$ – Anwar Saiah Jan 9 '18 at 0:03
  • 1
    $\begingroup$ "It would take more than polynomial time" I doubt that. Why do you think that? $\endgroup$ – Discrete lizard Jan 9 '18 at 7:29
1
$\begingroup$

The simplest is to reduce Clique to Independent Set using the complement graph, as discussed in the comments.

Alternatively, you can construct a graph to directly reduce 3SAT to Independent Set using "gadgets". One possible start is to do the following: for each clause, construct one node for each of the three variables in the clause. Now, we want to place edges such that:

  • No two variables in the same clause can be members of the same independent set.
  • No two variables which are the negations of each other can be members of the same independent set.

If you can accomplish this, then for a boolean formula with $m$ clauses, there is an independent set of size $m$ in your constructed graph if and only if the boolean formula is satisfiable, thus giving the desired reduction.

$\endgroup$
0
$\begingroup$

Reduction from 3SAT to Independent-Set: 1. Turn each clause of literals from formula to a group of vertices where each vertex has the name of it's corresponding literal and all vertices are connected with each other, giving triangles or pairs or single vertices. 2.Now connect each two vertices in the new created graph that represent a literal and it's complement. 3. The new graph will have independent-set of size m, when m is the number of clauses from the original CNF formatted formula, if and only if the original formula is satisfiable. Running time: o(n^2) --> polynomial

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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