Vertex Cover is NP-Complete + Example
Вставка
- Опубліковано 12 кві 2021
- Here we give a polynomial-time reduction from 3SAT to Vertex Cover, and show that VC is in NP, thereby showing that it is NP-complete.
If you like this content, please consider subscribing to my channel: / @easytheory
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
Thank you so much!!!! This was really helpful!!!
Thank you this explanation was a life saver 😪🙏
thank u so much!
Thank you for the video :)
i’m in graph theory and theory of computation this semester so ur kinda pushing the two together in this video lol, although we don’t really talk about NP complete
hey thanks for your effort hope you have wonderful life
Im in a CS theory course, and find this topic non intuitive, I mean its not obvious how to come up with this gadget, basically you have to learn it by heart, and after that you can refer to this kind of reduction in other cases.
Can you, please, tell me were the proof is written? I want to cite it. I need exactly this proof, previously I saw different reductions and they do not work for my needs.
Sir, if the vertex cover (optimization) problem is np complete, then there must exist an algorithm that can verify that the given solution is valid and minimum in polynomizal time. is it possible? I'm rally confused because some sources say that it is np complete and others say that it is np hard, which one is it?
So actually NP complete means *both* NP hard (any problem in NP can be reduced to it in polynomial time) *and* in NP (meaning it can be verified in polynomial time, as you say). So you are right to say it's NP hard, but a more precise statement is that it's NP complete, since it's also in NP
Semi-related to this, do you plan on doing anything in computability theory too?
I didn't see this until just now! Yes, eventually. I want to do some Kolmogorov complexity, as well as some decidability of theories and such.
@@EasyTheory That would be awesome! Especially Kolmogorov complexity as I find that to be one of the most interesting areas of CS/information theory.
hmmmm,,,,, so if X1 represent a vertex, then what does X1 bar represent? is it a negration of a vertex? does it make sense? if X1 BAR is a sepereate vertex, then why do we select that vertex as negation of x1? and in this case , is it safe to assume that a vertex has no more than three edges?
X1' or X1 Bar is a negation of X1
Vertices allowed = 2c + l is unclear to me.
Why is this the limit?
++
Because this value of the limit allows us to make a correct reduction from the 3SAT problem. If we set k lower than 2c+l, then for not every satisfiable formula the corresponding graph would have a vertex cover of size
far-fetched explanation