In this video and the, and the next, we'll develop an exact algorithm for
solving what's called the vertex cover problem.
This is a well known NP-complete problem. As such we certainly don't expect our
exact algorithm to run in polynomial time on general instances.
But, the algorithm does showcase. 2 of the algorithmic strategies that we
discussed for dealing with NP complete problems.
First of all, we can interpret this algorithm as on general instances.
Well, it's true, running in exponential time.
Nevertheless, improving markedly over the more obvious naive.
Brute-force search. This illustrates the point that for many
NP-complete problems there is a lot of room for algorithmic ingenuity, even
though you're not going to come up with a polynomial time solution.
A second interpretation of the algorithm we're going to develop is that it's
polynomial time for special classes of instances, in particular instances that
have an unusually good optimal solution. So, let me introduce you to the vertex
cover problem. The input is simply an undirected graph.
The goal is to identify the smallest size.
That is, the minimum cardinality of a vertex cover of the graph.
What is a vertex cover? We call a subset of the vertices a vertex cover, if for
every edge, at least one, possibly both, of the edges' endpoints lie in the set S.
There is, of course, always a feasible solution.
You could always choose every single vertex.
That's certainly going to be a vertex cover, but the hard question is, how do
you make sure you get one endpoint from each edge, in the most parsimonious way.
So what might this problem represent? Well perhaps you're assembling a team of
some sort. So maybe a team of programmers, maybe of
lawyers, maybe of football players, who knows? But think of the vertices as being
potential people you could recruit onto your team.
And think of an edge as representing a potential task that your team might have
to complete and the two vertices in the edge represent the two people who are
capable of accomplishing that task. So then, what a vertex cover is?
It says, hire enough people so that every single task you can accomplish.
You have one of the two people in your team that's capable of accomplishing that
task. So you could imagine various
generalizations of this problem. You could have a wait for each vertex,
for example, indicating the salary that you would have to pay that person.
You could also imagine that instead of edges you have what are called hyper
edges if more then two people are capable of accomplishing a given task.
But the unweighted graph vertex cover problem will be interesting enough for
our purposes here. Many people are of the opinion that this
is a poorly monitored problem. Many people think it should be called the
Edge Cover Problem, not the Vertex Cover Problem because you are choosing vertices
to in some sense cover the edges by picking at least one of their end points.
But this is the conventional name for this problem.
In the Vertex Cover Problem you are choosing a set of vertices and edges
provide the constraints. Let's now jump to a quiz to make sure the
problem definition is clear. So the correct answer is A.
Let's consider each of the two graphs in turn.
Let's start with the star graph on n vertices.
So this has one vertex in the center and n-1 spokes.
The claim is that it has a vertex cover of size one, obviously the minimum
possible. That vertex cover comprises just that
center vertex. Why is it a vertex cover? Well, every
single edge is a spoke. And one of its endpoints is the center
vertex. So you just pick the one vertex.
And you hit all of the n- 1 edges of the graph.
So how about a clique on n vertices? So, a graph in which every single one of the
n choose 2 edges is present. Why is n-1 vertices necessary and
sufficient for a vertex cover? Well, to see why it's necessary, consider any set
that excludes at least two vertices of the graph.
Because it's a clique, there's an edge between those two excluded vertices, and
that's an edge, such that neither of its endpoints is in this set.
So that's why the set is not a vertex cover if it has, at most, n-2 vertices in
it. On the other hand, if it only excludes
one vertex, then there cannot be an edge with both of its endpoints missing from
this set, because there's only one vertex in total missing for the set.
So that's why any subset of n-1 vertices will be a vertex cover of a clique, n-1
is sufficient. Figuring out the minimum size of a vertex
cover in these two special graphs probably didn't seem that hard.
And it's not! But when you're talking about general graphs, that you don't know
anything about Computing the Minimum Quantinality Vertex Cover is in fact an
NP-complete problem. There is no polynomial time algorithm
that solves it, unless P equals NP. So that's definitely a bummer.
So let's review our strategies for dealing with NP-complete problems.
So we discussed To an earlier video. So the first strategy is to identify
computationally tractable special cases of your NP-complete problem.
Now in the best case scenario, the version of the problem that you have to
solve in your own application lies squarely inside one of these
computationally tractable special cases, then, you're good to go.
More commonly, the instances that arise in your application won't necessarily be
in one of the computationally tractable special cases.
But, it can still be useful to have subroutines ready for various special
cases. One thing we discussed in the past is the
potential of a hybrid approach. Perhaps you do a little of brute-force
search, and for most of the branches of your brute-force search, the residual
problem falls into a com, computational tractable special case.
And it turns out there is some quite interesting computational tractable
special cases of the vertex cover problem.
And the story here is very much in parallel with discussions we've had in
the past about the independent set problem.
So, in particular, you can solve vertex cover in polynomial time on path graphs.
Just like we did with independent sets. Actually, more generally, in trees.
Or even more generally, in what's called graphs of bounded tree width.
But at least, for trees, that's a application of dynamic programming which
you're now. In a good position to solve yourself, so
I encourage you to think that through as an exercise.
Why can you solve the vertex cover problem in polynomial time, in trees? So
another quite interesting class of graphs, where you can solve the vertex
cover problem in polynomial time is the class of bipartite graphs.
One way to think about a bipartite graph, it's, it's a graph that has no odd cycle,
so then, obviously, trees are a special case.
An equivalent definition is that you can partition the vertex set into two groups
A and B, so that every single edge has exactly one endpoint in each of A and B.
That is bipartite graphs can also be thought of as the graphs for which there
is a cut that slices every single edge of the graph.
It's far from obvious how to solve the vertex cover problem efficiently in
bipartite graphs, but it can be done as an application of what's called the
maximum flow problem. That's a graph problem which lies just
beyond the techniques that we're covering in this class.
So what I'm going to cover in the next video is using a different algorithm, yet
another computationally tractable special case of vertex cover.
Specifically when you're interested in the case that the vertex cover is small.
And what I mean here by small is logarithmic in the number of vertices or
less. The second strategy for dealing with
NP-complete problems is to relax the requirement of correctness and to focus
on heuristics. Algorithms that are fast but need not
produce an optimal solution. So there are some pretty good heuristics
available for the vertex cover problem. I'm not going to discuss them here
because I think that time will be better spent discussing heuristics for the
knapsack problem, but you can for example use the greedy algorithm design paradigm
to generate some heuristics for vertex cover.
Now, some gritty algorithms do better than others, but if you make the Greedy
choices judiciously, you can get pretty good guarantees for the vertex cover
problem. So the third strategy is to insist on
correctness, in which case, you're not expecting to get polynomial time for
general instances, unless you're intent on proving p=np.
And so, while you were expecting an exponential running time, you still want
a running time, which is qualitatively better than naive brute-force search.
And this is exactly the point of the next video.
We're going to give an algorithm which is indeed based on enumeration but it's a
smarter enumeration than naive brute-force search.
So we get a faster exponential running time and that will allow us to solve a
wider class of problems.