Video 4-8: Interleaving

0:04 There's a final section in this algorithmic part fixed parameter algorithms uh that I want to briefly mention. It's it's a nice little trick to combine techniques compared to the others. It doesn't uh improve things by uh just as much. Um but it's certainly a a simple thing well worth doing when if if you ever do this in practice, I think this is going to have an impact. uh it won't reduce the exponential growth though but we'll we'll see um that's called interle and the motivation is a bit uh coming from an extreme case that I'll also show you in a minute so far the algorithms uh conceptually had two phases we first applied some reduction rules uh I called it pre-processing um initially or kernelization if it has specific guarantees And so uh then you end up with a problem kernel where everything is bounded in size by the parameter and then you solve this this kernel with a depth bounded exhaustive search where here I mean depth bounded really means there's a parameter where you count down and as soon as that reaches zero you you stop whether or not this instance is solved. Now why do we not uh apply this kernelization each time in the recursive call in the hope that things get shrunk further and we might get a smaller search space. In principle this might work uh just because usually the the reduction rules somehow involve the parameter and in the recursive calls the parameter gets smaller. So the reduction rules might apply further than they did initially.

1:52 Uh that that's the key idea. And let's look at an extreme example just to motivate that this sometimes can help a lot. Uh the example uh I'm going to admit at the beginning the example is a bit made up to make the uh effect extreme um in the way that it's it's kind of leaving out other obvious things you would want to do in this case. uh but bear with me for a second just to make the point that interle can indeed give you a lot of benefit in extreme cases and then other cases it'll probably also help it's just not as obvious. So remember we had for where we're still talking about vertex cover I mentioned vertex cover is the default problem in FPT uh where we um we've already beaten it to death but there's at least one more substantial result coming next week. Uh and also here we'll talk about vertex cover again and we've seen this rule. If you have ever uh a degree a vertex of degree strictly larger than the parameter you you only the only option is to take that vertex because covering all its edges via its k + one or more neighbors is not going to stay below the parameter. Now let's compare two algorithms. Uh the one algorithm A is what we've done so far. The catch is we only apply this rule, none of the other reduction rules.

3:20 And that's a bit stupid, but let's uh let's be stupid on purpose to make the effect clear. So only this rule. Let me stress that here. So again, you wouldn't want to do this. This just makes the example clearer to analyze. Uh and then we call the same algorithm that uh we've had before the simple version where we just uh this was the the baby FPT algorithm from all the way back where we just take an arbitrary edge and say well I'm going to include either one endpoint or the other. So I get this two to the K search space. Okay, that's the simple FPT vertex cover. Uh and algorithm B is the same idea, same in ingredients but interled. So uh we modify this this algorithm keep the same basic recursive structure but we check whether we can remove more highderee vertices in each recursive call and so here's some code how this looks like um because it's so long ago simple FPT vertex cover here is um as we had it back then uh basically some base cases otherwise we choose an arbitrary edge and we take the the two options either of the two endpoints has to be included. Uh and then here we can even be smart and and return the larger of the solutions that wouldn't be necessary for just the search problem. Now the interleaf version um differs only very slightly. There's this part here where I just created space. Um so this part is new. Uh here that's the reduction rule, right? Uh we check if there's a vertex of degree strictly greater than k. If that's the case, then we remove that vertex. And that's a concise way to put it. I'm setting the graph to the induced subgraph that I get if I take all the vertices except for this vertex I want to remove. Now I'm remembering in this uh set C or cover that um in my solution I have to pick this vertex V, right? If I'm uh returning at the very end some solution some vertx cover then I should include this vertex V. So if we remember that but then also we can uh reduce the parameter because we've included one more vertex. So we have one more one less more uh that we can still include. The rest is the same as on the left except that here also we include this set of forced vertices.

6:04 Okay. Uh, and now let's look at a at a very specific family of graphs. Uh, I call them lollipop flowers for lack of a not used name. This one's super silly, but okay. Uh, so it's a it's a family of graphs GK where K is some some parameter. Uh and then there's a part here where we have uh these kind of dandelion shaped flowers. Uh let me let me maybe draw the concrete example for k= 6.

6:42 Um, so we have a a head vertex here and then there's k minus two stars attached each with k minus 2 leaves. So it seems like I'm drawing k equals 7, right? So I have to draw this seven five times. That's that's doable.

7:08 I'm drawing the vertices with different size, but of course they're all in just vertices. Nothing special about head, right? So, k minus two, one, two, three, four, five of these added stars. And each star has k minus one leaves. Five again. Uh, and then we attach uh a tail of 3k + one vertices. So, 22. Oh my god, what did I sign up for here? Uh, so one 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22. Uh, okay. Got it.

