Video 4-4: Kernelization

0:02 Before we continue looking at some concrete algorithms, there's um uh a related notion to FPT algorithms, the notion of problem kernels, that you can already see from uh what we've looked at, and that's uh as you'll see is an equivalent formulation, but it somehow sometimes is much more natural to think about. Um that's the It comes from the idea of of a preprocessing uh step that um sometimes you can by uh looking at a specific input get this feeling, like in the example we've seen, picking that edge and then trying that vertex was clearly stupid. We should have when there was this um this edge in the tree and then here this was the input graph, the algorithm selected this edge and then decided, "Oh, let's try to put this one in the solution." Like, why? It's just obvious. If you have a degree-one vertex, you want to take the other end point of that edge.

1:02 Uh that's a simple insta- an instance of a reduction rule that in general says, "Here's a an input. I'm going to transform it to a slightly different input where um I can cheaply prove that it doesn't affect the uh feasibility, um but it's somehow a bit easier or smaller."

1:25 Uh we want to do only things that can be done in polynomial time at this point, and they are not allowed to at all change the satisfiability or the yes-no character of the input. Um one one example for the satisfiability problem again is uh clauses that are obviously satisfied. So, for example, here a clause that contains uh this is the other way around uh a single literal clause. If you have um a clause that contains only X, well, the only way to make that true uh it's a conjunctive normal form, so every clause has to be satisfied. The only way to make that true is to set X to true. And vice versa here, the only way to set that to true is false. So, if if you have such a clause, you can just replace that variable with the appropriate name. Either there's a solution with that variable setting or there is none at all.

2:23 This alone for SAT in the worst case doesn't do anything. The interesting problems we know three SAT as the is is a still NP-hard and has as assumption that every clause has exactly three literals. And we don't have any of this. So, it doesn't help in the worst case. Uh but sometimes and you can see it even as a special case of this uh resolution calculus. Uh if you have two clauses that have some shared pre- some some non-shared prefix and then one has X, the other has not X. Well, no matter what you'll do, you'll uh kill one of these two. So, um you can replace this by a larger clause where you just take either these or either these because any satisfying assignment will either if X is set to false have to satisfy one of the A's or if X is set to true will have to satisfy one of the B's.

3:26 Well, that's just saying I have to satisfy either some of the A's or some of the B's or maybe both. And that turns out to be well, practical SAT solvers the most important ingredient. They then do a lot of cleverness in trying to pick the right When do you apply this rule? This is um usually many clauses could be combined with a resolution like this. And it makes the clauses longer and longer, which isn't necessarily a good thing. It makes the formula longer and longer. Also not necessarily a good thing. Uh but the hope is that you some at some point uh can also get get rid of clauses if they say contain X and not X then you can just delete them. Or if you somehow get to to clauses that are short because A and B are maybe not disjoint, they might overlap and then the result might actually not be twice as long as it looks like in this general way of writing it.

4:25 So you could say um this is in a way a very powerful rule if you apply it correctly. Uh trivial example we've seen for vertex cover is this what I pointed out uh before if if you have vertices of degree zero, no edge at all drop it. And if you have degree one vertices, you know what to do. These are kind of for free. How far can we push this?

4:59 The goal in um specifically this FPT style of preprocessing is well, let's try to shrink the entire input to something that's only a function of the parameter and not the actual input size originally anymore. If we can do that, then clearly the resulting solution is FPT easy. Is in FPT because its size is already bounded by the parameter. So it's the running time of the overall algorithm can only be a FPT running time.

5:33 Let's see um one concrete example that's a bit less boring uh that's a bit more insightful, still rather easy. Uh if you have again the vertex cover problem and you find some degree larger K vertex, a vertex that has more than K edges. Uh if you think about for a second, all of these edges need to be covered, you're only allowed to spend K vertices so you can simply not cover uh the edges of this single vertex if you don't take this center. As a you have a vertex here with a lot of edges going out. And of course, this is not all of the graph. It could continue with other edges of various type. Maybe this. Uh but clearly all of these need to be covered, and you don't have budget enough to cover all the others. So, this guy needs to be taken. That's what this this rule says. If you have a vertex of degree strictly larger K, you can just pick that vertex, include it in the solution, so reduce K by one, and get rid of all those edges that are now covered.

6:35 >> [snorts] >> And you can even do this um when you have several such uh if they're particularly if they're independent, but even if not uh Yes, you still have to cover all their edges. So, um unless they they share a lot of edges or the degree is just K + 1, then maybe need to be a bit careful.

