Video 4-1: Parameterized Problems

0:02 In the next unit, we'll look at the generalization of pseudo polinomial time algorithms and the much larger complexity theory attached to it as well. That's called the the fixed parameter algorithms where fixed parameter tractability then the corresponding hardness. Uh this will keep us busy for a bit longer. Um basically I'll I'll show you some of the definitions today and then we'll see some more examples uh later. is a very active area of research which has a a good breadth. You can work on many different problems and on many different parameters and that's bringing us a lot closer to the current current frontier of research there. Um FPT again stands for fixed parameter tractable. I'll tell you what that means. But um first a bit high level what's the what's the idea behind it? Uh when you study hard problems, it often happens that they are not equally hard. Some are still rather tame to solve in practice. My hope is that with this vertex cover game that we played together in the first week, you've experienced this as well that often even these initially scaring looking large instances, you could actually tease out an optimal solution with not too much effort. Now there's of course several things going on. These were they were large for fiddly fingers on a phone but not really large and also they had a certain because of their size um a certain property still that there are somewhat sparse and uh there's not too many hideous things you can you can hide in a small instance. So maybe it doesn't completely generalize but still it seems uh some problems and vertx cover will be one of them. um at least the the hard instances have a certain quality. And so FPT tries to tease out if the input size alone doesn't tell us perfectly if a problem is is easy or hard to solve, maybe there's some additional hidden metric that we can attach to an input, a parameter, so that um that better uh quantifies how hard the problem is than just pure size.

2:20 And we've seen this precisely with max int as the first kind of parameter one could study. And uh you've seen that napsac is is easy if max is bounded by some polomial in tractable polinomial time solvable uh but not in general. And you can then wonder about what kind of running time bounds are suitable uh in this in this connection. Um the goal is now that we're it's up to us to choose a parameter. Now uh in in practice you want something where for the typical instances that you care about this parameter is indeed small even if the input gets big but also where um you can solve the problem efficiently if that parameter is small. That's a bit of um two things that work against each other. will see some examples of non- instances of non of bad examples for parameters. If you pick the right definition, it all becomes a bit boring. So this is a um a bit of a an art to pick the right parameters.

3:31 >> But the the main goal here is to show how it inspires new ideas both of algorithms and of lower bounds. Uh we'll revisit vertex cover in a bit as well. But let's also uh look at another problem that we'll repeatedly look at. Uh that's the the satisfiability problem. And I put this fruitly in the back because uh who knows what Drosophila Milanogaster is.

4:01 Oh, it's the common fruitly. But what's the why is this on an algorithms slide? What what does that mean? Well, in biology, you have these um organisms that are called model organisms that are there's this there's sea elegance, some sort of little worm. Biologists pick some somewhat randomly chosen critter and study it to death. I mean, not okay, no animals necessarily harmed. They study it very thoroughly, much more than maybe that specific organism would would warrant study, but rather as a place to focus attention and show what techniques can do and then from there branch out to other organisms. You see this in many many cases in in biology and it I think it makes a lot of sense and in a way it's um it frees you from arguing all the time why you study that specific problem even though sometimes this is not the most natural to for applications and I feel this is a bit the case for for maxad the thing I want to present so let's let's consider standard satisfiability of conjunctive normal forms formulas what we've done before SAT three set these things. Of course, in general, it's NP complete. We've known that it's the the first problem even to have that property proven. You can do you can pick different parameters and they may or may not make a lot of sense. One is you can pick the number of literals per clause and we've seen that three set already makes the problem np hard nplete.

5:41 So in a way this parameter may not be very interesting. Because also the flip side is true. There's this sharp transition if you have only two literals per clause. A literal with two clauses is kind of an implication in disguise. If you have something like x1 uh x1 or not x2, you know, you can essentially write this as x2 implies x1. Let's maybe write the logic version that that is the same. So if you rewrite all your clauses as implications, they form a directed graph and the thing is overall solvable if and only if it doesn't have a strongly connected component that with with contradictory variables and strongly connected components undergrad stuff you can do in linear time. So two setat is very easy and three set is already the full thing. That's a very bad parameter. It quickly jumps and there's nothing between two and three. Not a good parameter. Many other choices you could make may or may not be better.