8:04 And this is the tail. Okay, imagine what the graph looks like. Now I'm asking the question, uh, can I find a vertex cover with K vertices? Let's find the minimum vertex cover in this graph. Is not actually that hard. Um, if you start from these guys, it's got to be best to include the centers of these stars, right? Otherwise, I have to include all these uh leaves. That's going to be worse. So, I'm including all those that also covers all these edges. So, these are all done. What vertex is next? What do I have to include in the vertex cover?

9:06 That one. Yeah. Yeah. We have to cover this edge, right? Um, this guy is out because all its other edges are in. And then the rest is pretty boring because now every other vertex has to be included, which will just be all the top vertices.

9:25 Now uh you don't need to count precisely that's far more than seven. Okay far more if you want now so that means the instance that we're um I guess I should say the input is the graph GK and parameter K threshold K. So all the instances will be no instances just our poor algorithms don't know about that. Okay, let me copy example? Uh first of all, I've done the counting for you in terms of the number of vertices. Uh you can count the head, right? We have k minus two of these stars. Then it's k minus one vertices each plus the one in the center plus the tail. So we have k squ vertices roughly. uh if you look at algorithm A, it first applies this reduction rule. Now the way the graph is constructed, there are no vertices of degree K or larger. So our degree greater K rule just does nothing to this graph. There's no highderee vertices. So uh because the algorithm otherwise is very very stupid uh it remains um at a search space of 2 to the K. Um and let's make this worst case assumption that we always pick edges from the tail when uh the algorithm does the recursive uh does does the random choice the arbitrary choice. So it'll pick some edge in the tail and include one of the two endpoints decrease the parameter but it has to try all the two to the k options. So the total time will be 2 to the k times the size of the graph to find the edge or something close to that at least. And eventually it'll answer no not possible. Our algorithm B the interleaf version initially also doesn't do anything right and then it picks one edge and nothing happens and it picks a second edge. So we go down the recursion tree goes down two levels. But at this point the parameter has gone down to k minus2. And now suddenly these vertices in the head become highderee vertices. And so in in one step we remove all of them or to be more precise we include all of the red vertices. Uh and notice that we already reduce the parameter too much. And so maybe after one or two further recursive calls but constant depth the algorithm can conclude that it's not possible.

12:36 And this shows you in this case you win by applying this reduction rule again because once the parameter is smaller it becomes active on a larger part of the graph. Okay. So by and large um we just go a constant number of levels down and we explore a constant uh search space in this specific case. And so the overall time is essentially linear in the size of the graph. Now it's a very madeup example. Uh it needs specifically this graph specifically these algorithms where we don't apply I mean the the biggest caveat is why on earth would you only do the degrees greater K reduction rule and not the one with degree zero and degree 1 vertices. you would immediately remove this leaf here and then you would actually remove the entire tail. Okay, but uh for the point for the sake of the argument you could have examples like this where interle helps a lot. Maybe dandelion would be better. I think that was already taken for some reason. So graph theory people have horrible names and a lot of them too right the general setup for interle so we've seen this extreme example uh what can we do in general um we'll make uh some slightly more restrictive assumptions than maybe necessary but this is the part that's that's nice to analyze uh so suppose we have an arbitrary uh problem par parameterized problem with a kernelization where now it reduces the problem to a kernel of size Q and that's a polomial. This is not always the case.

14:35 Okay. Uh but for most of the problems that we've seen it actually was a polomial size kernel at least uh for vertex cover we had k^ squ I think as the best. Um so here that would be what would be one instance right k squ came from if you remove all highderee vertices and also all degrees uh zero and one you're left with all vertices between degrees two and k and so uh you can't have arbitrarily many of them um you can't have arbitrarily big graphs um after you remove all of the vertices of high degree um so we need kernelization that produces a polomial sized kernel and does that in polomial time that's standard and uh suppose we have a a depth bounded search tree algorithm where we somehow split the input into subpros with some branching vector. So whatever that looks like in our vertex cover example, this was one and three. Um you'll see in the next exercises some more uh some more fancy versions of that. Uh in general that's often a way to improve the exponential growth by splitting up into more more cases. And let's also suppose the the branching itself. So how to make the recursive calls is computed in some time and that's also some polomial in the input in input size.

