[MUSIC] So on the last video we solved the problem we are talking about. And that problem is trying to find the minimum set of users you need to send out announcement so that it reaches everyone. That problem is actually hard. And relates very well to the dominating set problem. What we're going to do in this video is try and get a better feel for what we can do when we recognize that problem is hard, just like we did back in course three with the travelling salesperson problem. So, at the end of this video you should be able to recognize available steps to help you solve your problem whether it be this problem or other problems. And then implement at least one possible approximation algorithm to this specific problem. All right, so the end again of the last video, we realized that finding a minimum dominating set is a known NP-Hard problem. So, this means we're not going to be able to come up with a perfect solution. What's our next step? Well Researching possible options is really your next step so the places you may want to go are text books or websites and here you'll be looking for approaches that been taken in the past to solve minimum dominating set. The other thing that you can look at are research papers, and the best website to find research papers in my opinion is scholar.google.com. And if you look on scholar.google.com you'll almost always find research papers on computer science problems and I bet you'll find some really good resources associated with minimum dominating set. So your first step really is to find out what have other people done, and then try to get a good feel for what you're going to do to solve your problem. And what I want to do is walk through now one potential approach you could take. And this is a fairly obvious greedy algorithm solution to this problem. So what we're going to do is we're going to mark all vertices. And what I'll do is I'll walk through all these steps of the algorithm carefully, but let me just give you a first idea. Right at the beginning we're going to say that all of the vertices are uncovered. And we're going to create a dominant set and we're just going to make it empty. And then we're going to essentially go through, as long as we haven't covered all the vertices, we're going to find the vertex that's going to cover the most uncovered vertices, and we're going to add it to our set. So, let's see what this looks like. So I've got this graph here in the upper left, and in the first iteration of the loop, I'm going to start looking for the vertex which, if added to the dominant set, is going to cover the most vertices. So if you look around you're going to find that it's actually, this vertex is going to cover the most. It's going to cover itself, along with seven other vertices so that's a pretty big covering, that's the one that's going to cover the most you select that to be part of your dominate set, you add into the dominate set and then you mark everything that's adjacent to as covered, so we mark all those as covered. Now we're not done because there are still uncovered vertices. So next Iteration loop, we're going to find what vertex is going to cover the most uncovered vertices. And this case, it's going to be this one because this is going to cover five vertices. We're going to mark that as covered or we're going to add that to the dominant set and we're going to mark all of his neighbors covered. Itself and all his neighbors is covered. At this point we actually cover everything in this graph. So for this graph, our greedy algorithm has actually found the minimum dominant set. Every time it's going to find a dominant set, this time it's actually found the minimum dominant set. But will you always find the minimum dominant set. So what I want you to do is the best way to learn these algorithms is by doing samples on your own. So if you can, pause the video, try and come up with a counter example before you keep watching. I'll see you back in just a moment. All right, I hope you were able to find a counter example on your own. One where this greedy algorithm will fail to find you the minimum dominant set. But here's an example of one that will fail that I found. And again, there's plenty of examples that you can find. But let's just walk through why on this graph it actually fails as using greedy algorithm. So, greedy algorithm is going to select the vertex. It's going to cover the most vertices and in doing so it's going to select to that center vertex. That's average select in a vertex, it's going to mark all the ones adjacent to it as covered. And now it's got these two other ones that haven't been covered yet. So in a net second iteration of loop it's going to select one of these two kind of at random. It will pick one of them and then it'll mark its neighbors as covered. It has no other neighbors to mark. And in the third iteration loop, it's going to find that the remain vertex, include that in the dominant set, and we'll be done. So this finds me the dominant set, but not a minimum dominant set. In fact, if you look at this graph you can tell that it's really just these two nodes that we need to have a minimum dominant set. So, greedy algorithms can be effective, but again remember that they have limitations. They won't always find you the perfect solution. So there's a couple questions I want you to look into about this problem. So first is, I've given you a greedy algorithm, just figure out what the runtime of it is. The second piece is a larger question and that is, are there better algorithms to try to solve this problem? And better can mean a couple of different things, right? Better could be that it's more apt to find the minimum dominant set, it's more apt to find smaller dominating sets, or that it just runs more quickly. And this is where your research is going to come in. So you're going to be reading the textbooks or websites about this problem or research papers about this problem. In through that reading you're going to get better feel for the algorithms that are out there and which one you want to employ in your solution. I do want to give you this one quick heads up that if you're really comfortable with theory of computation and complexity theory and I mean really comfortable with it. You could look into fixed-parameter tractability. It actually applies fairly well to this problem, but again, it's an extremely advanced topic. Don't dive into it unless you really are comfortable with those areas. All right, now that we have a better feel for this problem, and recognize that this problem is actually hard, and that we're probably going to have to use some kind of approximation algorithm to solve this problem, you can continue exploring this problem as your focus for your project. But I also want you to explore other problems and what we're going to do next is actually show you another kind of problem that you might want to solve and we'll dive into that in the next video.