6:59 So, that's the kind of pre-processing that we're looking at. And we'll see that this one is actually enough to get the size of the graph all the way down to a function of the parameter only, of K only.

7:12 Formally, what we're looking for is called a kernelization. So, we have a parameterized problem. Um we have a function that gives us uh from some instance to another instance with um the parameter of the new instance being Where is K prime used? Hm. Okay. Well, first of all, uh a kernelization is not allowed to change the yes-no status. A feasible instance turns into an feasible instance and vice versa.

7:58 Uh we have to be able to do this in poly time, the pre-processing. Think of this kernelization. That's that's your pre-processing. >> Okay. Um yes, a special case of kind of pre-processing with an extra rule, namely the size of the output is bounded by a function of um just the parameter, not the input size.

8:28 Okay. Um I wonder why they find K prime if we don't use it. I think we don't need it because if the input size is already so small, uh the parameter of the new problem uh even if it's even if it goes up, I think we don't care. Because we can bound some I think we may not not need this one. Uh we call this this G the size of the kernel. And in principle, this is again allowed to be an arbitrary function of the parameter, [snorts] but of course, we're also interested in small kernels because then they uh allow a more efficient solution.

9:22 Okay. Uh the kernel we've just seen repeatedly apply these two rules. That's that's called uh Buss's kernel after a uh researcher named Buss. Um So, if you have a degree strictly larger K vertex, you know to take that one, remove its edges. And if you have degree zero or one vertices, you also know what to do. This one just drop, this one take the other endpoint. Mentions that these these rules together, um if you just apply them as long as they are applicable, they already give you um a kernelization, and it has size K squared.

10:07 So, let's see why. Um the trick is to say um I don't care I arrived there. At some point, I know that the two rules are not applicable. Well, what does that teach me? Um, it tells me that the degrees of all vertices are between two and K. Any larger ones would have been eaten by this, and any smaller ones would have been eaten by this. The K that I'm I'm working with at the end might be a smaller K than what I started with, but um, this is an upper bound that's still true.

10:46 Now, in the resulting graph, um, we have only vertices of rather small degree at most K. And I'm going to pick at most K of these vertices. So, in the best size, I can cover K squared edges with that. Right? I can pick K vertices, even if they're disjoint, they're going to each just have at most K edges. So, if I have more than that many edges left, if the resulting number of edges in the graph is more than that, I can immediately say, "Nah, not going to work."

11:19 And so, um, formally, a kernelization has to be a pre-processing that returns another instance of vertex cover. I can't just say no in your face, but I can give you some obviously unsolvable tiny instance. For example, give me the complete graph on K plus one vertices, and the same parameter K, that just doesn't work, right? But it it has size bounded in terms of K as well. Whereas, the original graph here was big. And the other case is even easier because then we're already small, and we just leave the graph as is, and say, "Here's your kernel." I still don't know if this is solvable, okay? All I used here is certainly with K vertices of degree at most K, I cannot cover more than K squared edges. Whether I can, uh, cover the edges in your graph like this is not clear because this only works if the edges are nicely disjoint. This is essentially this means I have disjoint stars.

12:21 My graph looks exactly like this and every vertex has degree K. That may be the case, but it may also not be the case. And it turns out this is still hard to check.

12:35 But the output is now a graph of size at most K squared 2 2K squared. And um that is what the kernelization claims and it has the same yes no status. It's It has a vertex cover of size at most at most K if and only if the original graph had one.

13:04 Now let's also come back to what I claimed earlier. These two notions are really the same. Having a fixed parameter tractable algorithm an algorithm with this running time f of K times a polynomial in n or having a kernelization that gives me an input of only size bounded in terms of the parameter. If you have the one if you have one then you have the other. So let's prove this. So here I mean formally again it's a Yeah all of these L's should be should be pi uh need to be more consistent with the notation. I have a parameterized problem it's fixed parameter tractable if and only if there is a kernelization for the problem with respect to this parameter.

13:53 Let's first do the direction. Suppose I have a kernelization. So some function K for my problem pi kappa. Then what does that mean? Well, uh in my language this pi is language yes instance. I don't care about the sigma.

14:44 And we have X's in yes in the yes instances if and only if this kappa is in the yes instances. And what was kernelization on top of that?

