0:00

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.