NP-Complete Reductions: Clique, Independent Set, Vertex Cover, and Dominating Set

[@ropopal1094]

man you are smart and funny and explain well! thank you so much for your free videos and your great attitude. i declare you as my official teacher

[@davidtaylor2809]

Thanks. Meanwhile, some of my actual students hunt around for different videos because they don't like my style...

[@katchie2888]

@@davidtaylor2809 different strokes for different folks. thanks for the vid!

[@furkan-sahin]

Thank you for painting such a clear picture of something I struggled to understand!

[@kells9k]

baby doll

[@mixmix862]

@@kells9k ok

[@laolun2278]

I'm not sure which part of my comprehension went wrong, but what makes vertex cover different from dominating set? They seem pretty much the same.

[@pyetwi]

Dominating set deals with the coverage of vertices while vertex cover deals with the coverage of edges.

[@Rievax17]

It’s like every vertex cover is a dominating set but not all dominating sets are vertex covers

[@klaotische5701]

@@Rievax17 Yes, that's the exact reason why the reduction is only one side.

[@extremeforlife8563]

Am I wrong in saying that the independent set is the graph compliment of clique, while the independent set is the vertex complement of vertex over?

[@AlgorithmswithAttitude]

Basically, yes, though to make it precise, the wording is a bit tricky. If a set of vertices in a graph forms a clique, that set of vertices is an independent set in the complement graph. And, if a set of vertices is a vertex cover in a graph, the complement of those vertices is an independent set in the same graph.

[@samarthtandale9121]

Can't we reduce dominating set to vertex cover in a following way: Reduction: Given a problem to find a dominating set D in a graph G = (V, E), we find a vertex cover V and return it as dominating set because every vertex cover is a dominating set. This reduction shows that dominating set

[@AlgorithmswithAttitude]

It is true that every vertex cover is a dominating set...but a graph can have a dominating set that is smaller than the smallest door takes cover. So, if we ask the question "is there a dominating set of size 1" in a triangle, the answer is yes, any vertex will do. But the smallest vertex has size 2, and knowing that there is a size 2 vertex cover doesn't help us to know the size of the smallest dominating set. This example gets much worse when you scale it: a clique with n vertices has a dominating set of size 1, but its smallest vertex cover is size n -1.

[@andersimenes1937]

Great video! Thanks.

[@cagan8]

Any approximate time in the future you are thinking of covering Approximation Algorithms?

[@AlgorithmswithAttitude]

No immediate plans, but for sure one introductory algorithm would fit nicely into the NP playlist. It is a good suggestion, I will think about it.

[@yunoletmehaveaname]

If a problem is NP-Hard, does that make it automatically np-complete?

[@AlgorithmswithAttitude]

No, the problem could be so hard that it is not NP.

[@jaimecastillo9711]

A problem is NP-Complete if it is NP hard & has a non-deterministic polynomial time algorithm.

[@mohamedgamal93]

Amazing video!

[@vidhisanghavi8048]

Why we need 3 nodes for vertex cover we could do in 2 also. 6 and 3. why 4 is there ? 6 is connected to 1,2,4,5,7 and 3 is connected to 7 and 5

[@AlgorithmswithAttitude]

A vertex cover is a set of vertices that covers every edge. The (1,4) edge is not covered by your two vertices. (Your description shows that your vertices form a dominating set.)

[@JikeWimblik]

What about partial reductions to restricted 2sats to deduce restricted 3sats that make it easy to solve the main 3sat problem. To fiddly and approach for humans but not ai.

[@caialyu2833]

AMAZING THANK YOU SO MUCH!!!!!!!!!!!!!!!!!!!!

[@rohandevaki4349]

what is , , between two things not in the set? and to something not in the set? are they both not different ? at 3:55

[@AlgorithmswithAttitude]

For the given independent set of 1, 2, 5, and 7, consider the edges of the graph. Some edges, like the edge between 3 and 4, go between two vertices not in the set. Other edges, like the edge between 1 and 6, go from between one thing in the set, and one thing not in the set. But no edge goes between two things in the set, as then it wouldn't be an independent set.

[@rohandevaki4349]

how are you telling a independent set? there is no edge between 6 and 3, isnt it also a independent set? , why didnt you include it ? at 0:38

[@AlgorithmswithAttitude]

6 and 3 are an independent set of just 2 vertices. The highlighted set of 1, 2, 5, and 7 have 4 vertices, and every two of them are independent: there is no edge from 1 to 2, or 1 to 5, or 1 to 7, or 2 to 5, or 2 to 7, or 5 to 7.

[@rohandevaki4349]

you are just reading it, no proper explaination

[@AlgorithmswithAttitude]

Your other two comments are much more constructive. They specifically point out an area which is confusing you, and I can respond to them to try to clarify what is being said or described at those points in the video. This comment is...less helpful. I have attempted to make a helpful video. Maybe it is good, maybe it is bad. This comment is about as helpful as you just writing "Hey, you should make this video, but better." It doesn't really give me a lot to go on, no specific time, nothing. I definitely do more than just read in the video. Do I sometimes read the words on the slides? Yes. I also wrote the slides. And created the animations. And wrote the script. So...take it easy.

[@rohandevaki4349]

@@AlgorithmswithAttitude it is a bad video, i already referred other teachers tutorial, it is far better than yours, try to explain properly

[@AlgorithmswithAttitude]

@@rohandevaki4349 Maybe you should post that link here too. If I find it to be helpful I will leave the link up. Again, let's keep it constructive. I don't find it particularly easy to make videos. There is some balance between trying to keep it brief, yet having all of the material in it. Also, I do understand that there are videos of lectures out there, which might present the same material but take 3 times longer to present it. There are enough of those out there that I am not trying to make another one, as there is no need. You have tried to make films before, right? Would you find comments written as yours are here to be helpful?