Video 4-9: Linear Recurrences

0:02 Now back to our famous famous vertex cover problem where we've already had some FPT algorithm where the kernel was two to the K where we again remember the branching that we've seen so far was pick a any arbitrary edge one of the end point end points has to be in the vertex cover try both options. If you do that for depth K if K is the budget then um you get this two to the K search space for vertex cover. Can we do better? Uh there's several answers to this nowadays but let's um do the um immediate one.

0:43 One idea is that we can try to do better on the base cases because so far the algorithm didn't do anything smart at the base case it gave up when there was no hope at all. So if I'm out of budget I can no no longer pick any extra vertex then I give up and if I've covered all edges then I'm happy and I succeed. We can do a bit better namely um if we look at uh graphs with only small degree vertices. What do graphs look like that have vertices where the largest degree is two? Well they can have some isolated vertices not super exciting. They can have stuff like this individual edges. They can also have paths. Uh maybe of of odd length or of even length both can happen. And they can have cycles.

1:40 That's degree two. I cannot do much more I cannot even build a tree sadly right that already needs uh a vertex of degree three. So really this is all and this this means the graph is a disjoint union Well, that's um probably not a very interesting class to start with, but if we're left with such a class in a recursive call, we know what to do because what's the optimal vertex cover for all these cases. The isolated vertex, I can just ignore. For a single edge, I pick any of the end points. For a path, this basically have to pick every other vertex, so there's a stupid way to pick the three points here, but of course, I can always start by not picking the end points. And for a cycle, it's completely symmetric. So, if I have an odd cycle, I have to pick one more edge one one more vertex than one would want in the alternating pattern.

2:51 If it's an even cycle, exactly a half the number of vertices. So, if I have such a graph, I immediately know how many vertices I need for the optimal vertex cover. Okay? And algorithmically, you do you do one depth-first search, say, to find the connected components. Um then you know whether it's a cycle or a path, and I think you can deal with these two special cases. Here, you just start picking every other vertex starting from not the first, and here it doesn't even matter until you've uh walked around the cycle.

3:30 Uh do do do >> I mean, of course, if every vertex has degree at most two, then the number of edges is also small. Let's throw that into an algorithm where we do um nothing smart other than that. So, um This is uh very similar to the old algorithm if you still have that in mind. If we have no edges more to cover, then we're happy and we return the empty set as the optimal vertex cover for this subgraph. If uh we have some edges left, but we don't have budget for more vertices, then this is impossible. Then, if we have this special case, all vertices of degree at most two, we find the optimal vertex cover. Um and let's let's call the vertices that we need to cover all the edges there capital C.

4:39 Uh if we need more than K, then we're out of luck. If we need at most K, then we return this C. Okay. And what's left is um the previous case, so um we do whatever we've um uh we we um I think we haven't really talked about this in the context of depth-bounded search. We've looked at this rule for the kernelization, though. Um Here, if we take a vertex with maximal degree, this makes good progress because either that vertex is in the vertex cover or all of its neighbors are. And probably that other case usually makes good progress or you can even stop right away. That was the rule we had for kernelization. If we have a degree um K + 1 vertex, so here in general, you pick any any vertex with maximal degree and branch into these two cases, either that vertex is included or all its neighbors. The benefit of this of this base case here is that we now know this maximal degree vertex needs to have at least three uh edges because all vertices if all vertices had at most two, then we would have stopped already.

6:02 And that helps us a bit because we now know in this one case that we include at least three vertices in our set. So, this um set B of the vertices that we delete, I guess. Of course, we delete them from the graph, but we include them in the vertex cover. Um that's what you do here. So, uh you take the the graph where you remove those vertices and try to recursively solve it where you subtract your budget appropriately. And in this case where we can make larger progress, uh the input of the parameter gets smaller by three. That's that's the basic benefit here. The rest is the same as we had it before.

6:53 Maybe let's record the picture. Yeah. If we have a vertex and it has three neighbors, then we have either this or the flip version.

7:21 Now, clearly this seems more clever, but uh does this buy us anything in terms of the worst-case running time? For that, we need to analyze the running time for this. Or again, to make things a bit simpler, we'll mostly focus on analyzing how big the search space is, how many recursive calls we have.

