Vertex Cover is NP-Complete + Example

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.

▶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.

[tahashaikh]

Thank you so much man! This is the only good explanation out there

[path_selector]

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

[samarthtandale]

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?

[springworks]

Thank you this explanation was a life saver 😪🙏

[ignaciomartinchiaravalle]

Thank you so much!!!! This was really helpful!!!

[josemanuelgil]

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.

[mohitbhalla]

hey thanks for your effort hope you have wonderful life

[ivanbliznets]

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.

[nexushare]

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?

[Someguy]

Vertices allowed = 2c + l is unclear to me.
Why is this the limit?

[zacharysmith]

Semi-related to this, do you plan on doing anything in computability theory too?