Video 4-2: Depth-bounded search I

0:02 In the next section, we'll look at some first algorithms that properly use the fact that we're only aiming for an FPT algorithm and not a polinomial time algorithm in general. Uh so we look at some uh uh some first design technique for this for this regime. And the simplest kind of design is actually something we've already seen, namely an exhaustive search. Um but we'll make it a bit more uh explicit that we bound the search or the the size of the search space as a as a function of the parameter and uh our brute force search for satisfying assignments um essentially did that but it it kind of uh didn't didn't have to work hard to do so. Uh the question is can we can we do this in other problems and can we do something that's nonobvious uh in this in this realm and as a first example uh let's consider the vertex cover problem again and uh remember that the the brute force solution for vertex cover um had this this running time where we go over all subsets of size Okay. So there was a a polomial part we're checking but the the key component was this uh so it was n to the k times a polomial in n and so this n to the k is not an ft running time because I cannot separate out the dependence that might be exponential but only depends on k from n. and is in the basis here and I don't get it out. So this is uh is not an FPT running time. If you think about the problem though for a minute, you realize that we've we don't have to check all subsets. We can do something much smarter.

2:14 And the idea is to turn it turn it around. The uh end result that we are looking for is a vertex cover. So it has to uh cover all the edges by picking vertices. If you look at a single edge, that means every vertex cover has to use one of the two end points. Maybe both if that's useful, but it has to pick one. So an obvious choice is to pick some edge and just to do a two-way branching. Do I include the left or the right endpoint? And these cases are not exclusive. And uh that's the basis for a very simple algorithm that does just that. Now here the parameter is part of the the parameter of the problem turns into a parameter of the function. Um so that we can keep track of when to stop. The algorithm uh otherwise is is relatively simple. So there's a base case. If I have a graph with no edges, then I don't have anything to cover. So a vertex cover is fine to use the empty set. If I ran out of parameter, then I cannot add anything more. And if I reach this case and I'm not in the first case, I actually know I have edges that are left uncovered. So there's no vertex cover I can report.

3:39 And here it'll mean that uh this instance is a no instance. There's no vertex cover with uh at most k vertices. Um if neither of that's the case, then we're in the the normal case. So we pick some edge. There is one because it's not empty. Uh I choose one arbitrarily and then I iterate over the two end points. And for each of those I construct the graph where I remove this vertex and all its incident edges. Right? So you have some some graph could look arbitrary. And then there's there's these two vertices uh v and w connected by this edge. And now suppose I'm I'm using this is my u here. So I get rid of this and maybe this is connected to uh many other vertices. So I'm getting rid of this vertex and all its edges. And what's left is the the black graph without the red edges. This is GU. Uh and then I recursively call my my method. Uh try to find a vertex cover for the rest. But you're only allowed k minus one vertices because I've implicitly picked this vertex u. Uh so I I don't store vertex u anywhere at this point. I'm just doing this for both recursive options because the the method is slightly smarter returns the smallest vertex cover. U if we have the choice to do that anyways.

5:24 Why not? So um after we do the two options, we try the two possibilities and recursively all further options um if only one of the two leaded to some vertex cover then we return that and here we add this vertex u back in. Okay, at this point you see this red vertex that we removed is included in the vertex cover. So all the edges that we removed are already dealt with. That's the important bit for correctness. And the last bit is the last part just takes care of the case. If I had if both options led to a positive outcome, I could have taken either endpoint and they both led to some vertex cover. I'm just picking this the smaller one because that's going to be the better one. Uh just shows you that um with the same running time here um you cannot just find the yes no answer. You can actually find an optimal vertex cover.

6:23 suppose assuming that it has size less than K. Okay. Um I guess the correctness of the algorithm is somewhat evident um from from this argument here. Whenever I remove a vertex all its edges have been covered and the rest is held dealt with recursively. So formally you would do an inductive proof and show that uh in all solutions that you construct all edges are covered. What's left is uh the running time. And so here um we obviously have two recursive calls for each uh for each run of the of the code where we're not in the base case. And in the recursive calls we always make K one smaller. So after a k steps deep uh we'll stop. And so that's exactly why this is called a depth bounded search. I'm a priory saying I'm not going to go deeper than k steps. And so uh 2 to the k is the size of the search space that I'm I'm spanning open. And the time for the rest um um isn't isn't super important here.

7:42 uh but you can check that the construction of this graph might take linear time and I guess everything else is actually faster. So the overall time now has the form for an FPT algorithm because the parameter the only the only thing that's not pol polomial only contains the parameter and is nicely split off as a factor.

8:14 Okay, so that was the first kind of slightly non-trivial idea. Maybe you could have come up with this uh without any of the theory about kernelizations. Um but at least now we have the language to speak about what it means for vertex cover. Uh, of course this means that Pvertex cover is in FPT. Another remark about this code is that we don't need to know the parameter up front to do anything uh interesting here to do something interesting. It's actually good enough to just guess a K and run the algorithm and see what happens. And once you have this idea and you analyze what comes out, you might as well just increase K until the algorithm succeeds. And so just to make that very explicit, here's the code for that. But it really just calls that method with increasing K um until we find a solution. Now this is this will always terminate after some point because every graph has a vertex cover if you take all vertices.

9:21 What's interesting about this is what is the running time and uh the running time here is as often as this loop runs. So uh if overall the the true outcome the true answer is K, there is a vertex cover of size K, then you're running this loop from zero up to K. And uh the running time for this simple vertex cover method is what we just analyzed.

9:51 And if you simplify that sum, I mean this part doesn't depend on k prime. So it goes out of the sum as a factor. What's left is the sum of the first powers of two that's bounded by the next larger power of two. And so really the whole thing has the same running time as if you had known the parameter before up to constant factors. So what looks very wasteful iterating over all values for k. It's like a linear search for the right value of k. uh you may have come up with smarter solutions like binary search or exponential search or or something like this. Uh but here really all it says if your cost is exponentially increasing it doesn't matter what you pay up to the point the dominant cost is the last call anyways. So you might as well step up one by one.

10:49 Okay. So this this already shows that um we're getting a bit more than we initially set out for. We don't just solve this parameterized problem. We now have a proper algorithm that can solve the optimization problem vertex cover. But the running time depends on the parameter which is the optimal uh output size.