7:42 Okay. For the worst-case running time, um I guess we should imagine we can build a graph where we never run into this this uh early truncation case. And let's just assume where maybe this is not even worst case, it's pessimistic case, okay? We assume the worst that can happen individually. If you can find a single graph where all of this happens simultaneously, it doesn't matter. It's an upper bound, see? So, we never run into this base case, and we always need both recursive calls for the vertex and its neighbors. And we ignore that here some some things like picking this vertex of maximal degree or checking for these cases, that gets a bit cheaper because we lose some vertices. Um but if the parameter K is is substantially smaller than the graph, then this is maybe even justified. As an upper bound, it's definitely true. So, let's say um we do a recurrence in terms of K, in terms of the parameter.

8:42 If we start with zero, then we immediately stop. Otherwise, if we have a parameter K, we do a linear scan of the graph for checking the conditions and finding the vertex of maximal degree. And then we have two recursive calls where the parameter goes down by one if I take the middle vertex.

9:02 And I reduce this by at least three uh let's start with with exactly three. If I pick these uh other ones here. Right? So, that's a lovely recurrence. How do we solve that?

9:21 Let's further simplify this a bit and ignore the cost here for now, and just count the number of base cases. So, how often do you end up with uh T0? Uh then you can just multiply everything by by n squared for this. In the worst case, the graph has n squared edges. And that's an upper bound for the total running time. And we'll we'll not even try to make it uh much smarter because uh you'll see this um the dominant part comes from the BN. Um This is a bit bad. This should be a K, right? Mm. I think here my notation is a bit confused because this B really counts the parameter.

10:16 >> Let's say this is a recurrence in TK. The N, of course, is the number of vertices. Uh the important contribution comes from the base cases. So, we get a recurrence for the small cases, uh 0 1 2. Um these are immediately solved as this up to two vertices that can have at most a single edge and so on. Um Ah, so this is a parameter. If I can pick at most one or two vertices, that's where we stop. And if we have the general case, then we just have these two recursive uh terms for the number of leaves. So, that's looking a bit simpler than this. Uh still, I don't know if you've seen a technique to solve these kind of recurrences.

11:06 How would you solve it? >> [snorts] >> If you had to do this now. mention something here as well for justifying this step a bit better.

11:29 If you think about the recurse the the recursion tree of this algorithm, it's a binary tree because we always uh have two recursive calls. And the base cases that we count are just these leaves here.

11:44 But then, of course, the um intermediate number of uh steps here is upper bounded by the number of leaves as in any binary tree. It's precisely uh n one less.

12:04 So, by counting the leaves, that's what this BN does or BK BK does. We get within a factor of two with the number of recursive calls in total, even including the the ones that recurs further. And if we multiply each of them by the the cost we spend at the root, then each of these has to do this this step here of finding max degree vertex and checking if the checking all the degrees. Then at at worst, we get this quadratic overhead for each of these nodes. So, how to solve such a recurrence? What's the It's going to It really looks like it's exponential still, right? It feels not that much different from just doubling going down by one and doubling the number of children, which was the two to the K. Maybe for like for clarity, we had this the old version was some BK prime.

13:12 We had two times BK minus one, right? And then some some base case. And that of course led to BK prime being two to the K.

13:29 So, we should expect something exponential here. Um Let's see. There's a general technique that solves all these kinds of recurrences where you have potentially even a constant multiplied by some term that goes a constant number of steps back. So, BK minus some constant. You can have any mixture of such terms. Like here, we have two terms but that go back to a different number of steps. You can have any number of these. And in principle, you could even deal with something non-recursive there, but we don't have that here but it makes life a little easier. The tool to do systematically solve these This This other more physics math tricks that get the same result, but I think the cleanest systematic way is generating functions. So, if you've never Have you seen this ever before? Such a kind of this this power series as a way to solve recurrences? Okay. Then um I think you'll like this.

14:34 It sounds at first rather mysterious, but bear with me for a sec. So, we define um a function that has a formal parameter set. It's written as set because you could think of it as a as a function in on the complex numbers, but we'll not we'll not need this. So, you can think of this as a just an algebraic object. It's some power series, and we can manipulate it just symbolically. And if you want, you can think of this as uh this variable set of being less than one so that uh we don't have convergence issues, but the sum makes makes some sense.

15:27 Um we'll define this so that if you take a sequence like the our BK, you turn it into a single object, this this generating function, just by this this formal series. And with that definition, we can use our recurrence to plug in what we know. We can rewrite the term we know for B of Z. All right, by definition, our our sum here. And then um what what is done here in one step is inserting for BK the recursive formula.

