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.