Video 4-3: Depth-Bounded Search I

0:02 Let's stop just uh juggling definitions around and instead um come up with some algorithmic techniques that use this uh notion of parameters. And the first and and simplest I guess um is a kind of exhaustive search that uses the parameter to make it not arbitrarily expensive. I think on on an example it's easiest to see what that means.

0:31 We've actually seen an example even though a not interesting one with this brute force algorithm for satisfiability. It kind of had if you pick as parameter the number of variables naturally a search tree that was bounded in depth by the parameter and that led to an FPT algorithm. It was for a parameter that isn't usually small but the same kind of trick does work for other problems. And the first one we'll look at is our uh lamp lighter problem, the vertx cover problem. And we'll use the canonical parameterization. Okay. So I give you a graph and um a threshold k and ask you can you cover all the edges with at most k vertices and you're allowed to take a function that depends horribly on k but not uh more than polomial in the in the graph size.

1:24 Um you can do something similar as for the satisfiability problem by picking an arbitrary edge and saying okay I mean I have to cover this eventually. I can pick one of the end points. If I pick one of the end points not then I have to pick the other one. And so you have a a natural bisection over any edge. You have to pick either one endpoint or the other end point maybe both but not none.

1:54 And that gives you a simple um algorithm that you can can execute. Maybe let me show you an example first before we go through the code. Uh so here's uh a little input graph. And uh this is the recursion tree where we pick as the first edge this edge 01. Now um we'll only ever get there will be in principle a second search uh sub tree that we never get to. This is the sub tree where we decide zero is included in the solution. So in all of this here we decide we're going to take zero which means all these edges are already good.

2:42 So for the sub problem I'm just deleting them. That's why it's gone here. Okay. Um, now you also have to remember that you've used up one vertex. So here we had a threshold of three. Now we've reduced it to two. Uh, then we pick the next edge that is not covered yet. I mean the next edge in the sub problem. And again we have two options. This time again we pick this vertex one. And uh we see which edges are already covered by that guy. So what's left is this little triangle. Now sadly here it turns out we have a budget of one left. You cannot cover a triangle with one vertex, right? Uh even without going through the case distinction, this is obvious. You cannot pick just one vertex and have all three I just covered. So I have to backtrack. This was a mistake. Where's my backtrack? Backtrack. Backtrack. Uh picking the one here was apparently a mistake. Let's try the other option. Picking the two here. Of course, that's better because it has many many more edges, right? Okay.

3:52 We're not trying to get smart straight away. And in this case, uh I see there's only these two left. And uh of course, I can do it. The algorithm does this very structured. So, it picks this edge and decides, oh, maybe I should pick this this uh vertex here, even though that's a degree one vertex. And you already smell this wave this um opportunity to improve things. Uh so it it picks this one and finds out I'm still left with an edge I can't cover. I have no vertices left to do that. So eventually I have to pick this one and then everything's covered. So that's the final solution. And we find that here by observing that we have no edges left. Okay.

4:45 U uh if you find it helpful, you can see this in action. Uh it just shows you how it um branches into exactly the tree we've seen. Maybe that's not super insightful. Um here the code um if you think about it you can keep keep the code running even after you you found one solution in the hope that maybe you find another one that's higher up in the tree and has a smaller vertex cover. So what I've shown you is when you stop the first time you have one that's is enough for the decision problem. The same algorithm in the same worst case running time can actually solve the optimization problem as well but just keep going. Now here in this in this graph there's only one uh solution. If you get rid of one edge then there's more solutions. Let's maybe do this a bit faster. And you see because the graph is symmetric there's this different solutions.

5:45 And then for slightly larger things this already gets a bit out of hand. And um let's maybe rather see the overview here. Um, of course, it will eventually be a complete binary tree. That's how we defined it.

6:02 Um, okay, maybe maybe more uh fun to watch than really useful. The point is the algorithm is simple. At each step, you pick an edge and you do two recursive calls where either you pick one endpoint for sure in the solution and then see what that does or pick the other endpoint and see what that does. And uh crucially if neither of that leaves anywhere an optim feasible solution then there is none with kvertices because you've at each point um try it exhaustively all options that you had.

