NP Completeness 9 - Set Cover Problem and Outline of Proof Technique

In this video we introduce the Set Cover problem and prove that it is NP Complete by reducing the Vertex Cover problem to it. Once we finish this proof we discuss a general outline of the proof technique that we have used thus far in this unit.

[@Derek123488]

what if an element exist in more than 2 sets, such as e1 exists in S1, S2 and S3, than how can we construct the corresponding graph?

[@learningalien9586]

explain in wonderfull way. Thank you professor painter

[@raja_putih]

Super easy to follow and just what I needed for my algorithm course, thanks so much!

[@juanse_velasquez9831]

Just what I needed, thank you for the video!

[@marco.nascimento]

Great explanation! Thanks

[@soustab10]

Thanks for the playlist.

[@asherb5134]

How do I build the graph with an edge that is only in one Subset ? since according to your example each vertex is connection to another vertex if they have matching edges that correspond to the original subset items .. ?

[@rohandevaki4349]

great explaination

[@Snowmanver2]

Thanks, very useful!

[@wearedoingsomething]

Thank you very much!

[@utsavseth7116]

You are a legend sir

[@carson9903]

Thanks!

[@1UniverseGames]

Can you explain for 4-Approximation Vertex Cover Problem?

[@nexesdz3907]

thanks men

[@chaosjoerg9811]

All I wanted to know was how to show that Set Cover is in NP. :(

[@lukewalsh9083]

thats what he showed in the video :)

[@RaviolistRavioli]

I love you

[@PR-vz9hx]

I love you too

[@PR-vz9hx]

@Ravioli Ravioli 💅when was this

[@nachomacho7027]

Subscribed bro

[@sahil_tayade]

Can you do machine learning next?