Video 4-3: Problem kernels

0:02 In this subsection, we'll look at problem kernels. A well overloaded term um but I'll I'll make precise what we mean by this in this context. And that's a um an entirely different way to design um FPT algorithms. You can think of it as a as a reduction rule. Uh I'll have some simple examples soon. think of any um simple easy wins um what to do to your input to make some some parts that certainly are not helpful go away. And so the goal is not to change the outcome if we're thinking about a decision problem. It should not affect whether it's a yes or no instance, but you're allowed to modify the instance and ideally make it smaller. And you should do this efficiently. That's the idea. Uh so a trivial example if we're back to the satisfiability problem and we have a conjunctive normal form that for some reason contains a clause with a single literal because we're taking the end of all the clauses. If there's a literal that just contains x that means x has to be set to true or if it's not x to false. There's no choice actually. So a simple reduction rule would just do exactly that. Okay, not exactly exciting because uh most formulas won't contain any such uh such extraneous clauses, but if if they do, it's a valid reduction rule. It certainly doesn't change um what the uh the truth value is. Now, uh, this sounds super super un unhelpful or boring and less powerful than anything.

1:48 It's actually a special case of I guess the most uh effective way to solve satisfiability in practice. Um, maybe this is a remark at this point as a digression. Um, it's not part of this module. Um but even though satisfiability is NP hard is actually very tractable for many practical applications to reduce a problem to a large propositional logic formula and call a blackbox SAT solver to solve it even if it has thousands of variables and they certainly don't do the exhaustive search that we looked at before two to a thousand would never ever finish. um they use some clever uh uristics and based on this uh resolution calculus which really is is um is not more than that. If you have two clauses that have some literals but they also have uh they overlap in one variable and they use it in the opposite way. Then uh instead of those uh literal you can you can add a new literal um which takes uh all the parts without X because in a way uh these two clauses together mean either X is true or false. So at least in one of them you'll need some of the other literals to become true. So you can add more clauses to your formula this way. And again this sounds maybe not super powerful but if you combine this with clever uristics of how to choose these that's exactly how practical ST solvers work.

3:27 Okay, that's just a side remark. Um, I'm not claiming this is an FPT algorithm in a formal sense. Let's look at a different example uh where this is a bit easier to make the case. Back to vertex cover. If your vertex if your graph happens to have vertices of degree zero, they don't contribute to anything. You just delete them. There's no edges that they would cover. And if they have vertices of degree one, right, then there's some part in the graph and this this vertex is just dangling off here. This edge, it's single edge would just as well be covered by the other end point. So just get rid of this guy. It's not going to ever be part of an optimal vertex cover. Yeah. Okay. I'll I'll retract that statement. But uh there's always an optimal vertex cover without that vertex.

4:25 This rule again doesn't look very powerful because many graphs won't have too many uh degree zero and one vertices. But thinking along these lines will actually lead to something more interesting.

4:44 The goal here will be I mean you you can define these simple rules uh forever but the goal is to have rules where you can prove that they leave the instance much reduced namely so much so that it's only bounded in terms of the parameter. That's what we uh what we're really after. Uh so we'll uh I'll often say pre-processing is just anything you do something to the input before you get going. Um, what we're after in this in this chapter for a problem kernel is something more specific. Okay, let's have a look at a a more refined version of this vertex cover rule. Uh, and this one's a bit more clever. So, we're given u an instance to this parameterized problem graph and a and a threshold k. Now, suppose the graph contains uh a degree greater than kvertex. So vertex with more than strictly more than K neighbors. If I'm only looking at vertex covers of size up to K, there's no way I'm going to include more than K neighbors of this single vertex. So I have to choose the highderee vertex. There's no other option. Any vertex cover will have to use that one if it's supposed to stay below K vertices.

6:01 So, uh, I'm I might as well include this vertex, get rid of all its edges, and make K1 smaller for the remaining graph. Okay. Laptop decided to freeze. Uh, you can think about the next point. And um you can you can apply this rule simultaneously for all vertices. You don't have to apply it one by one. You can in one shot get rid of all the vertices of of degree larger than K because the reasoning will be the same for all of these. Neither of them can include all the neighbors. So you have to use all those vertices.

6:58 As always with these rules, uh we'll think of we'll think of them as uh uh doing one step, but we'll apply the rule as long as it applies. So as soon as long as you find vertices of degree greater K, you'll apply the rule to get rid of them. The thing why this can uh cascade is that you're also making K smaller as you're going. So more vertices might qualify to be a high degree. Okay. Woken up again. Good.

