Let's see how this substructure lemma 
naturally leads to a recursive search 
algorithm. 
The algorithm is recursive. 
I'm not going to bother to specify the 
base cases, which is when you're given a 
graph, with a most 1 vertex. 
Or whether you're given a value of k, 
equal to 0 or 1. 
So let's assume that the graph has a 
least 2 vertices, and that k is at least 
equal to 2. 
I wouldn't be surprised if this algorithm 
reminds you, of some of the recursive 
implementations we discussed for various 
dynamic programming algorithms. 
And in the same way those algorithms 
exhibited exponential running time, 
without memoization, we're going to see 
an exponential running time here. 
For all of our dynamic programming 
algorithms, we were able to cleverly 
organize sub-problems from smallest to 
largest, thereby eliminating redundantly 
solving the same sub-problems over and 
over again, yielding polynomial run time 
bounds. 
Here, we're going to be stuck with the 
exponential running time bound. 
Obviously not surprising given Given that 
it's an NP complete problem, but still, 
if you really want to understand this 
deeply, take this recursive search 
algorithm.Try to come up with a 
polynomial time version,try to come up 
with a small set of sub problems, ordered 
from smallest to largest that you can 
solve systematically.You will be 
inevitably stymied in those attempts, but 
you'll better appreciate what's non 
trivial about the recursive solution 
here. 
In step 1 of the alrogithm, we pick some 
arbitray edge, u, comma v. 
Why is it useful to focus on an edge? 
Well, by the definition of a vertex 
cover, it has to include either u or v, 
so that's our initial clue. 
We're going to proceed optimistically. 
We're looking for a vertex cover of size 
K, so let's assume one exists. 
What does the sub structure limit tells 
us? It says. 
That if such a solution exists, then 
necessarily either gu or gv or both 
themselves have small vertex covers, of 
size only k - 1. 
Moreover, it's a simple matter to extend 
such vertex covers to a small 1 for g, 
you just augment them by the missing 
vertex. 
So let's first adopt as a working 
hypothesis that g sub u has a smaller 
disk number of size only k-1. 
Let's recursively try to find it. 
If our recursive search comes back with a 
solution of vertex number of size k-1 for 
g-u, we're good to go. 
We just augment that by the vertex u and 
that's our vertex number of size k for 
the original graph of G If that recursive 
call fails to find the small vertex cover 
will you say, oh well then it must be 
that v is the key to getting a small 
vertex cover. 
So we do exactly the same thing, we 
recursively search g sub v for a vertex 
cover of size K - 1. 
If the second recursive call also fails 
to find a small vertex cover, one of size 
only k - 1, then by the substructure 
claim, the other direction, we know that 
the original graph G cannot have a vertex 
cover of size k. 
If it did, the substructure limit tells 
us. 
One of the 2 recursive calls would have 
succeeded. 
Since they both failed, we conclude 
correctly that the original graph did not 
have a small vertex cover. 
The correctness analysis is straight for, 
forward, formally you would proceed by 
induction. 
So the induction hypothesis would then 
guarantee the correctness of the 2 
recursive calls, so on the smaller, our 
sub problem is GU and GV the recursive 
calls correctly detect whether or not 
there are vertex covers of size K-1. 
The substructure limit guarantees that we 
correctly compile the results of the two 
recursive calls into the output of our 
algorithms. 
So if one of the two recursive calls 
succeeds, we're good to go. 
We just output the vertex cover of size K 
as desired, and this is the crucial part, 
if both of the recursive calls. 
Fail then by sub-structure liner we know, 
we correctly report fail. 
We know there is not a vertex cover of 
size k or less in the original graph G. 
So lets analyse the running time using an 
Adhoc analysis. 
Lets think about the number of workers of 
cost that there can be over the entire 
trajectory of the algorithm or 
equivalently the number of nodes in the 
recursion tree generated by the algorithm 
and then we'll come up with the bound on 
how much work is done on a given. 
recursive of call, not counting the work 
done by its recursive subcalls. 
And now, the cool part, and this is 
really where the rule of a small value of 
k comes into play is that, each time we 
recurse, we subtract 1 from the target 
size of a vertex cover that we're looking 
for. 
Remember, if we are given, as input, the 
parameter k. 
Each of our recursive calls involve. 
The parameter value of K minus 1. 
So what this does is limit the recursion 
depth or the depth of the tree generated 
by this algorithm to be at most K. 
Initially you start with K, each time you 
recurse you decrement it by 1 and you're 
going to hit base cases by the time K is 
around 1 or 0. 
Putting those two observations together, 
branching factor banded by two, recursion 
depth bounded by K. 
The number of recursive calls in total, 
over the entire life time of this 
algorithm, is going to be bounded by two 
to the K. 
Moreover, if you inspect the pseudo code, 
you see that not a whole lot of actions 
going on, other than the recursive sub 
calls. 
So even with a very sloppy 
implementation, where you have construct 
a G sub U, or a G sub V from the input 
graph g. 
Even if you do that crudely, you're going 
to get a linear time bound big o of m 
work, per recursive call, not counting 
the work that gets done later by the 
recursive sub-calls. 
So, that means an upward bound on the 
total amount of work done by this 
algorithm is the number of recursive 
calls, 2 ^ k, times the work per call. 
M 2^K*M. 
Now this running time you'll of course 
notice still exponential in K, but, of 
course it has to be exponential unless we 
intend on proving P=NP. 
Don't forget the vertex cover problem is 
NP complete. 
So what have we accomplished? We had a 
trivial exponential time algorithm by 
brute force search earlier. 
Why did we go to this rigamorole to come 
up with the second algorithm with this 
exponential run time bound. 
Well, this is a qualitatively better 
running time bound than we have before 
with naive brute force search. 
Here's 2 ways to see why this running 
time bound is qualitatively superior So 
first, let's just inspect this running 
time from a mathematical perspective and 
let's ask how large can we take K while 
still having a polynomial time algorithm. 
Recall that our naive brute force 
searched algorithm where you just try 
each sub set of K vertices random time 
theta of n to the k. 
And so that's polynomials Time if k is 
constant, and it's super-polynomial time 
if k is bigger than a constant. 
For this running time bound 2 ^ k * m, we 
can let k grow as large as log of the 
graph size and still have a polynomial 
Algorithm, So now we have the sig way 
from these mathematical balance to 
thinking through actually implementing 
these algorithms running them on actual 
data. 
So for the naive per search you have got 
this running time of of n to the k so 
even for a relatively small graph you 
know lets say n is may be fifty or 
hundred you are not going to be able, 
You're not going to be able to run this 
brute for-, naive brute force search 
algorithm except for extremely small 
values of k. 
3, 4, maybe 5 if you're lucky. 
So naive brute force search has very 
limited range of applicability. 
So by contrast our smartest risk 
algorithm can accommodate a noticeably 
larger range of k's. 
So remember the running time here is 2 to 
the k * the graph size, and so even for 
values of k up to 20, for many networks 
of interest you're going to be able to 
implement and run this algorithm in a 
reasonable amount of time.