16:01 Um let me zoom out a little bit or uh put one extra step here. I start with three. That's where the recurrence becomes valid. And then I can insert what the recurrence tells me for BK.

16:22 But of course I cheated by starting at three. I can't simply do that. I have to add the extra terms back. So I have Z squared B2 and Z B1 and Z to the zero B0. So these I have to also uh keep there. And I can insert that these are all one, right? So this is all just uh Z squared Z one. That's That's these guys here. And that is the the part where we inserted the recurrence. And now you can uh manipulate this. First of all, the sum, if you have a a power series like this, you can split this up into two sums. One for the BK minus one, one for the BK minus three. Then you can pull out factors of Z. And then you find you have a the same kind of shape again. So that's that's done here. I pull out one Z for this one. I pull out three Zs for this one.

17:20 Now if you look at Look at this carefully, this is actually the same as B of Z. If you shift the index, K starts at three, but then we start really at K minus three at zero. Here it's almost that. We have to subtract a little bit because we only started at two. So we have to subtract the first two terms. So here, this thing immediately gets gets B of Z. Here, this thing you need to subtract the first two terms again. Okay? But other than that, we've now rewritten our recurrence into an equation for this function B of Z. Again, these these terms are just uh You can insert what we know. This is one. This is one. Uh then you multiply out with the Z. So the one stays alone. Here we have Z and minus Z. That just cancels. Then the Z squared also just cancels. Uh kind of lucky. And what's left is z times p of z and the z cubed p of z.

18:27 Now, treating this as a formal formal equation in this variable p of z, you can solve this. You can just bring all these p's to one side.

18:44 Right? So, I'm subtracting z p z and z z cubed p z. Then I have p times 1 minus z minus z cubed equals 1, the thing on the right. Now, of course, you can divide by this polynomial. So, what you get here for this for this obscure function is always if you if you go through this and look where do we really need um properties of this recurrence, uh all that we kind of needed is that there's some constant shift and that we can pull out factors. All of this works in in rather full generality. And you'll always end up with a rational function, a polynomial divided by another polynomial.

19:24 >> [snorts] >> Okay, now you may say, "Cool, that helps me not at all." Right? Because this is uh just some mysterious way to write this function. Uh but you can move on from there. Do people know partial fractions? Partial fraction decomposition, partial fraction decomposition. Um there's a general formula if uh if you look on the TCS cheat sheet, So, here is the general recipe explained. Um you can also ask a computer algebra system to do this. I know that Wolfram Alpha can do it. Um This uh I should have prepared in in SymPy. This is a you know, this um open open source computational algebra system in Python that can do these things well, but I can never learn this I can never remember the syntax. Um That that we should maybe figure out. I'm sure it can also do partial fractions. The the point is you can factor this polynomial in the denominator.

20:51 And it has in this case three roots. Over the complex numbers, every polynomial completely factors. You know this. So, there's always going to be three roots for this guy, even though some might be imaginary. And you can always write this as the product of these. So, this 1 minus z minus z cubed. It is somehow z minus z0 z minus z1 z minus z2. And um in this case, even the z's are all distinct. Uh they're here. Um Give me a sec. The link broke. I can't get it back.

22:20 The reason I want to show this is that I think it's it's useful to know tools of this of this form. And I want to convince you how easy it is to use some of these things.

22:33 If you can get uh Google Colab to work. Because it's Python and because it's uh open source, it's integrated Huh. It's It's loading, but it doesn't finish loading. I don't know. Maybe we'll have to do it another time.

23:29 No internet. That's a bit bad for the live stream. What's happening with eduroam? Okay, there we go. Okay, maybe I'll I'll come back to it later. Um Live demos are always dangerous. All All that currently shows you is how to factor a polynomial, which uh or or to how to find the roots of a polynomial. Uh the goal was that you were able to do this on other examples quickly. Uh you can always write a polynomial like this, factoring it over the complex numbers, so you can always find a decomposition of this form. And then, if you have uh a rational function like this, you can always find a representation as a sum of these uh fractions where there's only a the the contribution from one of the roots in each. Uh how to find these constants? There's this cute trick that you say, um suppose I want to find the one for Z0. So, um I can take this equation as I have it here. I want to solve for A0.