6:40 Uh because it's the first time you do this. Let's um briefly discuss the code for this. It's a simple recursive algorithm but just in case. Uh so you always start with a graph and a parameter. the threshold you're still the number of your budget for uh vertices. If no edges are left, you're happy. Then you can return the empty set, which is your signal. Pick the empty set. That's going to cover all my edges. The return value of this is always a valid vertex cover of at most k vertices. Uh if K is zero and we've not exited here, that means we have a problem because we've run out of budget and have edges left. Otherwise, we pick an arbitrary edge and um for either of the end points, we take the graph where we've removed all uh edges incident to this vertex that we remove and then recurse on that graph with one less budget. So let me maybe um introduce this notation here. It'll come later again. But this is a bit clunky, right? We define the graph where we leave out one vertex and we leave out all edges that no longer make sense because their end point has been deleted.

7:57 This gu is the same as an induced subgraph And it's somewhat standard to write this by giving the graph and then in in square brackets the subset of vertices. So that thing is the induced subgraph of G.

8:39 in this uh set that we give here it's just one vertex where you remove the vertex set where you remove one vertex. Uh that notation will be more will be convenient to use um for other problems as well.

8:53 uh for these two options you compute the return value of the recursive call which could either be a valid vertex cover for that sub problem or this I can't do it uh special flag uh and here this is just um one of them will only ever happen right because we return right away if uh the one recursive call says it's not possible I might as well return whatever the other one returned. And here I guess I'm assuming that's uh taking the union with not possible returns not possible.

9:42 Um if both are possible that's the case that's left here then in this case I'm returning the smaller one that allows me to find indeed the optimal solution the smallest Okay. Um, we never really needed to check for a set to be a vertex a vertex subset to be a vertex cover. This kind of was handled in the recursion. Um, that's the uh truncation here. The running time analysis is from from the examples you've seen is I guess rather easy. K always gets exactly one smaller and we have two recursive calls. So if you wanted you could say there's initially some N and K. Then we do two recursive calls on something that's losing maybe some edges. Maybe I should say M here rather.

10:45 We can always get rid of isolated vertices. They never contribute much. And what do we do on top? Uh I guess we need some linear term for uh computing this this induced subgraph and other things.

11:11 And so this clearly doesn't seem to change m. So I'm going to have this this term as many times as I recurse. And this one goes down. So you get this uh this running time uh from the um running example. I guess not hard to believe, not hard to uh prove. Okay. Note that this is way better than the stupid brute force for vertex cover. If you go through all size K subsets, it's much more, right? Um this n to the k that's right um to not lie, let's say theta. This is much much more than 2 to the k even for relatively modest n and k.

12:22 So in a way we get something non-trivial. Now you may have noticed that for this to work we need the parameter as an input which from the theoretical side is a non-issue because we define problems to be parameterized so that you get this parameter as a function that you can compute or uh the problem has a threshold as part of its input. If you think about more from a from a broader perspective, you want to solve the optimization version of vertex cover, uh then it's a bit inconvenient that you need to know this parameter up front. And it turns out it it isn't really needed for the running time we want here. Uh for for one thing, of course, you could just say I'm going to binary search. K is a number between uh zero and n. And um I can take n half and then use this algorithm. But then you've already lost because the first call is already two to the n half.

13:28 That's too expensive. So don't do the binary search. Now, you could do um something slightly smarter. You could say, I'm going to use exponential search. I'm going to start with small K and double K until I overshoot and then I do binary search from there. That's better.

13:57 Um but you're still going to do in the worst case 2 to the 2K. So this this one's to the n half. You could do exponential search instead. So this is right binary search. Juke juke juke juke juke juke. Um exponential search would mean start here, double in each step until you overshoot and then do the binary search. Um, so you would still pay for this for this one to do the 2k in the worst case. So it turns out good old linear search is better if you just keep increasing from the left step by step. You may use many more steps. But the point is that the steps exponentials are weird. The whole running time is dominated by the very last call. exponentials are such that each time each new call costs as much as all the previous ones combined.

15:08 So, uh it's better to um not jump ahead of yourself. Maybe you need to do K was one to check that the next one isn't feasible. So, that's what's written here. Uh if you don't know okay K you just try from the bottom and the first one that works is yours. Um in the case of of vertex cover it's that way around the k + one is not needed here. Then if it's uh if you would do this with click then you would have to go one k beyond what's feasible. Vertex cover goes from infeasible to then feasible if you have enough vertices. And click would go the other way around.

16:11 Okay. The analysis we've informally maybe discussed um if you sum up the running time for this linear search, it is essentially twice the last step.