3
$\begingroup$

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:

  1. 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.
  2. Create an edge between a node and its negation.

An example i found:

enter image description here

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.

$\endgroup$
  • $\begingroup$ You are overthinking it. If you are reducing 3SAT to IS, all you have to do is to produce an instance of the latter given an instance of the first. $k$ isn't fixed by anything, you get to choose it. $\endgroup$ – quicksort Aug 7 '17 at 17:54
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! Just one question: What happens if the formula is satisfiable but just if two different clauses have the same literal as true? e.g, if the formula is $(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee x_3)$ then it's satisfiable because if $x_1$ is true then the formula is it too. Yet, if we take another literal then that would not be an IS, would it? $\endgroup$ – jscherman Aug 7 '17 at 19:22
  • 1
    $\begingroup$ First note that both clauses are identical. The corresponding graph would consist of a single $K_3$ and hence any single true literal node would be a maximum IS. For instance $S=\{x_1\}$. $\endgroup$ – fade2black Aug 7 '17 at 19:37
  • 2
    $\begingroup$ Good point! I understand your concern. You mean what about $(x_1 \lor \overline{x}_2 \lor x_3) \land (x_1 \lor x_2\lor \overline{x}_3 )$. In this case we would have $\{x_1, x_1\}$ which is one element set in the set theoretic terms, but two vertices. I think we could fix it by labeling vertices as $x_{ij}$ corresponding to the literal $x_i$ of the clause $j$. $\endgroup$ – fade2black Aug 7 '17 at 20:12
  • 1
    $\begingroup$ The main idea is that if the formula is satisfiable then there are at least $k$ true literals. But we can select only one literal from each triangle since two vertices are connected by an edge, so we have exactly $k$ independent vertices (true literals). $\endgroup$ – fade2black Aug 7 '17 at 20:19
  • 1
    $\begingroup$ Exactly! Duplicating nodes for each clause seems to be enough. Thanks a lot! $\endgroup$ – jscherman Aug 7 '17 at 21:36

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.