16:12 uh from this from this alone or basically this part alone we know that the search space has some exponential size and this base of the exponential growth alpha is just this root of the characteristic polomial whatever that is for these di okay just depends on those uh numbers by how much do we reduce the parameter in each of the recursive calls if we now um think about the variant a of the algorithm. Again, we first run the kernelization that takes p of n time and leaves us with uh an instance of size q of k. Then we uh for each recursive call in the worst case have to compute this r of n. So we have r of q of k because q of k is now the problem size. And so that's for the branching and then we have this for each recursive call in the worst case. Uh what happens if we do it interled? Uh you can uh write down general code for this if you want. Um the uh the general rule would always be as soon as the input is somehow bigger than what the kernelization produces right this q of k again is the size of the kernel then it it makes sense to run the kernelization again. So you uh run this kernelization and obtain the reduced instance and then you do the branching on the reduced instance and you do that recursively like this is this is to be inserted into your recursive algorithm. Now if you analyze the the running time for for this procedure with interle it has the same structure. It's uh also a recurs uh recursion depending on the parameter and for each recursive call you get right um a recursive cost for the size of the parameter in that recursive call. But now the extra terms they tend they shrink with um the parameter specifically here whenever um the input is bigger than this this Q of K and that K is the current K right that's the maybe most important bit that's not on the slide uh that's the current K or current parameter By current I mean in this recursive call and it's reduced for further recursive calls. Uh that's what's called L here. So we potentially in the worst case we have to run the uh kernelization in each recursive call that costs time P. But the input size for that kernelization is bounded by some function of L. And also the branching which takes time R of the input size is also now a function of L the current parameter not the initial parameter.

19:41 Okay is it looks like a a subtle difference that doesn't make any uh hasn't any big impact. The non leaf version was just this um but it has it has two kind of implications. one will be it makes the algorithm faster but to to know that or to see that uh it means that the analysis becomes a bit harder previously that's why I went over this uh before we started uh with this section again previously we could essentially ignore this inhomogeneous part of the recursion we just pretended this wasn't here solved the recursion that is left and then in the end multiplied by this term because it was a constant with respect to L right it's the initial parameter so in the worst case in each recursive call you have this cost now with kernel with interle the cost of this goes down so if you want to analyze you don't want to just upper bound it by the cost without interle you have to include it in the recursion so it makes the analysis a bit harder first okay um as an example Let's look at the same algorithm we've analyzed in detail before this better FPT vertex cover vertex cover which again was the um okay I think I'll have it on the slide again so the initial call um has potentially large a large graph but then we apply the reduction buses reduction removing all degree all vertices of degree zero one and greater than k and so the resulting graph is at most uh k^ squ in size. That's the the kernelization at the first step and then we start the interle recursive call. Okay, so there's a one-off cost in terms of the original graph size plus whatever we do in the recursive procedure. Okay, so I don't have the code for this again on the slides. It's the algorithm where we split off the case that all degrees are bounded by two in which case we solve trivially what the vertex cover is or we check whether we can solve it in with at most k vertices and otherwise we branch off but then we have one recursive call where we reduce the parameter by at least three because if I remove the case of all degrees at most two one vertex has to have degree at least three. So the recursive cost for this uh can be written as uh some base case and then for uh the recursive calls same contribution as before but now um an extra term that captures finding the largest degree vertex and potentially reapplying our reduction rule. And that's uh both can be done linear in the size of the graph and the graph is in the worst case quadratic in the parameter in the parameter of the current call.

22:48 Okay. Uh maybe for consistency I should have called this L here this K uh L that's what it was on the previous slide. But of course it's just a name for the local variable. Now the point is I cannot simply ignore this part if I want to get the tighter analysis. So um if we dig into this uh analysis from before what we did at this point was uh go from the sequence TK to the generating function and I'm only roughly sketching the process at this point. So we said there's um I can write this uh like this and then split off in the recursion after I shift it. So I'm taking out the first few uh the base cases uh I just leave as a fixed polomial. This was just a uh what was it? um was one right it was uh 1 + set plus set squared in our case um and then for the remainder of the sum I can insert the recursive uh equation maybe let's do it for the concrete example that we have here so I'm not going to do the full thing I'm just sketching it up to a certain point. You'll see in a second why or or what that is about. Um so one set plus set square we suggest cost is one for these small cases and then for k at least three we can insert the recursive uh equation. And then you may may remember or look up these two parts essentially led to some shifted and modified version of again the generating function. Didn't give that a name uh T of Z. So the the green part becomes some I guess here we pull out one set and then t of sets and we probably have to subtract some and then there's a set cubed t of zed and because I'm starting at three so this one's probably fine as is. Uh this one needs some subtraction because I start at three when uh the generating function would have started at one. But what's new is this k squ okay that didn't exist before we had a homogeneous recursion where we only had as sumance these recursive calls not anything else. Uh but this blue part can also be rewritten.