6:55 You could pick the number of variables. Then we know there's a trivial algorithm where the exponential blowup is in the kay because you can just dry out all assignments. Now the funny thing here is it doesn't matter how many clauses you have if the number of variables is is restricted. This is kind of a more reasonable parameter. Okay.

7:19 Now it also has a problem in that if you fix the number of variables there's only so many clauses you can sensibly form before they start to repeat or contradict each other necessarily. So it's it's formally true but also um maybe of limited use. The number of clauses, you can think about that one. The number of literals overall then more more fun ones, right? Maybe or maybe these make sense. Who knows? Uh these certainly have been more studied. Uh these are a bit they're essentially n, right? This is not much different. So um this is roughly uh the same as the total size of the formula if you if you wish. And so these are not good parameters because they cannot be small independent of n whereas these potentially can.

8:26 Yeah, I've had that sometimes there were different ways to kind of fix it. If it's that bad, what used to work in the past is quickly go to sleep.

9:01 Uhhuh. So the only thing that's that dies is the preview for you. I've not yet figured out what triggers it. At least that's a rather easy fix and uh somewhat magically it doesn't disrupt the live stream or the recording much. Okay, where we've been. Uh these are some other parameters that people looked at. Um, you can also study this maximization version of SATS. I think it it popped up briefly in unit two. So you could say uh I'm not not as strict. I don't want to satisfy all clauses just the number the maximum number of clauses if the whole thing is maybe not satisfiable. And then you can say my parameter is this optimal value. The number of clauses I want to satisfy or number of clauses clauses I can satisfy.

10:19 All of these could potentially make sense. And the power of this of this theory I guess is that it leaves you this freedom. Uh the downside of the theory is also means you have to choose and you have to be careful what the results mean. Um with the remaining few minutes, let me give you the key definitions and then we can start with proper examples next time. So um uh the full-blown version of a decision problem has the language of allowable instances and the yes instances and the alphabet which I lied away earlier. [snorts] Usually we just assume that's binary if nothing else is written. Then a parameterization of such uh a decision problem is some function a mapping that you can compute in polomial time that gives you for every potential instance a number. That's all. Uh a parameter is something where you can stick a a value to every possible instance. And then the parameterized problem is just a pair of these two. So you have a a decision problem and such a parameterization and those together form formally a parameterized problem. So for example uh what we've just seen satisfiability with the parameter the number of variables you could write as p variables sat that's the notation we'll use. The rest of the problem is as before. You're given some some formula in CNF and uh here not even CNF any any formula goes and the question is is there some satisfying assignment or the clique problem you're given a graph and a number and you ask whether there is a clique of that size you could pick that number the threshold that you're given as the parameter and you could just same you could do full vertex cover. Okay. Now for for each of these you can ask uh is that a sensible parameterization and what kind of algorithms may be possible as running time as function in n and k. Okay.

12:34 Uh the typical case we'll study is an optimization problem. Most of the theory deals with decisions but these decision problems come from a theory from a from a optimization problem. Um so formally um what what I've shown you on the previous slide is enough but to be more convenient we uh use this canonical parameterization when the parameter is the objective value of the optimization problem. So in in long if you have a decision problem that happens to consist every instance happens to consist of some some input string X and a number then the canonical parameterization is just ah take that number as your parameter and this kind of form that you give a a pair of of some encoding and a number this is what we've done for the threshold languages so the decision problems coming from an optimization problem where you say Uh here's an instance and can you find a vertex cover with um uh at most that many vertices?

13:40 Then that's a yes no question. That's the most typical kind of languages where we have this pair of something and a number. So again formally the optimization problem was this uh all this tpple you can look back in unit 2 if you care about the details and the parameterized version with the canonical parameter is just using the threshold language which gives you all these pairs of an instance and a threshold and the parameter is the threshold itself. Okay, this is indeed what we've done here. These two are canonically parameterized problems. So intuitively, maybe vertex cover is hard to solve. But if you always just care about graphs that can be covered with very few vertices, maybe that has a different complexity. So instead of max int, our old parameter from unit 3, we now can specify which one we want. And maybe it's just the size of the output in invertex cover. [snorts] Okay.

14:51 Uh more examples that we've seen and we'll always use this naming convention that P means what comes is some parameterized problem. So a pair of this normal problem and and some function giving you a parameter and then the next thing is if there is something it's the parameter and after that comes the normal problem. That's just a um a concise way to write these things so that uh we can have short statements in the theory section.