15:00 The size of the resulting kernel is some fun function G of the parameter of X. And okay, this looks like it's two X's. The first is a kappa. And this is an X. Because it's so hard to write this legibly I usually just write K immediately for the parameter of the input.

15:29 Okay. Um we also know because this is a computable problem not otherwise interested in it at all. So there is um some deciding some some Turing machine that can decide if an input is in in this language in some running time which we don't really know.

16:07 Some running time of the input size. All we assume is it's computable. And again without loss of generality this T is weakly increasing. It's the same same trick we used before.

16:34 Now, uh we have to find an FPT algorithm for this problem. And it will consist of two steps. we're given some some input X in our language in the the superset. Now, we compute the kernel.

17:26 That is that is a polynomial time operation polynomial in the length of X. Um let's call this X prime. And we know that the length of X prime is bounded by some this function G of the original input size.

17:59 And now we'll just run this arbitrary Turing machine that we're given here on on this kernelized on this kernel instance. Now, the time for that we we don't really know anything about apart from this upper bound T.

18:25 But because this is now bounded by uh Sorry, this G of the parameter K. That's important. Because this this now is a function again by weekly increasing we can upper bound we can insert this upper bound for the size of X prime. And we get an upper bound for the running time of the second step. That is some horrendous function of K, but it's only a function of K.

19:04 for the two steps is the sum of the times of the two steps. I'm spelling this out here. It's f of K plus n to the c for some constant.

19:37 And so, you see here um we can construct even here a slightly stronger algorithm where this is not a multiplication, but an addition. Okay, that's the one direction. If if I have a kernelization, I can turn any decider into an FPT algorithm.

20:01 Let's do the other direction as well. If I have an FPT algorithm, this may be a bit more interesting. How am I supposed to turn that into some pre-processing algorithm if all I know about the algorithm is its running time?

20:24 So, given an FPT algorithm A for this kernelized parameterized problem, and say it has running time at most f of k times n to the c, some function of this form is guaranteed. Now, what do we do? We have almost nothing at our disposal. So, I mean, we're going to have to run this algorithm. We don't have anything else we can do. This general uh theory of of of computability, I guess, tells you in general you can't do much with a black box machine to inspect it. So, we're going to run this algorithm, but we can't keep it running for good because the kernelization only has polynomial time to produce a kernel. So, we'll shortcut it after a certain number of steps.

21:28 We simulate this for n to the c plus one steps. That is clearly a polynomial in n. So, that satisfies the polytime uh requirement for a kernelization. Now, A may not have been finished after this. So, there's two options. If A terminates before, then we know the answer because A computed it, right? Then um we're still required to produce a kernel, but uh it should be satisfiable. So, we can just output any trivial yes instance for the problem.

22:42 I think this is using some mild assumption of the sort that the problem has some yes instance. But, I mean, it's not a very interesting decision problem otherwise. >> [snorts] >> And if the answer that came out was no, we'll output a little no instance.

23:15 And that's our pre-processing, which is not not so insightful because these trivial instances have nothing to do with the original input. Okay. Uh The other option, if A doesn't terminate, that's the clever trick. Well, then we know that the time that this machine took apparently exceeds our budget that we gave it. Otherwise, it would have been finished. And uh from that, you see by canceling the into the C, that N is smaller than the function a function a function, but actually the function of the parameter. So, it already is a kernel.

24:20 End of proof. That thing, of course, has the same yes no status as the original input because it is the original input, and it has a size bounded in terms of the parameter only. Now, um um I think this is at the same time beautiful and a bit sobering or disappointing. It's beautiful because it tells us this slightly wonky notion of FPT algorithm where it's maybe not clear should it be f of k times n to the c or plus or maybe we allow squared or you know, there's a bit of a freedom in this uh run time bound. It's equivalent with this maybe more natural notion of some pre-processing in poly time turns this thing into a size that's bounded in term in terms of the parameter only. And you see how any FPT algorithm by using this this this theorem back and forth you can turn into one that has a plus in between.

25:19 So, the multiplication was to make it a bit more convenient to argue that algorithms are in FPT. You don't have to worry about splitting this properly up, but you can always by making f bigger.