24:54 I can multiply by Z minus Z0. So, take this. Um I really don't feel like copying the whole thing. So, uh you multiply the whole thing by Z minus Z0. And then you set set to Z0.

25:35 What then happens is that um these two other terms on the right-hand side get multiplied by zero, so they're gone. This cancels and you only have A0 on the right. And this, you have whatever that term is. I mean, the the Z minus Z0 cancels with the factor in its denominator. So, I might as well put this here instead of the um multiplied-out version.

26:04 And so, if you multiply by Z minus Z0, you just cancel this contribution. And so, by setting Z to Z0 in the remainder of this stuff on the left, you get your constant A1. Now, because this is already in a rational number, I'm not going to do it because it's not making things nicer. It's some horrendous number here. Um but each of these terms will have some constant up here. It's just some number. Now, each of these terms, also no matter what this constant of this this root looks like, is just a the the sum of a of a geometric series, so something of this form um all set to the Uh well, I'll I'll I'll have it on the next slide instead of writing it. one over set J to the K times set to the K. So, this is uh let's work right to left, I think is a bit easier to see. So, you have this this geometric series. That's what we call a geometric series.

27:12 It has set to the K, but then it may have some factor in front. And this is just a number, right? Set J is some some root. It's a bit annoying because it could be a complex root, like in this case, but don't worry about it for now. Um this this part sums to Well, first of all, I can rewrite this, of course, as K greater equals zero, then Z divided Z J to the K. So, this should sum to one over one minus this Z over set J.

27:48 Assuming that this converges. Again, if Z is small enough, smaller than this set J, then that'll be fine. >> [snorts] >> And so, this is what we should expect. Now, there's an a term in front that just multiplies with this. And that's precisely what you have on this side. It's this minus A J over set J, that's that part. And the divided by one minus one over one minus Z over set J, that's that's the geometric series. Aha. So, these terms are it's essentially such infinite sums. And at that point, we can go back. We've made this formal um change. It's a bit like like a other kind of transforms, Fourier transforms, or other things where you you go to a different space. There some manipulations become easier and then you transform back. And for the transform back, you just need to make somehow these terms again look like generating functions. And voila, that's um what these look like.

28:50 So, this is formally a generating function. And there's this notation of plucking the coefficient. So, this set to the K in in uh square brackets means I'm taking the coefficient out. Um Uh I had this here on the slide, but I never read it out. So, if if you have this definition, then the coefficient at set to the K of this generating function is BK. It's um comparing coefficients as you would do for a polynomial, but you can also do it in a infinite power series.

29:30 And so here, if you pluck the uh Kth coefficient of B of Z, you get back BK. But B of Z is the same as the sum of these terms. And there I can pluck the coefficient using this formula. And so, my result for BK is the sum of the coefficients I get from these terms individually. Now, maybe you say this doesn't look all that nice. But it is a closed form for our recurrence. This is precise. It's an equality all the way through. Now, granted, there's some constants. The A AJ are some numbers that we haven't figured out, but in principle, they can be computed. It's just annoying numbers. And the sets as well, they're also just some numbers. But if you zoom out, what does this mean? How fast does this grow? Well, it's all exponentials. Uh but exponentials are uh some are better than others, and some of these are complex numbers.

30:31 But if you take the absolute value, the complex numbers don't matter much. All that counts is the absolute value of the base of the exponent. And if these are three different exponential growths, only the this this the fastest growing makes any difference. So, we might as well ignore all of these. In this case, if you look at the concrete numbers, um I really would have wanted to have the absolute value of this guy now, which um Uh now uh it may It's showing the collab. Let me show you. Uh so, this was our recurrence. Um Okay, this is already showing the reformulated version. Let let me just uh for the sake of um the demonstration how easy it is to compute with symbolic algebra. So, this is SymPy library that you can import and is already installed in most Jupiter environments. Then you can say, I I need a formal variable X. And now I can define a polynomial, say X cubed - X squared - 1.

31:48 And then that polynomial is written even with nice LaTeX. And there's a function solve that you can give um a term that it's equal zero. That's the equation, and you solve for X. And then you get uh different solutions. And here you can show the three. I mean, this is a a degree three polynomial. The precise solution is symbolic there, but it's not particularly lovely. But the rounded version is here, and the absolute value is here. Uh this doesn't exactly match the polynomial we had. This is already the characteristic polynomial.

