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.