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.