In the beginning the problem had 4 vertices in the independent set {v1,v6,v3,v8}. But the reduction using the constructed graph gave a solution with maximum of 3 nodes. How does this work?
As it is your reduction is wrong, you need to specify that if a literal appears in several clauses you have to add one vertex for each copy. Then you have to add an edge from each copy of each literal to all copies of its negation. In your example no literal appears twice, hence the problem is easy to miss. If you don't do that then your proof does not hold because many clauses may be satisfied because of the same literal, thus your satisfying assignment may correspond to a set of less than m vertices
Finding these videos 2 days before final, thank you very much good sir.
Amazing explanation. I was really struggling with this because I am self-studying and had no one to help me. Thank you!
Great explain and guidance ❤
It’s such a clear explanation , thank you so much !
Best explanation
Thank you!
great explaination
thank you for the study video! Pro Painter!
nice work!
Thank you~! Could you share the example answer???
In the beginning the problem had 4 vertices in the independent set {v1,v6,v3,v8}. But the reduction using the constructed graph gave a solution with maximum of 3 nodes. How does this work?
Because we reduce to 3Sat so 3 variables
As it is your reduction is wrong, you need to specify that if a literal appears in several clauses you have to add one vertex for each copy.
Then you have to add an edge from each copy of each literal to all copies of its negation. In your example no literal appears twice, hence the problem is easy to miss.
If you don't do that then your proof does not hold because many clauses may be satisfied because of the same literal, thus your satisfying assignment may correspond to a set of less than m vertices
Your suggestion would not allow all possible solutions for (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ !x2 ∨ !x3) because you'd block x1.
I came here looking for an explanation for that as well. You're absolutely correct, this proof is not correct.
nice
Does this has at most 4 vertex
Prof share pdf. Dont be greedy. please share😅
8:40
LAME :p
Thank you!