26:22 Um because if you look at it now uh this is just some specific sum and you can again uh look up formulas for this one. Uh just to give you a hint of why this this could be possible. If you take the geometric series where you have z to the k, you may remember that this is just 1 over 1 minus zed. Now let's take the derivative on both sides. Sounds a bit crazy maybe. Uh if you do that here though, it's a sum. So the derivative is taken for each sumant and then you have k in front and then set to the k minus one. And here we have to take the derivative as well as 1 - set to the minus one. So if you take the derivative of that oopsies uh is 1 - set to the minus2 that's uh and the minus in front that's the outer derivative and then you take times the inner derivative which is minus one. the minus goes goes away again. But really what it says is just 1 over 1 - z^ squ. And if you take derivatives another time, then you get something that's very close to the term to the series that we have here.

28:01 Um then you get uh I guess here we can actually sum at one from one because that first term is zero anyways. Uh that avoids having this negative exponent. So we have the k from before and then we get another factor k minus one and that's set to the k minus two. So here we can sum from two because uh all the two other the other terms are multiplied by zero. And here you can take derivatives again. So same game minus2 for the outer derivative um 1 - z to the minus 3 and then again the minus one for the inner derivative. So you get a similar type of formula for this series. That's not exactly k^ squared set to the k. It's k * k minus one. And then there's a shift we've said. But maybe with the uh kind of mod uh simplifications or or changes of variables that we've done last time, you can maybe get a glimpse of how you can get from this to the blue one.

29:09 So to cut things short, uh what you get from this blue thing eventually is is just a function of this form. It's some rational function. So it's a polomial of set divided by another polomial of set. Let me say capital for functions. So it's some rational function like this. and it'll actually always have a one minus set uh factor at the in the denominator. Okay, so we don't even need to figure out in detail how this works. Um it's not that's not the focus of this class. My point is you can use the same machinery that we've covered for the linear recur rec recurrences last time uh with generating functions and you can also solve these inhomogeneous equations where you just need to find a representation for this series and to be honest this one you could just type into wall from alpha and it'll spit out the result straight away uh for simple cases like this um no need to do it manually and So if you do that and do it in the general case, um you can again get a result that you can just use as a black box. Uh so if you have an inhomogeneous linear recurrence equation of this shape, same as before, but this additional um function added or additional term added and uh we assume that this additional term is not too big. this polomial bounded by a polomial. Uh then you can show in full generality if you take again this uh characteristic polomial that's actually the same as before.

31:07 Um that doesn't quite check out. I don't know. This is uh probably replaced by this. Forget about it. uh then you can you can get uh an asmtoic representation an asmtoic bound for the solution tn in terms of tn0 where tn0 is the previous uh recurrence without this inhomogeneous part okay in other terms what it says this this uh light blue part here it doesn't contribute to the grow to the leading order growth it doesn't contribute to the most significant part of the growth of this recurrence. If this stays a polomial maybe intuitively it's kind of clear because the overall growth is exponential in n maybe it's clear that if you do something polomial in each step that shouldn't harm too much. Uh but you're doing it in each step so you multiply it with a exponential part so it's not obvious. Uh the trick why it doesn't contribute a factor f of n times this um this growth is that also the added term shrinks if you go down the the uh depth the the recursion tree. So most of the invocations of this fn will be at the bottom level where n is is constant. Uh that's maybe the intuition.

32:33 So but uh what it means for you really is whenever you have such a um a linear recurrence and this additional term the inhomogeneous part doesn't grow exponentially you can basically ignore it. You just solve the equation as if it wasn't there and the result is at most a constant factor off. Uh let me comment on um uh just because it's so nice a little bit of advertisement for this this piece of mathematics. You can push this application of generating functions further. So what we've done um was we started in in sequence land. We had a recursion for a number sequence and we wanted to know how quickly it grows because it describes the cost of our algorithm. And uh from the recursion itself, this isn't obvious. So we translated it to generating function land uh specifically this um ordinary generating functions um and then used basically algebraic equations in this um generating function land uh to modify what we got from the recursion. So specifically here the recurrence equation gets a functional equation for the generating function which you could solve and simplify specifically partial fractions was the magic potion here uh that did the heavy lifting. So you get a closed form for this generating function where you can in the best case extract coefficients back. That's precisely uh to this point that's exactly what we did for the vertex cover example.

