Video 4-10: Interleaving

0:04 The last chapter here um ties together a few little tricks that um maybe if you've spent enough time on thinking about how to lower this this exponential base get lost easily. This is just a a kind of little trick that helps sometimes uh but I think it's it's useful to keep that in mind. It's called interle and the idea is that um so far what we thought about for these uh these two techniques of kernelization and and depth bounded search was kind of one after the other. First you take your input and you do some pre-processing to reduce it to some small kernel and then you apply the stepbounded exhaustive search and because this takes polomial time it kind of didn't matter too much what you do there. This is really what what uh costs a lot. But um why not if that's expensive anyways uh try to do this reduction in each recursive call because the parameter gets smaller that might actually help.

1:04 And uh yes it increases the cost you do per step here but the number of steps was the uh the big deal anyways. If we can get the number of steps down that would be useful. Okay. So as an example again uh we look at vertex cover and just to make the case that this can sometimes have an tremendous effect uh let me create an artificial setup here. Suppose we do this uh comparison with this straw man algorithm where we only do the large degree rule. If the if the graph contains some vertex of degree at least k then we we have to include that one because taking all its neighbors is already too costly. So we do only this um reduction rule for the kernelization whereas of course we could have used this other degree zero and one uh vertices as well but let's ignore that here to make the example easier. So algorithm A and that's really the straw man is not not a real contender but for bear with me for a bit. We do once this rule um remove all vertices that have too large a degree. It says until saturation because you know each time you take a vertex here the middle into the solution K goes down by one. So this can potentially uh kill a lot of your graph.

2:29 And then um we'll call the original simple FPT vertx cover which just branches over in some random edge. And uh the contender is the same rather limited uh algorithm but it does this in interled fashion. So we take this as a recursive method and before we do the branching each time we apply this rule and that's what this looks like. So here's the old algorithm just from uh copied from a couple of slides earlier and here's the one where before you do anything clever you apply this degree K rule uh as long as you can apply it and the hope is because here you reduce the parameter you might make some progress and uh skip some of the recursive calls right that's that's the idea and Um there's a specific family of graphs where this indeed makes uh a huge difference. That's these lollipop flower graphs. Um maybe the name speaks for itself. I don't know. Uh it is a tree at the end of the day. A rather simple instance for vertex cover if you take it in isolation. Uh but let's bluntly apply our two algorithms to it. So what is a lollipop flower? It has a parameter k and that tells you um we have this head vertex here that has k minus two such uh copies of of stars these kind of petals or flower parts whatever each of these has again k minus one leaves attached so that's also k minus 2 k minus 2 not k minus and then we have this long tail just a long path of 3k + one vertices. So 16 here and zero up to 15.

4:37 And the numbers are crafted to precisely make this work. uh the number of vertices is k^ squ + 4. You can work it out mostly dominated by this part. Now if you apply rule a uh apply algorithm a this rule greater k does nothing because no vertex has degree is strictly larger than k. The largest degree here is this four which for k= 5 isn't even k. But then um if you apply algorithm A after this first rule, it just goes into the exhaustive search mode. Now note that um well the parameter K is the K of the graph. So we're trying to find a vertex cover of size K for this graph which is completely hopeless. K is five.

5:31 uh even just this tail part, there's no way you're going to need at least say half of these vertices and that's already um I don't know one and a halfk, right? There's no way this going to work. But the algorithm doesn't know yet. So it stupidly picks k edges and does both recursive calls until it eventually finds out ah tough luck. Nothing works. So it spends essentially a two to the k time right now algorithm B with the um again the rule initially does nothing but after it has removed two edges we're down to k minus 2 as the parameter and then suddenly these uh k minus one degree vertices in the head are beyond the are killed by the rule and so we have k minus one of those here. So after deleting these k minus one, my parameter is at zero and I'm I immediately notice I have to stop. There's no solution.

6:32 So after spending essentially time just to read the graph, we're done because we go down a constant number of steps and then you terminate. Uh if you want to see this in action, there's um animation here.

6:48 It's the part that we've seen seen last time, but now there's uh also this uh lollipop, right? Um I just go to the end and here you see it explores this entire to the K tree whereas the interleafd version it starts picking any edge and branching over the two points. Right? So now it has picked two vertices. Now you see now it um immediately goes to the head and uh decides this is infeasible because with the parameter five you're only allowed to pick these five vertices. The two from the tail and the three here and then you're out of budget and so you only go down two steps.

