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

[@taha7shaikh]

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

[@camrws]

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

[@springworks0068]

Thank you this explanation was a life saver 😪🙏

[@NachooCh]

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

[@sid2364]

Thanks a ton for the explanation! One thing that doesn't make sense to me is how we "come up" with the 3SAT formula... what does this CNF formula have to do with the graph that we are given as input for a Vertex Cover problem? I'm just confused since they seem slightly disjointed?

[@josemanuelgil9618]

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.

[@mohitbhalla5864]

hey thanks for your effort hope you have wonderful life

[@terracottapie6872]

Thank you for the video :)

[@naomialidinata4099]

thank u so much!

[@samarthtandale9121]

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?

[@christophertralie9311]

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

[@ivanbliznets701]

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.

[@brendawilliams8062]

1.1 is in a 1007438183 using 32

[@nexushare8105]

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?

[@a2g108]

X1' or X1 Bar is a negation of X1

[@Someguy8231]

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

[@anshuhimanshusuthar5614]

++

[@terracottapie6872]

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

[@zacharysmith4508]

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

[@EasyTheory]

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.

[@zacharysmith4508]

@@EasyTheory That would be awesome! Especially Kolmogorov complexity as I find that to be one of the most interesting areas of CS/information theory.

[@hervediedie]

far-fetched explanation