34:16 You can push this further by instead first approximating the generating function and then you only get back in the end an approximate solution for your uh number sequence. But often times that's the best we can get because the recursion is is so tricky that there's no nice closed form and it's not even clear how quickly it grows uh from the get-go. uh but there's um there's this um field called singularity analysis. So a singularity in the function like don't think about AI in this case uh it's just a point where the derivative of the function um is broken in some way uh where the function is not smooth. Um so it could be uh for real functions it could be a point like uh if you take the absolute value function it has a singularity at x equals 0 because if you come from the left and come from the right the slope is different and that causes problems for the smoothness of the function. Now in in general um you have to view these functions as complex functions mapping complex numbers to complex numbers and then singularities are in in a way both easier and harder to work with. Complex is always less intuitive but in a way the theory is a bit cleaner. To cut this short, um you can usually find a single dominant singularity, one of smallest absolute value and you can prove that this dominates the growth of the number sequence that you started with. So what you do is you approximate your your generating function by a simpler function plus an error term which is a big O term but of a slightly funky funky shape. So this is for the limit that set goes to Z0 not the more computer science usual n goes to infinity.

36:17 Uh and then um from this shape there are theorems like the one on the next slide that show you what what what happens if you take coefficients if you apply this coefficient plucking operation on this thing. You get the coefficients of f and suppose that's this and you get some error term that corresponds to the error term. So I I know this is uh it's impossible to follow this in detail because I haven't told you what all these things mean especially singularities uh we didn't talk about um just in case you're interested here's some concrete example of what these transfer theorems can look like and there's a technical condition it's not so important what this means if you're curious I can point you to the right places or I can tell you offline um if you can represent your function for example like this uh for some real alpha here and then the coefficients behave in a nice way the coefficients of f are essentially the coefficients of g with some error term where you get a polomial that depends on the on the power here okay and you can extend this further to uh solve other kinds of recurrences that's the gist of it. Um there's a a field called analytic combinatorics that pushed this to the limit. Um no pun intended I guess. Uh whenever you whenever you have a recursive description of some objects probably there's a way that with method with techniques from this field you can get an asmtoic uh approximation of the of the numbers from the recursion.

38:06 So just a little bit of advertisement because we delved into generating functions. Anyways, uh briefly back to vertex cover though where we left off was uh with this recursion that described the cost of our interleaf vertx cover algorithm. Now we just apply the blackbox theorem here and what we get is the cost is the same up to constant factors maybe as the cost would have been without this f. We just replace it by nothing. But that's this the recursion we've solved last time for the number of base cases which was exactly this 1.4 something to the k. So we get that now the total time is this uh exponential no polomial factor applied to it whatsoever. There was this um this one step where I said initially the graph can be arbitrarily big. We apply the reduction once and then comes the recursive part. This is for the recursive part. So we have to add the uh initial reduction step but that's all.

39:22 Uh so we basically transformed via this uh uh interle technique uh the cost from exponential search space times a polomial to uh just plus the polomial sounds like not such a big deal but in terms of actual time it can mean quite a big difference. Okay. And this is again the provable worst case uh actual time might be better if you don't always get the worst uh the worst case recursive calls. Uh the last bit I wanted to mention is that our better FPT vertex cover is not the end of the story so far. Uh um people have worked on this more and pushed the exponential growth a bit further down. Uh they also have this plus here. So they're also using interle. Um and so far this is the best the best result I could find. It's not clear how far you can push this. Um is likely that there is some limit below which it seems there's arguments uh against pushing further but I don't think this is reached yet. Uh but the algorithms essentially try more and more cases and more and more clever combinations.

40:42 Uh so it gets more and more messy. Uh but in principle you can push down this this recursive uh this this exponential growth uh quite dramatically from two to decay to 1.2 or 1.3. Um that's already a a pretty impressive result.

41:05 That's all I wanted to say about um this analysis and also the whole of FPT algorithmic techniques for now. Um a quick summary is what we've seen um the two strategies for designing FPT algorithms. One is the depth first added the depth bounded exhaustive search where we use the parameter to truncate recursive calls and the second was kernelizations where we shrink the problem size using uh some reduction rules and we've seen how we can analyze the resulting algorithms. Now again generating functions are pretty cool but if you don't love them just as much as I do you can use the blackbox theorems and all you really need is the characteristic polomial and interle kind of gives this this last twist uh that really the exponential search is is all there is in terms of the dominant Fast.