7:49 Okay, so pro proof in point case in point is sometimes this interle idea does help. Now this is a bit of a two algorithms are very constructed and this input example is as constructed as it can get. So can we hope for some general worst case speed up from this? And for that um let's look at again our analysis from before and let's even apply this in a slightly more general way. So we assume we have any kind of kernelization that produces a polomial size kernel.

8:25 Remember in general a kernelization is not required to do that. It can produce an input instance that has a size bounded as some function of the parameter. It could be very very large in the parameter as long as it's no longer dependent on n. And here we say let's have a really good kernel a polomial size kernel.

8:47 And um then we do uh suppose there's some depth bounded search tree that has some such branching vectors. So we branch into i different cases and in each we subtracted something from the parameter exactly as we had it for vertex cover but kind of as the general scheme that's what it could look like. uh say also the branching is polomial. So we want everything to be cheap right polomial. So uh if if we do that then the search space should have some some uh exponential size and for the running time of this approach we want to compare with first applying the kernelization once then forgetting about it and just applying the algorithm here. That would be algorithm A from before. What does that cost? Well, we have u we compute this um kernelization that costs us p of n time. That's this part. And then we have uh how often do we have to do the branching? Well, alpha to the k times and how large is the input on which we uh have to find the branching rule.

10:01 Well, that's the output of the kernelization Q of K. And note that here in particular, this um kind of the the size here we assume is fixed. And we're just analyze the search space. Now, with interle general setup is is a recursive procedure stylized like this.

10:22 Um if the instance you get in size is larger than what the kernelization could give then you try to apply that kernelization because then you may save something you make it smaller and then on this smaller instance you do your branching [snorts] and that of course is recursive. So the running time for that is uh is similar to before. We have the recursive calls but then the um the branching itself and this this first step here that costs P or R of well Q of the current size. So the parameter goes down over time. So these if you go down in the recursive tree also the branching cost that you have keeps decreasing because you make the instance smaller and smaller necessarily as you go down. That's what the kernelization gives you here. So the non-leaf version instead here had this with k where k is the initial parameter. Okay. Um so fine um we have another lovely recurrence to solve but this time we can no longer simply say we uh multiply each the number of of leaves or the number of um calls just by this factor here that doesn't depend on L because it does now depend on L.

11:53 So previously we had this constant cost essentially uh for the recursive calls and now it it goes down. It should be cheaper. How can we analyze this? Um again as a concrete example let's look at the interleafd version of this better FPT algorithm. So same algorithm as before. We have the special case as a stopping condition all degrees less than two. But before we even go into that part, we apply our kernelization. Um, which is this this bus kernel. So, uh, we check if there's any degree zero vertices, ignore them. Any degree one vertices, throw them away and include the other endpoint of the single edge. And any degree greater K vertex, well, you have to take it. Um, and we've we've shown this is Buzz's kernel.

12:51 We've shown earlier in this chapter that the kernel that results from this is quadratic in K. So this we always do um and we apply that first. Then we do the base case check are all things degree at most two and then we do the recursive calls if we still have to. What is the running time for that? Well, we have this um cost in terms of the size of our graph and the two recursive calls. And the main difference here, this is K. So as K gets smaller, this also gets smaller.

13:31 So like before we can set this up as a as a recurrence, but now it has an inhomogeneous part. I don't just have these recursive calls here. I also have this this other term uh but um luckily generating functions can still help us in almost the same way and as long as this term can be written as some or upper bounded by some polomial all of this always works um and I'll I'll go through it a little bit um but we'll do it at a fairly high level because we're interested in the in the qualitative result here more than in the fine grain details of the calculation. Um you could also make this an exercise of solving these recurrences exactly but I think for our current algorithmic application that's less important. So by the very same trick as before we uh split this sum take the first few terms off then this sum starts at three which means I can replace tk by its recursive definition and I get this. Now the the two terms here are the very same terms we've had before. So those become uh shifted set cub terms out to um set cub t of set.