25:37 Okay. Uh on the other hand, it's a bit, yeah, uh disappointing because it's telling us in the general case the pre-processing is rather uninspiring. Either the original input is left unchanged or it's just thrown away and replaced by something entirely different altogether. >> [laughter] >> Such is life. So, let's see a more positive example to finish off here. Um As another Well, we've seen the uh buses kernel, I guess, for vertex covers also proper one. Let's see a a second good example. Um we'll look at this max sat problem again. So, uh uh we have some some formula of >> Do I need the variables? Maybe not. Um I'm trying to get a to a kernel of this size K squared, so rather small if you want. Um and the question was can we satisfy K clauses?

27:12 With some assignment. That's that's the max sat problem and parametrized in terms of K. make an assumption here that every variable occurs uh at most once in a clause.

27:49 Turned positively, if not then if a clause contains X and not X if that's part of a clause, then just dump that clause, right? It's always going to be satisfied.

28:22 Okay. Uh let's also say N is the total size of all clauses at total number of literals, say. >> So to count as a proper kernelization, this is the thing we should count. The number of literals should be small. We also have the number of clauses M. But this is really N is a is a bound for the actual encoding size. Um if M is small, there could still be very long clauses for some reason. So it it's that's not good enough.

29:20 Just to state that as a goal. Now um We could do this by a case distinction. The first option is that our parameter is rather small compared to the number of clauses that we have. And uh maybe you can think about this for a second. What would you do? If I tell you here's a formula over over 17 clauses.

29:50 Can you satisfy eight or more? And eight importantly is less than um 17 half. And that will need a case two further down where this is uh not satisfied.

30:24 Well um if you have this, you just output yes or you output true as a kind of formula. Because this is always going to work. And the reason is pick any assignment. A random one if you like.

30:59 Now these two options, it will satisfy some number of formulas. Satisfied. Now if L is already larger than K, then we're happy, right? Then we have found a satisfying assignment that satisfies as many as we wanted. Otherwise, our L is strictly less than K, which is less or equal M over two rounded down. And these are integers, okay? So if L is strictly less than this K, it's also going to be strictly less than M M over two. Without the rounding.

32:08 And so if you negate all the variables, think about what a a clause needs to be false. It needs every single literal to be false. Now if you negate all the variables, they'll be true. One of them at least and you know, right? Just all of them. So all the clauses that were false before will now be true.

32:48 And so, that's the number of clauses that are satisfied. And what do we know about this m minus l? I think we don't even need this conclusion here. I can just bound l uh greater equal Yeah, that's that's more than m two m over two rounded down because this is if anything, it's slightly larger than half or it's exactly half. Uh depending on you can take case the do a case distinction for odd and even.

33:43 Uh but then you need in all cases, this is at at me at least l k. Too many Too many variables. And so, either some arbitrary assignment satisfies at least k or the negation does. It's never too hard to satisfy half of the clauses. That's what this says uh long story short. This was in a way the easy case. Um the reason we split this off is because then the other case that k is large respect compared to the number of clauses this tells us something I mean, first of all uh again >> This tells us something about the number of clauses in turn. Then these cannot be all that large.

35:04 Which means we're already small in some sense, but they could all be long. So N could still be small. I could still be large.

35:24 Let's just say this is a a comment. So let's just split the clauses in long and short. FL is the set of clauses C that have more than K variables. Greater equal K. And the literals. That's same thing. And the short clauses are the others.

36:13 We need another little case distinction depending on how many of these we have. Let's say capital L is the number of these large clauses.

36:23 If I have uh Let's say this is 2A. If I have many of these large clauses then it's enough to satisfy only some of these large clauses. And because they're all very long longer than K.

36:47 You can intuitively pick disjoint positions to make them true. If you just write them uh below each other and say, "I'm going to satisfy this literal and this and this." If they're all sorted, you This is a bit um you should think of this as you have the variables listed as columns and then the rows are the clauses and you put a you put a dot if the variable occurs in that literal. You will find um so that all the long clauses are satisfied.

37:50 It's a bit pigeonhole principle. Uh and the last case is to be that the number of long clauses is small. So, in this case, obviously it's a yes instance, right? So, you return true as a the obvious the primitive yes instance. And in this other case you can in a way still use the same argument from these large clauses, you can you can satisfy all of them by picking some variables somewhere. So, what you what you are uh left with is only the short clauses. But with a smaller parameter now, you can guarantee that these capital L large clauses are always going to be satisfiable because this these other clauses only need to pick a few number of variables.

39:16 >> Even only if the original problem is a yes instance. And maybe I will finish that proof next time. So this uh This part Let's say is is a claim. The proof is not too hard, but I don't want to completely skip it.