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.
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.
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.)
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.
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.
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 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?
Thank you for painting such a clear picture of something I struggled to understand!
baby doll
@@kells9k ok
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
Thanks. Meanwhile, some of my actual students hunt around for different videos because they don't like my style...
@@davidtaylor2809 different strokes for different folks. thanks for the vid!
Great video! Thanks.
Any approximate time in the future you are thinking of covering Approximation Algorithms?
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.
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.
Dominating set deals with the coverage of vertices while vertex cover deals with the coverage of edges.
It’s like every vertex cover is a dominating set but not all dominating sets are vertex covers
@@Rievax17 Yes, that's the exact reason why the reduction is only one side.
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.
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?
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.
Amazing video!
AMAZING THANK YOU SO MUCH!!!!!!!!!!!!!!!!!!!!
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
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.)
If a problem is NP-Hard, does that make it automatically np-complete?
No, the problem could be so hard that it is not NP.
A problem is NP-Complete if it is NP hard & has a non-deterministic polynomial time algorithm.
what is , , between two things not in the set? and to something not in the set? are they both not different ? at 3:55
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.
Anderson Lisa Lewis Christopher Rodriguez Margaret
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
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.
you are just reading it, no proper explaination
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.
@@AlgorithmswithAttitude it is a bad video, i already referred other teachers tutorial, it is far better than yours, try to explain properly
@@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?