14:51 This this term becomes this part is again the the function which shifted but then I have to subtract the first few terms which I'm missing here. And what's left is is this um sum over k^ squ set to the k this one.

15:09 Okay, that's not uh involving any of our tks. So this is in terms of the equation for solving for t of zed. It's a constant but it does involve somehow uh zed. So I have to work it out what it is. Um and eventually here you can just one solution is just look it up. Uh another solution is find out how simp allows you to evol evaluate these. Maybe there's more doits needed. You can also do it manually. We already know this one. The standard geometric series that is what everyone should know from kindergarten.

15:50 You can formally take the derivative on both sides of this equation and it just works. The derivative of a sum is the sum of the derivatives. What's the derivative of z to the k? Well, k * z to the k minus one. And what's the derivative of this lovely thing? Well, it's spelled out here, right? Is a 1 - z to the minus one. Then it's derivative of a function with some function inside. So you you use this chain rule of derivatives. It's -1 * 1 - z to the minus 2 and the inner derivative is -1. And so multiply the minus 1's cancel and you get 1 over set squ one one over 1 - set 2. Is that useful? Well, it gives us something that's a bit similar to this but not quite. We can take another derivative of this thing. Take the derivative again. Uh the second derivative of the left hand side here. Again you do this for each term is this. And the second derivative on the right hand side turns out to be that. Now this is not exactly what we need but is close enough. If you multiply out uh basically you have to add these two up, right? So you can puzzle out what this sum is, what this series is. And all you really needed is uh taking derivatives.

17:17 So um you you could do that. You could also be lazy as I was here and say ah it's going to be something with uh a denominator of 1 minus z cubed and some polomial in zed that we may not even we may decide not to care.

17:35 Why do we not care? Well again this is this is a generating function of its own kind. It's the generating function of some if it was just this 1 minus 1 over C cubed. There's there's some way of rewriting this again as a generating function. And if you if you peek at this, I just need to divide by two. So it really is the generating function of a half k n then * n minus one. In other words, this is a fairly modestly growing function. It's a polomial. The coefficients grow like a polomial. Whereas the other parts here we worked out they grow like an exponential. So this is a cute little term that we can also essentially ignore.

18:35 Okay. Um more formally if you put this into here and then solve this equation for t of zed what you end up with is this representation. There's some polomial in the numerator and the denominator has this polomial from the actual equation from the recursion and this one minus set cub comes from the inhomogeneous part. So it has the exact same form as the previous kinds of recurrences. There was also just some rational function. The only difference is we gain a few extra roots but the roots of this thing are all one. So they're not going to be contributing the exponential growth. Okay, at least like um in this case where this is k^ squ. If this is a different function maybe the result is different.

19:28 Okay. So um we can find all the the roots here and we have this triple one but the dominant one is again the the one we had before as well is the very same uh 1 / z is still this 1.46 four, six, whatever it was.

19:48 And that's a general principle that this this inhomogeneous part uh doesn't really help uh doesn't change the growth rate as long as this function itself is uh is working out to be well the formal I guess this is the algebraic way of saying it. um if the function doesn't have a singularity. So say a zero in the denominator is a singularity in the sense that the function escapes to infinity at this point. If um if your generating function doesn't have anything like that, it's not going to contribute to the exponential growth.

20:32 You can also tie that up into a neat theorem um by by going through the analysis in this way. Yeah, same recurrence as before just we have this inhomogeneous part here on top. If the inhomogeneous part is sufficiently small and the condition that works is this. So it it might even be exponential but it should be with a smaller growth rate than your largest absolute value root of this characteristic polomial.

21:02 Then the same conclusion as before is true. we get this um the same same answer as for the homogeneous equation where you just delete this fn.

21:19 Okay. Oof. Let's see if you're still awake for this and that will come to an end. Now that I see it, I'm not sure if we can actually say what it claims the theta class without any uh okay with this recurrence that has literally no other terms. Okay, it's fine.

23:21 Uh should I give you more time or shall we discuss? Uh it it's actually a rather simple but a bit a bit of an annoying one because uh here you have this inhomogeneous part two to decay and it just dominates the rest. Um in a way the question is a little gotcha question that be careful with this theorem. It needs that the inhomogeneous part doesn't grow too fast here. This is the same recurrence we had before of course. So you would expect this one is the the growth if you don't have this two to decay. But if of course the topmost call has already a two to decay term that's that's just going to dominate everything.

