The goal of this video is to develop an exact algorithm for solving the vertex cover problem. The algorithm will run in exponential time in the worst case in general instances, but it's nevertheless qualitatively better than naive brute-force search. One consequence of this smarter search algorithm is that the vertex cover problem is computationally tractable in the special case where you're looking for a small optimal solution that uses at most a logarithmic number of vertices. Let me remind you quickly of the vertex cover problem. The input is simply an undirected graph G. A vertex cover of a graph is a subset of vertices that includes at least one endpoint of each edge of the graph. The goal on the vertex cover problem is to compute the smallest size of a vertex cover. Let's consider a variant on this problem where we're additionally given a target value k, k here is going to be a positive integer, and we want to know whether or not there is a vertex cover with size k or smaller. Now, as stated, I haven't really made the problem any easier. If you could solve this version of the problem where you're given a target k, you can also solve the original one, where you want to know the smallest value of any vertex cover. Namely, just run this sub-routine for all possible values of k from 1 up to n, and the smallest value of k for which you can find the vertex cover is then the answer to the original optimization version of the problem. Rather, to make the problem easier, I want to think about the special case where k is small. So, for now, I'm going to be deliberately vague about what I mean by small. We'll fill in those details in due time. Now, why might you be interested in the vertex cover problem when k is small? Well, we talked, for example, one thing you might be modeling is hiring a team. Each vertex corresponds to a potential team member, someone capable of performing various tasks. A vertex cover means you hire a team that is capable of handling any task that might be thrown your way where the edges of the graph correspond to tasks and the endpoints correspond to the two people capable of performing the task. And, you can imagine, maybe you're only interested in forming a team if it has reasonable size, so you have a budget for how many people you could hire. And then, you're only interested in solving the vertex cover problem when there's a good solution, a small cardinality vertex cover, otherwise, you just punt and you're not willing to take. on the project. You can also imagine maybe you have some domain expertise that suggests that your graphs do have small vertex covers, recall star is just a vertex cover of size one. So if you know that your graph is star-like in some sense, you might expect that there's an optimal solution that has few vertices. Is it useful algorithmically to focus on the case of k small? Well, yeah sure, if you're looking for a small optimal solution, then brute-force search isn't as bad as usual. If you want to know whether or not there's a vertex cover comprising only k vertices, you can just check every subset of k vertices. The number of subsets of k vertices, assuming that there are n to start with, would be n choose k, and for small k, that's going to be like theta of n to the k. So in principle this naive brute-force search runs in polynomial time, as long as k is constant, as long as k is bigger one. But practically speaking, I mean you can't really imagine running this naive brute-force search algorithm and unless k was super small. You know, say k=3, maybe k=4, depending on the size of your graph. In any case, this naive search is limited to very small values of k. And it's then natural to ask, as we always do, can we do better? Is there a smarter type of search? So, the answer is yes, there is a smarter way to go about this search that's going to allow us to solve the problem for qualitatively larger values of k. The search algorithm is going to be driven by a lemma which is similar in spirit to the kind of reasoning we did about optimal solutions in our dynamic programming algorithms. And I think it will be a little misleading to call it an optimal substructure lemma, so let me just call it a substructure lemma. So consider it some input, so our job, the job of our algorithm is to check whether some undirected graph G has a vertex cover of size k or not. Consider also, some edge, let's say between u and v of this graph. In the same way as in all our dynamic programming optimal substructure lemmas, we thought about taking the original instance and reducing it by one in some sense. Removing an item, removing a vertex, removing a position of the alignment, and so on. We're going to be thinking about this graph G, but with one fewer vertex. Actually, two different graphs of that form. One that we get by deleting u, that's one endpoint of the edge that we chose, and in addition to u, all of the edges incident to it. And we'll also look at the graph that we get, by deleting v, the other endpoint of the edge, and all of its incident edges. I'll use the notation Gu for the graph we get by deleting u, and G sub v for the graph we get by deleting v. The lemma asserts that we can reduce the question that we care about, namely does or does not G have a vertex cover of size k to analagous questions on the smaller graph, Gu and Gv. Specifically, G does have a vertex cover of size k if and only if at least one of Gu or Gv has a vertex cover of size k-1. So the proof is not too hard. I'll be able to squeeze it in on this slide, and then, once we know the substructure lemma is true, I'll show you how that leads to a smarter search algorithm for vertex cover. So this is an if and only if statement, so we'd have to have two different parts of the proof, assuming the left prove the right, assuming the right prove the left. Let's start by assuming the right-hand side. Let's assume that Gu or Gv or both, does in fact have a vertex cover of k-1. Let's show that then G must have a vertex cover of size k as well. It doesn't matter which of Gu or Gv has the good vertex cover. Let's just say Gu. So let's think for a second about which edges of the original input graph G survive into the smaller graph Gu. For the purpose of this proof, there's basically two types of edges in the world. There's ones where one of the endpoints is u, that is edges incident to u, and then there is edges where neither endpoint is the vertex u. So the edges in the graph Gu are precisely those where neither of the endpoints is u. So let's call those edges E sub u, those are edges not incident to u, the edges in G sub u. And then we'll call the edges incident to u that got deleted, Fu. So let's call k-1 vertices that the vertex cover in G sub u, let's call it capital S. What does it mean to be a vertex cover? It means you include at least one endpoint of every edge. So S, by virtue of being a vertex cover for G sub u, it means for every edge of E sub u, that is every edge of the original graph, neither of whose endpoint is u, S contains at least one of the endpoints. So, if we think about capital S in the original graph capital G, the only edges that its missing are those of F sub u or those where one of the two endpoints was the vertex u. Well, that means that we just take capital S and we throw in the vertex u, we get a bonafide vertex cover of the original graph capital G. S takes care of all of the edges of E sub u by definition, and then u single-handedly takes care of all of the edges of F sub u, because all of those edges are incident to u. So that's why if we assume the right-hand side, we can conclude the left, if either Gu or Gv, Let's say Gu has a small vertex cover S of size k-1. All we need to do is to augment it by the missing vertex u, and boom, we get a vertex cover of desired size k back from the original graph G. So, what about the other direction of the substructure lemma? Now we have, now we assume that the original graph G does in fact have a vertex cover of size only k. And we show that has to be reflected in one of these two subgraphs, either Gu or Gv must itself have a small vertex cover, size only k-1. Let's let capital S denote the small vertex cover of the original graph G. So S has k vertices, and every edge has at least one of its endpoints represented among this set. In particular, the edge uv that we singled out at the beginning, one of its end points, either u or v, may be both, but certainly has to be in the set capital S. Let's say u is in S. So lets think about the pink picture from the other direction of the proof. Let's think about exactly the same decomposition of the original edge set capital E into two sets. Now, this set S, remember, it's a vertex cover of the original graph G. So S contains at least one endpoint of every edge. But now, u, which is one of the vertices in S, sure it, is an endpoint of every edge of F sub u, every edge incident to u. But u is not an endpoint of any of the edges in E sub u. So what that means is the other k-1 vertices of S have to be responsible for containing endpoints of all of the edges that survive in the G sub u. The vertex u takes care of edges incident to it. S with u removed, those k-1 vertices include an endpoint from all of the other edges, all of the edges in E sub u. So that completes the proof of the forward direction and therefore of the substructure lemma.