7:48 So uh I wanted to draw this highderee vertex but maybe by now it's a kind of clear. Let me just leave it with this. Okay. So this is more promising maybe uh just because it it seems to do something more interesting and if k is not too big this has the potential of making the graph really small. Let's first define uh what we want formally. So um a kernelization is is talking about a parameterized problem as always and a kernelization takes one input and transforms it into another one. Uh and it also transforms the parameter. So there's a um a mapping a new parameter if you want um I mean the the I guess that's not right. Uh the kernel the parameterization stays the same uh but the the result of the kernelization will have a smaller parameter. Okay. So what what are the conditions? First of all, if the input is a yes instance, then it's supposed to stay a yes instance after the kernelization and vice versa. Second, this kernelization should be efficiently computable. And third, that's the important part, the size of the output must be bounded by some function of the original parameter. And uh that means we're actually doing something more than just a general pre-processing. we're really producing a kernel which is uh the hard part of the problem subject to uh the parameter k that uh decides the problem and we get rid of all the uh extraneous uh parts of the problem. Okay. Um we call this this x prime a kernel and this mapping capital k a kernelization and the function g is is often called the size of the kernel. You can already see the game that you want to minimize this size. So let's convince ourselves that this uh this reduction we've seen before uh reducing the highderee vertices already gives us a kernelization for vertex cover and we can even say something about the the size of the resulting kernel. The uh what I mean by this is that we repeatedly applied a rule. This is important. Um so when we do this after we've done this uh I guess we also need to get so we need to combine it uh buses reduction really is um buses redu rule for highderee vertices together with this simple rule from before the 01 degree rule right so uh I'm I'm removing isolated vertices I'm removing leaves vertices of degree 1 and I'm applying this highderee removal rule whenever possible but uh when none of these rules is applicable anymore then I'm left with a graph where all the vertices have degrees between two and k okay it'll probably be smaller than K this is the original K of the input but that's that's say a worst case guarantee. Now this means um whatever the vertex cover looks like in the resulting graph if this was a yes instance it can only contain k vertices and so uh because these are bounded in degree I can only cover k squared edges with k vertices in this resulting graph which also means if I have more than than k squ edges if my number of edges m is larger larger than this, there's no way I'm going to make a vertex cover with K vertices. So I can output as result of my kernelization a trivial no instance. So if you want to be specific, you can say uh I'm just forgetting about the old graph and I'm constructing a complete graph on k + one vertices with the same parameter k and then uh that's a no instance. uh and otherwise if my number of edges is at most k well then both the the number of vertices is also at most uh k squared because uh I have to put these edges somewhere and I can only put uh I can I have to put uh I have to put the I can at most put k uh edges per vertex. Um so the overall uh input size is bounded by say twice that and so that's our our kernel size. Okay. So here the rules are still pretty simple. Um but by looking at it after you applied them to saturation you already get a a non-trivial result.

13:13 namely that you can reduce any graph to something that's bounded uh by k^ squ. Okay. Now as the last bit here um let me prove that indeed these two design principles what we've seen uh essentially are the same. So whenever some parameterized problem has any fixed parameter algorithm then it also has a kernelization and vice versa. So I could really uh define FPT in terms of having a kernelization. It's the same thing. So there's an if and only if. So we have to prove the the two directions or the two implications. Let's first go back. So we start with a assume I guess it's not an assumption. We uh we assume that there is some way to decide the language.

15:07 So, but it might not be clear what the time is. Um as we had it before, we assume this this technical condition that the the running time bound is weakly increasing as you can you can always uh guarantee but it makes the proof easier. So now we have two cases uh or two steps. um we're given some x where we're trying to check if x is in l. So first of all Let's call that x prime that takes polomial time. And also we know that the size of x of x prime is bounded by some function of just the parameter where k is this the parameter of our input always. And then the second step is we run our algorithm A on this kernel. So that decides uh I mean by the correctness of the kernelization the uh answer for X prime is the same as the answer for X. So that will be a correct output. Now the question is how long does it take to run this algorithm A? So far we've only spent polomial time but the time for the second step um we can only give us uh t of x prime.

17:41 Now this is where we assume the weekly increasing which means we can upper bound the outcome by upper bounding inside. And now this is um something that only depends on K. So that's an FPT time so far, right?

18:02 So, together give an algorithm for the kernelized for the the parameterized big O of this this part and a polomial in N. Let me just write poly N for N the input size I guess. So which is already remarkable in itself. If you have a kernelization, you get an FPT algorithm, but you actually get one with a plus between the the two uh parts uh not a multiplicative con condition. And so once we've proven the whole theorem, you can actually always go to an algorithm with this plus because you can take any FPT algorithm with the part that you're see in a minute, convert it to a kernelization and then go back and then you have a running time of this shape. So that proves the uh one direction. Now for the other implication uh we start with an FPT algorithm and we know it has some running time.

20:05 uh that's given by uh a function of the parameter times a polomial and so if that's the case then there will be some exponent C so that this is true okay this is an upper bound for the running time and yeah I guess we can even leave this off uh and claim that that's that's um an upper bound. You can always make the polomial a bit bigger if needed. So the trick now will be to simulate this algorithm A but only for a certain amount of steps. Okay, so so far that's a polomial time because it's bounded by a polomial. Um and now there are two options. Uh if a terminates within that time then it has produced an output and uh If it outputs yes, then we we're supposed to produce a kernelization. So we have to take the input and produce an equivalent instance that's small. So I'm just taking any fixed yes instance of constant size and output that. It's a bit of a stupid kernelization, but it works. It's according to the definition.

22:00 It doesn't. It just ignores the original input because it solved it already. And if the output was no, then we likely likewise output a no instance.

22:29 uh the other option is that a did not finish and we uh stop it after this many steps. So that means this was not enough for this time bound. But if that's the case, then we just divide by n to the c and get that n is less than f of k. Oh, look, the original input size is bounded by something just in terms of the parameter. So it's already a kernel of its own.

23:19 and so in both cases we just spent polomial time polinomial time for simulating a doing trivial stuff here also not doing anything interesting we're just outputting the overall input before again so maybe you feel cheated a bit by this second part because it didn't do anything smart. That's how proofs sometimes go. Uh still the proof established this this slightly non-trivial fact that you could have defined FPT with a plus instead of a multiplication or the part that contains the uh dependence on the parameter which uh I think this is the only uh the only way to prove it that I know. So it's um sometimes non non-trivial things come out of these uh these proofs even if in hindsight they might feel a little less interesting. Okay. So we established that really uh FPT is the same as having a kernelization. Um and another example of kernelization we'll have to wait for next week.