Video 5-1: Parameterized reductions

0:03 In the next unit, we'll look at parameterized reductions to show that a problem, a parameterized problem probably doesn't allow a fixed parameter algorithm. And uh this is complementing the previous unit of algorithmic techniques to design FPT algorithms to show that in some cases it seems unlikely that we have uh any fixed parameter algorithms for a given problem. And we've already seen some examples of these problems where in the previous chapter I initially introduced the problems at the beginning but then they never popped up again in any of the techniques. We've talked a lot about vertex cover and some versions of satisfiability and uh uh this closest string problem. But then there were some other graph problems where I was uh suspiciously quiet about. Um and we'll we'll see in this chapter uh why. As I said, it's uh going to be shorter than the previous chapter, but we have to cover a few um more abstract concepts um for reasons that will become clear after the first attempt. Um maybe I'll leave it at this mysterious uh remark.

1:15 The goal would be to prove that a problem is not in the class FPT in which case we shouldn't try finding an algorithm that has a FPT runtime. Clear? Uh but uh so one example that um maybe you've noticed wasn't popping up in the last chapter was was the clique problem parameterized in the the canonical parameterization of the problem. So parameterized by the threshold itself. Uh does a graph have a uh subgraph of size k or does it contain k vertices that are mushially connected? And it seems indeed that no ft algorithm can solve the clique problem. But how would we prove this in particular? Um with the usual problem that uh for the uh maybe not so likely case that P equals NP but at least it's still a possibility. Um we cannot possibly prove such a statement. If P equals to NP then all of the problems that we discussed here all problems in NP are also in P and then of course they're trivially also in FPT because any polomial time algorithm is also a fixed parameter algorithm an FPT algorithm. So the strongest kind of lower bound we could possibly hope for given this uncertainty whether P is equal to NP uh would be something conditional on the assumption that P is not NP. That's the least we need. We'll actually seem to need more. This is uh not going to be sufficient. Um in in another way going back to classic complexity theory this is the standard assumption. You would say things like there is no polomial time algorithm for the clique problem without the parameterization unless P equals NP. Right? Because click is an NP hard problem. We know that that statement is is correct. Either P is completely equal to NP or there is no polomial time algorithm for click. Okay. So more abstractly that's the kind of statements we'll have. Um no algorithm has a certain property uh whatever that will be FPT algorithm in in this case unless some uh hypothesis from complexity theory fails and it could be P not equals NP or it could be a slightly uh um stronger assumptions. In the first part, we'll look at reductions. Namely, uh they were the key tool in uh classic complexity theory to avoid having to talk about things we cannot possibly prove. Um we we said instead let's just relate the hardness of problems to each other. And uh we certainly uh will try the same for for fixed parameter problems or parameterized problems. So can we somehow compare the relative hardness of these problems? Um and the thing is that we need somehow a notion that takes the parameter into account otherwise it's not going to make uh interesting statements. So um to preserve the existence or non-existence of FPT algorithms such a reduction has to keep the parameters small in the produced problem. So you take a parameterized input of of one problem an input and and a parameter and you output via the reduction the input to another problem then that also needs has a parameter and that shouldn't be too big otherwise intuitively you can't make uh statements about FPT algorithms and more precisely um this is a very natural way to um to formalize this you have two parameterized problems. L1 remember this is a language it's a decision problem and kappa is a parameteriz is a parameterization a function taking an instance from uh the strings this talks about so from sigma one star here and it gives you an integer the parameter of this input so we have two such parameterized problems and then an fpt reduction from l1 kapa 1 to l2 kapa 2 is a um an algorithm or a a function a mapping that takes some word in that where this L1 is taken from produces a word that L2 is taken from. So that for all uh inputs to this mapping A we have that X is in language L1 if and only if the output from the mapping is in L2. That's precisely as in polomial time reductions. Then polomial time reductions as the name says had to run in polinomial time. Here we allow FPT time. So the algorithm A that output that that performs this mapping uh can take FPT time. So it could take more time if the parameter is big. Um and now the third part this is the new bit. It has to be parameter preserving. So uh concretely it the parameter of the output has to be bounded by some function of the parameter of the input but not the input size. Right? So this one here does not depend directly on the size of x on the length of x but only on its parameter.