32:28 But you can this is the reciprocals of those. Sorry about that. Um I'll I'll show you the the theorem on the next slide that kind of follows from this analysis, but then kind of puts it into one theorem that you can just apply without going through the derivation each time. In this case, Z0 has uh a smaller absolute value, so if you take the one over the reciprocal, that's the largest contribution. So, these other two are lower order term. And here specifically this one over Z0 is 1.46 something. And so, that's going to be the growth rate. Where did we come from? This was an algorithm for solving vertex cover. And we started with an algorithm that had two to the K. And now we're with the simple trick of uh treating the special case of degree at most two graphs separately, we brought it down to 1.46. Uh rather cool. Um the general uh theorem for for solving recurrences of this shape, um that is what ties to the collab, uh looks like this. If you have a recurrence where um the right-hand side as T shifted down by some D1, D2 up to DI, uh I think here it's allowed that some of the DI are the same, so you can represent several recursive calls with the same subproblem size or subproblem parameter.

34:02 And um D is the largest of them. Then you can always write this explicitly in this form that follows exactly from this generating function derivation, but you can shortcut to the asymptotic growth by looking at this characteristic polynomial where um mnemonically, so you you write Z to the D, the largest D, minus and then this minus D1 is exactly the minus D1 here, so you just copy these down in a way. But you have to remember to put minuses between. That's if if you work out um the derivation, that's what it what it comes to. And then that's that's the formula we used here as well. And we start from this TK is TK minus 1 plus TK minus 3. That's the largest thing I subtract is 3. And I have this is K minus 3 and K minus K minus 1. Um it's already evaluated to the 3 minus 1 and 3 minus 3.

35:19 Okay. And the crawler is probably what you will use most. The order of growth only depends on the root with the with the for this one now a largest absolute value. Okay?

35:54 Maybe you can uh Let's let's just say you guess. Like um if the link would have worked, you could have just typed this up. Now, let's just pretend we're trying to solve this by thinking hard or by gut feeling. Suppose I have some hypothetical algorithm that doesn't split into this K minus 1 K minus 3. That's this one that we had. That's the the actual algorithm we looked at. But suppose you find some other clever way of decomposing the problem. And these these vectors that you subtract with the the guys here are these options. Which of them gives you the best running time? What do you think? I think at this point it's a a gut gut feeling guessing exercise.

38:11 Well, what we could do is is uh work it out here step by step. What do I have to type for the polynomial for the different values? Let's say we take Shut up, auto complete.

38:28 What's the first option? One and two. What would I have to type for the characteristic polynomial? Well, the largest thing I subtract is two. And then I have to subtract X to the power two minus the thing I subtract. So, there was one and x to the 2 minus 2. And the rest is copied. So, to solve for the two roots, what you get is these two roots. And the one with the largest absolute value 1.61 is the one that dominates. So, that is worse than 1.4 something to the K. Okay? This corresponds to the 1 2 vector.

39:17 Look. Chuck. That one corresponds to this polynomial. And that gives us 1.61. That's larger than 1.4. Here's the 1.4565 blah blah blah. Uh let's do uh one more and then the rest uh you'll have to believe me. What do I have to type for? Uh good that auto complete is stupid. Um what do I have to type for this? Don't believe the AI.

40:02 Yep. And so there what I get are these lovely all of these are going to zero, but this one is the 1.38. That's the best we've seen so far. And the other one the 2 2, you don't even need this heavy machinery at all. 2 2 means you go back two steps each time. So, that's going to be square root 2 to the power of K. Right?

40:33 So, this this says TK is 2 * TK - 2. So, make the subs this make the substitution K prime is 2K. But this goes back one step in K prime. So, the fake solution this T K prime of K prime would be 2 to the K prime. But, now if you insert again what we have, that K is K prime half, then this becomes square root 2 to the power of K.

41:16 And that's 1.41 something. So, actually this guy is best. Uh I mean, I find it a bit surprising because you'd think going back two steps is kind of more powerful than having this one, but the four really helps. I And the this this is just something we have to do the math.

41:36 Okay, but now you know how to analyze any such algorithm. If you have a a depth-bounded search where you recurse, and this the reduction in the parameter is any such list of different things, you can always work out this polynomial and and guess what the size of the search space is. >> [snorts]