Why does the reduction from 3SAT to IS work?

I was reading about the reduction from 3SAT (input: formula) to Independent set (input (graph, k)) in order to prove that the latter is in NP-Complete. The reduction i've seen follow the next steps:

• For each clause at the input, create a node for every variable it contains in case it doesn't exist yet. Then, create a $K_3$ with these nodes.

• Create an edge between a node and its negation.

An example i found:

While proving this reduction is correct, they say:


$\Rightarrow$) If the formula is satisfiable, there is at least one true literal in each clause. Let S be a set of one such true literal from each
clause. |S| = k and no two nodes in S are connected by an edge.

I don't understand why this works. I mean, $k$ is fixed at this point (from the input) so if $k=3$ i can take $S=\{x_1, x_3, x_4\}$. If $k=2$ i can take $S=\{x_2, x_4\}$ but if $k=1$ i can't.

Could you explain me why this works or if i am not understanding anything correctly? Thanks.

The $\Rightarrow$ implication means that you need to prove that if the given $3SAT$ formula is satisfiable then there is a maximum IS.

So assume that the formula is satisfiable.

Since the formula is satisfiable each clause has at least one literal (it may be $x_1$ or $\overline{x}_1$ for instance). Now I claim that according to the structure of the graph the maximum IS must have $k$ nodes where $k$ is the number of clauses.

Why?

Because each clause corresponds to a single triangle $K_3$, and hence you can choose only one node from each triangle, where you have exactly $k$ triangles (any two nodes in the $K_3$ are not independent - they are connected by an edge).

But which node do we choose from each gadget/triangle?

You choose those literals which are true. These literals form independent set. Indeed, if two true literals belong to different triangles then they are not connected by an edge since only $x_i$ and $\overline{x}_i$ may be connected by an edge. But $x_i$ and $\overline{x}_i$ cannot be true at the same time (remember that our IS $S$ contains only true literals).

So we have exactly $k$ nodes/true literals which indeed forms a maximum IS. Therefore if the formula is satisfiable then the graph has a maximum IS.

You also need to prove the opposite, namely, if the graph has a maximum IS then the formula is satisfiable. I think you could prove it yourself.

StackExchange Computer Science Q#79828, answer score: 4