7:20 Okay, if such a mapping exists then we write in analogy to how we had it. We had less or equal P as the notation for a polomial time reduction from L1 to L2. So we write less or equal FPT for such a a parameterized reduction. This is essentially the natural definition if you think about uh this requirement um analogous to how we defined FPT time. So so far no big surprises.

7:58 Okay. Uh let's see some example. Um first of all uh if you just take some classical reductions they may not necessarily be parameter preserving. Um so as an example for this uh let's look at the vertex cover problem and the independent set problem. Uh just to remind you vertex cover well we talked about it a lot. So here you have to um find the smallest subset that covers all the edges. Uh what can I do here? I got to pick one of those two I guess. So I need three, right? I can't possibly do it with two vertices. But vertx cover was find a subset of vertices so that all edges have one end point in the chosen set. An independent set uh let's take the same graph. A maximal independent set is a subset of vertices that are not connected in any way. So what's an maximal independent set in this case? This looks like a good one to pick. Uh maybe this one and this one.

9:15 And I guess I can't do four or can I? It doesn't look like it. Uh I don't know if you see a larger one. A classical reduction um between these problems.

9:40 uh from uh classical complexity theory we can prove that independent set can be polomial time reduced to vertex cover for example with this reduction uh the graph for vertex cover is the same and the parameter is the number of vertices minus k so you're given an instance of the independent set problem I'm just making up some uh arbitrary graph here. No, it's not uh not anything special and some threshold k right so let's say k is equal to five uh can I vertex cover this with five vertices uh oh god okay got to take this got to take this then this looks like a good one then almost everything's covered right just these too. That covers everything. So I I could do it with four. Um I might as well just include another one. Uh I could or or not. Doesn't matter. Now the the thing is if we take this parameter for vertex cover the reduction says we should take the number of vertices which is 1 2 3 4 5 6 7 8 9 minus 5. And then um this this claims there is a vertex cover of five vertices if and only if there's an independent set of four vertices or more. So vertex cover at most five independent set at at least four. And um the trick is to just take the complement. I think I can't count right one two three four ah okay because I didn't let me do uh what I what I did before. So let's add the fifth uh vertex cover vertex. The simple property I'm using here is if the red set is a vertex cover, the complement set of vertices has to be an independent set because if there was any edge uh between those blue vertices, then that blue edge would not be covered by the red vertices. Right?

12:07 And this is an if and only if. Now that's a fine reduction in classic parame uh classic complexity. It also goes the other way around by the same uh same trick. Uh but it doesn't preserve the parameter. If your graph is huge and k is small then um you have a small parameter initially but the output parameter is huge now. So you cannot bound it by just a function of k.

12:52 All that says is you have to work harder if you want an FPT reduction. So in particular this um this does not imply that the parameterized problem P independent set is FPT reducible to Pvertex cover because that uh that preduction is not parameter preserving. It could be there's another one in principle that shows this uh but in this case actually we don't believe it is true. So this this statement probably isn't true.

13:29 Uh let's see another example where things do work. So where the um reduction is parameter preserving um as a boring reduction too but uh as a simple example to make the point we can reduce uh the independent Z problem to the clique problem also in the parameterized sense with an FPT reduction. And again this reduction works both ways. Um and the reduction is simple. Uh I have some graph as input graph. I'm not going to make it too big now. So maybe this is your input graph. And now you ask for an independent set of size I don't know three.

14:20 That should be doable by picking. No, it should not be doable. Okay, it's a no instance. Fair enough. Um, now you're taking uh the complement graph where you add all the edges that are not in the original graph. I guess that gets too messy.

14:55 Um, so the complement graph has this edge and this edge and this edge and this edge. I'm just counting degrees. Uh seems that's all uh the three here belongs on this side. Uh but we actually do the same parameter.

15:24 So now the the thing is if this has let me take a parameter two where it's a yes instance so we can draw it. If we can find an independent set here like these two then uh we can find the two click in the other graph and it's trivially this one um it's not super exciting I guess um because uh with just two vertices it's a single edge but you you get the point an independent set exactly means no edges a click means all edges is if you just take the complement graph, one turns into the other. Uh but we've not modified the parameters. So it's obviously parameter parameter preserving even in a very literal sense. Um the important bit is just that K prime is bounded as a function of K. Certainly true in this case.

16:26 Okay. So this means uh the independent set and click problem are also in the parameterized sense equally hard. Okay.