0:48

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.

Â