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.