24:21 Okay. It's maybe debatable whether indeed this this dat theta here is is all you get. Uh the lesson I want you to take from this is that the toll term might also dominate. Okay. Um let me finish with uh two little remarks. First of all, what we've seen here is an instance of a general really cool strategy that you can use um on many problems in combinotaurics in a way with these these recurrences were counting recursive calls. So it's a combinatorial question and for many combinatorial questions you can apply these generating functions and somehow go from a question about counting things to some uh complex analysis questions about functions. There's a lot more than what I've shown you. So we we've we're we're as computer scientists working in sequence land. We deal with sequences of numbers and recurrences. That's where we feel home. uh if you venture out into generating function land, you can turn this into these functions. A recurrence equation turns into a functional equation for the generating function. And then sometimes you can uh do things on the right that you couldn't easily do on the left, say at least not as systematically and and mechanically. And if you're lucky, you can then easily go back.

25:46 That's how we've done it here. Um the general uh power for this is stay more on the right and don't go back exactly but only as an asmtoic statement going back and that's where the the full power of this comes in. Uh you can approximate the function the generating function in a specific way. What you need is a singular expansion. So you rewrite the function as an approximation that's valid close to this uh this um root of the denominator. In our case I mentioned before this is a singularity because the function becomes strange there. The uh technical term is in in the sense of complex analysis the function doesn't behave like a power series uh locally and you can approximate a function. This is all well defined but a bit beyond what I want to go into here. But there's um there's a specific way how you can approximate a function around a a special point where it goes wild. And if you do that approximation, you can also get an approximate um term for the coefficients that turn into a a normal asmtoic representation as n goes to infinity. Whereas here um the approximation is as zed goes to zero.

27:08 So it's a different kind of uh limit regime. And there's tons of cool math behind this part that makes this approach really powerful. Whereas for what I've shown you, there's also purely combinatorial tricks that would have also gotten the result. One example of these transfer theorems that allow you to go back from a representation of this function. So f is the this is a precise function. g is a simpler function where you already know what the coefficients look like and you have an error term that somehow tells you how close are these. If you go close to a say here the the singularity is at one and forget about these technical conditions for now. This is mostly to showcase what this can look like. You're not supposed to know the details. Um but then you can say the coefficients of f are essentially the coefficients of g and the error terms here translate into an error term for the asmtoic expansion.

28:08 That's the uh the flavor of these theorems. That's all um you need to know here or maybe it's all I want to show. I don't I don't even know if you need to know this. uh maybe some at some later point maybe there will be some extra module on something like this. Uh I should mention under the term of um analytic combinatorics there are cool lecture videos from from Bob Satvic that dig into this if you're if you're interested and there's good books as well. Uh don't want to say anything more about this.

28:55 That's what we used. Um locking coefficients. This was essentially using the derivatives. I can pop this up a bit more. Let's stop here. Um stating the final result for our FPT algorithm. What the interle bought us in the worst case is that we have this search base and then plus a term that depends on the original graph size. We don't have this multiplicative dependence anymore. So it's a rather modest improvement at the end of the day in the worst case. Even though this lollipop example made it look very dramatic. [snorts] Uh if you're worry about how far you can push this constant down um two years ago it was improved from 1.27 to 1.25. Uh but I'm also going to tell you this is all like with the open AI anthropic proof of um ETH falling you can get a subexponential algorithm. I might say a few more things about this in two weeks. I mean this is nothing up here is wrong but you can get subexponential assuming these proofs are true and they're from last week so or a week before.

30:26 Uh that's the exponential time hypothesis. We'll speak about this more. My point is don't pick as your thesis topic to try to lower that constant. It's very pointless. It probably always was, but now it's also uh asmtoically not interesting. Okay, let me wrap up this first part. Uh we've seen fixed parameter tractable algorithms as a specific notion of being faster in a very well- definfined sense. And we've seen essentially two techniques kernelization and these uh dep bounded search trees. Um the next unit will go to um impossibility results in this area. When should you not be able or when should you not look for FPT algorithms anymore? And then after that we'll do some some uh more closer to research techniques based on that and maybe then more comments on the recent developments.