algorithmgraphnpsatindependent-set

How can 3-SAT be reduced to Independent set?

I was reading about NP hardness from here (pages 8, 9) and in the notes the author reduces a problem in 3-SAT form to a graph that can be used to solve the maximum independent set problem.

In the example, the author converts the following 3-SAT problem into a graph. The 3-SAT problem is:

(a ∨ b ∨ c) ∧ (b ∨ ~c ∨ ~d) ∧ (~a ∨ c ∨ d) ∧ (a ∨ ~b ∨ ~d)

The equivalent graph generated is:

graph

The author states that two nodes are connected by an edge if:

  1. They correspond to literals in the same clause
  2. They correspond to a variable and its inverse.

I am having trouble understanding how the author came up with these rules.

Solution

  • I think what can clear the problem is reduction concept. Suppose you are familiar with a problem say X(i.e 3-SAT)[what it means familiar? You know how much is hard to solve X]. Also you are currently working to analysis another new problem say Y(i.e independent set)...

    How can the knowledge of you about X help you to come up with Y? If you can find a relation(i.e reduction) between them, then you can use the knowledge about X to Y. Something like "Y is harder than X" or "Y is as hard as X". So what that solution wants to do is finding a relation between two problems.

    In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

    Two rules you noted here is all of that(i.e the relation).

    1. You cannot select two vertices of an edge simultaneously. Also you cannot set a variable and its negation TRUE simultaneously.
    2. You must have a TRUE variable at a clause. Also to maximize the number of selected vertices you must select one node form each clauses.

    This shows where these rules comes from.

    PS: What here noted is not precise as a proof to solve the 3-SAT to Independent Set problem. This explanation was just for you to get more insight about what procedure the proofs want to do. The proof left to academic notes.

    One another important thing in the reduction is its own time. On the other hand the reduction time(i.e time takes to convert a X instance to Y instance) must be less than the X problem time(o.w it dominates the X solution time).

    Also There is some notation to show that X < Y with an other time order as index of <. Moreover, if you show that X < Y and Y < X. This means that these problems have equal hardness.

    At the last point note that what quoted note said about reduction ...a reduction is an algorithm....