سؤال

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.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top