In this video and the next we'll develop an exact algorithm for solving what's called the vertex cover problem. This is a well know NP-Complete problem as such we certainly don't expect our exact algorithm to run in polynomial time on general instances. But the algorithm does showcase two of the algorithmic strategies that we discussed for dealing with NP-Complete problems. First of all, we can interpret this algorithm as on general instances. While it's true running in exponential time, never the less, improving markedly over the more obvious naive brute force search. This illustrates the point that for many NP-Complete problems there's a lot of room for algorithmic ingenuity even though you're not going to come up with a polynomial time solution. A second interpretation of the algorithm we're going to develop is that it's polynomial time for special classes of instances. In particular instances that have an unusually good optimal solution. So let me introduce you to the vertex cover problem. The input is simply an undirected graph. The goal is to identify the smallest size, that is the minimum cardinality of a vertex cover of the graph. What is a vertex cover? We call a subset of the vertices is a vertex cover if for every edge at least one possibly both of the edges end points lie in the set s. There is of course always a feasible solution, you could always choose every single vertex, that's certainly going to be a vertex cover. But the hard question is how do you make sure you get one endpoint from each edge in the most parsimonious way. So what might this problem represent well perhaps your assembling a team of some sorts or maybe a team of programmers maybe of lawyers maybe of football players. Who knows but think of the vertices as being potential people that you could recruit onto your team and think of an edge as representing a potential task that your team might have to complete and the two vertices in the edge represent. The two people who are capable of accomplishing that task. So then what a vertex cover is it says hire enough people so that every single task you can accomplish. You have one of the two people in your team that's capable of accomplishing that task. So you could have course imagine various generalization to this problem. You could have a weights for each vertex for example indicating the salary that you have to pay that person. You could also imagine that instead of edges you have what you call hyper edges if more than two people are capable of accomplishing a given task. But the unweighted graph vertex cover problem will be interesting enough for our purposes here. Many people are of the opinion that this is a poorly monikered problem. Many people think it should be called the edge cover problem, not the vertex cover problem. Because you are choosing vertices to, in some sense, cover the edges. But picking at least one of their end points. But this is the conventional name for this problem. In the vertex cover problem, You're choosing a set of vertices and edges provide the constraints. Let's now jump to a quiz to make sure the problem definition is clear. So the correct answer is A. Let's consider each of the two graphs In turn. Let's start with a star graph on n vertices. So this has one vertex in the centre and n-1 spokes. The claim is it has a vertex cover of size one, obviously the minimum possible. That vertex cover comprises just that center vertex. Why is it a vertex cover? Well every single edge is a spoke and one of its endpoints is the center vertex. So you just pick the one vertex and you hit all of the n-1 edges of the graph. So how about a clique on n vertices? So a graph in which every single one of the n choose two edges is present. Why is n minus one vertices necessary and sufficient for a vertex cover? To see why it's necessary, consider any set that excludes at least two vertices of the graph. Because it's a clique there's an edge between those two excluded vertices and that's an edge such that neither of it's end points is in the set. So that's why the set is not a vertex cover. If it has the most N-2 vertices in it. On the other hand if it only excludes one vertex then there cannot be an edge with both of it's end points missing from the set. because there's only one vertex in total missing for the set. So that's why any subset of n- 1 vertices will be a vertex cover of a clique, n- 1 is sufficient. Figuring out the minimum size of a vertex cover in these two special graphs probably didn't seem that hard, and it's not. But when you're talking about general graphs that you don't know anything about. Computing the minimum vertex cover is in fact an NP complete problem. There is no polynomials in the algorithm that solves it unless P = NP. So that's definitely a bummer. So let's review our strategies for dealing with NP complete problems that we discussed in an earlier video. So the first strategy is to identify computationally tractable special cases of your NP-Complete Problem. Now in the best case scenario, the version of the problem that you have to solve in your own application lies squarely inside one of these computationally tractable special cases. Then you're good to go. More commonly the instances that arise in your application wont necessarily be in one of the computationally attractable cases, but it can still be useful to have sub routines ready for various special cases. One thing we discussed in the past is the potential of a hybrid approach. Perhaps you do a little bit of boot for a search and for most of the branches of your boot for search. The residual problem falls into a computationally tractable special case. And it turns out there's some quite interesting computationally tractable special cases of the vertex cover problem. And the story here is very much in parallel with discussions we've had in the past about the independent set problem. So in particular you can solve vertex cover and polynomial time on path graphs just like we did with independent sets. Actually, more generally in trees or even more generally in what's called graphs of bounded tree-width. But at least for trees, that's an application of dynamic programming which you're now in a good position to solve yourself. So I encourage you to think that through as an exercise. Why can you solve the vertex cover problem in polynomial time in trees? So another quite interesting class of graphs where you can solve the vertex cover problem in polynomial time is the class of bipartite graphs. One way to think about a bipartite graph, it's a graph that has no odd cycle. So then obviously trees are a special case. An equivalent definition is that you can partition the vertex set into two groups, a and b, so that every single edge has exactly one end point in each of a and b. That is, bipartite graphs can also be thought of as the graphs for which there's a cut that slices every single edge of the graph. It's far from obvious how to solve the vertex cover problem efficiently with bipartite graphs. But it can be done. It's an application of what's called the maximum flow problem. That's a graph problem which lies just beyond the techniques that we're covering in this class. So what I'm going to cover in the next video is using a different algorithm yet in another computationally tractable special case of vertex cover specifically when you're interested in the case that the vertex cover is small. And what I mean here by small is logarithmic in the number of vertices or less. The second strategy for dealing with NP-Complete problems is to relax the requirement of correctness and to focus on heuristics. Algorithms that are fast would need not produce an optimal solution. So there are some pretty good heuristics available for the vertex cover problem. I'm not going to discuss them here because I think that time will be better spent discussing heuristics for the navsac problem, but you can for example use the greedy algorithm design paradigm to generate some heuristics for vertex cover. Now, some greedy algorithms do better than others, but if you make the greedy choices judiciously you can get pretty good guarantees for the vertex cover problem. So the third strategy is to insist on correctness, in which case, you're not expecting to get polynomial time for general instance unless you're intent on proving P equals NP. And so while you're expecting an exponential running time, you still want a running time which is qualitatively better than naive brute force search. And this is exactly the point of the next video. We're going to give an algorithm which is indeed based on enumeration but it's a smarter enumeration than naive brute force search so we'll get a faster exponential running time, and that'll allow us to solve a wider class of problems.