Video 4-2: Fixed Parameter Tractability

0:02 In the next section, I want to formally introduce what we mean by this notion of fixed parameter tractability. So, an algorithm that is maybe in the worst case exponential or at least exponential is the best we know uh subject to P not equals NP. Uh but if you look at a second kind of hardness criterion, a parameter of the problem, then it becomes more solvable. What do we mean by that? Um different options from different problems where there is a specific algorithm with a running time. If we want to solve satisfiability, where the parameter is the number of variables, then we have an easy brute force 2 to the K times linear in the formula size algorithm that just tries all assignments. So, it's kind of a a very uninteresting algorithm, but you could say in terms of the running time if K is small, this is actually fine, right? Um the next step up was when you have uh the the canonical parametrization of the clique problem. So, we're looking for cliques in a graph of a certain size, and this threshold that we give is our parameter.

1:10 So, the larger the cliques we ask, the more tricky the problems get to solve. That's the assumption under this uh parametrization. Well, we can just go through all size K subsets of vertices and check if they form a clique. That check is indeed here cheap because it's just local to the subgraph. So, you could say this is in a way even better than this um next one because here I have this n to the K as a theta class from the number of candidate subsets. And each just takes K squared to check. If K is small, that's faster than linear in the graph size, whereas for vertex cover, the stupid brute force algorithm would take n [snorts] to the K times m. Right, I'm picking a uh any um going through all possible subsets of K vertices and to check that they are vertex cover, I have to go through all the edges. If the degree of the vertices is is large, then maybe there's a lot of edges to check.

2:09 Okay. And I mean, notwithstanding that you can maybe devise some clever data structure to speed this up. Let's not go into this. The The question is rather what kinds of running times um could we get? And even worse was this graph coloring problem where if we stupidly check all possible solutions, then it's K to the N uh even different candidates to check, and then each again needs to consider the graph to see if every edge is not monochromatic.

2:42 Uh let's have a um a look a bit at what happens when um we want this time to be polynomial. What size can this parameter K take?

3:02 What's the largest K I can put here so that the result is still a polynomial? Yep. Yep. I can even have uh some constant log N. That's also fine, right? Uh as C times log base 2 of N is precisely N to the C then. Uh so I can I can tolerate up to logarithmic in the parameter, and it's still polynomial, but not more. Then it comes to quasi-polynomial. If you have log squared or so, or poly log. Um for the same question here, And that's maybe your first indication why um what I said last time already, we want to put the line here. Let me maybe make this a bit less mm Let's make it a bit more uh indicate that there's that there's potentially ways to go between the two worlds. But um that's a certainly a difference where they can only have constant parameters or at least logarithmically growing. Uh this one is the same, right? Um but there's another uh growth here with the parameter or just an n with the input size, doesn't make a difference.

4:40 And um now here, this is even worse. Here I can at least when the parameter is constant get a polynomial time algorithm. Um we'll call this So, this up here will be will be called an FPT problem, fixed parameter tractable. Whereas this middle ground where a constant parameter is is polynomial time but not more, this will essentially correspond to another class XP. So, uh I don't know what the X really stands for. It's poly time if you bound the parameter by a constant. This problem down here, this is in a way much much worse. So, let me draw here the line as well, but this is a solid line for for real. Uh even a constant k makes this algorithm exponential unless k is one. So, I can really just say uh k = 1 would be the only thing for this specific algorithm. Now, this is just the brute force method. Maybe there's a better way to solve this coloring problem.

5:41 Certainly better than than just doing this. However, it turns out that even a three coloring is NP-hard as you may know. Uh so, even setting the parameter to a constant makes the problem NP-hard. So, here there's there's literally no hope to have something that depends on the parameter in any interesting way. Uh I guess I mean it's completely solved, right? K equals 1 is boring. The graph cannot have edges. Uh how about K equals 2?

6:29 Because it's a well-known problem that I'm sure you've heard of. A graph is two-colorable if it's bipartite. And uh that you can check with some reversal.

6:49 Uh the the beauty of I mean bipartite graphs have many many useful properties. They are for example characterized by having no odd cycles, which is something you can check with a depth-first search or uh you can essentially just in a in a breadth-first search color the vertices by layers. And if that doesn't work, then you're just screwed and there's no way.

7:14 Some problems are like this bottom one. There's there's nothing to be learned. They're um for some very small cases are easy and then they jump to NP-hard with nothing in between. So, we clearly want one of these other ones and the the definition that I guess makes some sense from a practical perspective, but also really just makes the theory a bit more round is is this one. So, again after going through all the the setup, what it really comes down to is you want um a running time that depends polynomially in the input size or in the encoding length of the input and with an arbitrary function in the parameter. And then these two things are multiplied.

8:01 Um F here is really uh unconstrained. It needs to be a computable function. But Ackermann is computable. This is a extremely ridiculously small requirement. And you'll see it's only kind of to allow simulations. You want to be able to say I have a Turing machine with an a known upper bound for the running time, then I want to be able to simulate it. For that, I need to compute how many steps I should simulate. That's where this comes from. So, think of this as kind of a technicality. It's an unrestricted function f really. It could be a tower of of Potent I mean, Ackermann is the worst I can think of, but it's a bit hard to write down. It could be k to the k to the k to the k k times, or think of um any of these any of these ridiculous functions. What's that? Busy beaver functions, yeah. Uh computable is not much of a restriction.

8:58 Of course, the hope is that f is not that ridiculous. But we'll certainly have to deal with a super polynomial f. Otherwise, the overall thing would be polynomial. So, in a way that the natural smallest functions, I guess, are just exponentials.

9:21 Okay. So, the the key notion here is is a an FPT algorithm, a fixed parameter tractable algorithm. If it has such a runtime. And for the problems that admit such an algorithm, capital in all caps FPT is the class of problems that belong there. You can say this is the uh the equivalent of the class P. Uh except that now it it has parameterized problems.

9:51 So far so good? Uh if you are thinking about this times, it'll turn out that this is not so consequential. You can essentially put a plus here. If you're um in the seminar, then you may have seen that people also studied what happens to the theory if the polynomial needs to be degree one, linear is only allowed. That's a an interesting um re- restriction. Uh we're not going to look at that here, though.

10:25 Let's see some example. Does this even exist? Do we have any problems where this is true? Well, we've seen this one before. Um I would essentially just say proof see above. Uh I I have the proof typed up. Well, yeah. Uh the proof is the brute force algorithm just is FPT in this case. If you pick as parameter the number of variables, uh a bit more formally speaking, here is this code that implements this uh brute force method. You give a you're given a formula over K variables. K, the parameter, will always be denoted by K. Here's the number of variables. If there is no variable, well, then the formula is a constant. And if there is some variable, then try to go set the first variable to one of the two values, true and false. And uh I'm sure you can come up with a more concise way to write this. Yeah, but uh here it's just written as a loop, so you take your formula, then you replace it, you replace X1 with this fixed value, and that's the notation from logic for substitutions.

11:42 But really you just go through the parse tree of the formula, replace your X by a constant value, and maybe you evaluate subtrees that are constant now straight away. All of this can be done in linear time, and then you call the brute force algorithm with this formula in the restricted value variable set. The crucial point is here the number of variables goes down by one. And uh so um this algorithm will will build a binary tree for the variables. For each one, there's one layer. Here, I have X1, and it could be true or false.

12:26 Now, let's just put zero and one. We're computer scientists, come on. And then here we have X2, and in each case for X1, I have the two options. And so on. So, this tree clearly has has height at most K for the variables.

12:47 That's all we'll we'll only get the worst-case running time 2 to the K for the total number of nodes in this tree, and each spends linear time on basically the substitution. And maybe the satisfiability check. >> [snorts] >> So, great. We have a problem that is in this class FPT. Which I I was trying to sell FPT as the equivalent of of P, but I'm telling you SAT is in this easy class is a bit of a problem, right? So, of course, all of these statements in the whole chapter only make as much sense as the parameter is small. And if you cannot guarantee or if if the inputs you're looking at don't necessarily have small parameters, then it doesn't help you much. We will we will see for the rest of the chapter some more uh more insightful algorithm design techniques than just writing out the brute-force method and observing that it fulfills our definition that we bent around it.

13:50 Uh before we get there, though, um let me point out that this this another nitpick in kind of the the definition. You can really pick bad parameters. That's all this is in a way saying. Uh so, the statement here is um if you have a a parametrization that is lower or bounded by some function that's always just increasing. It's only weakly increasing, but uh it eventually goes to infinity as a as a function of the input size. Okay? So, this is saying your parameter is growing when the input is growing. Then even if the problem the underlying language is only decidable, the problem is a parameterized fixed parameter tractable problem for a completely uninteresting reason. So, again, the the subtext here is if you pick a stupid parameter, then all the notions become a bit meaningless, so you have to be careful not to do that. And exercise a bit the definitions, let's let's do this proof. So, um weakly increasing is my way of not using double negation.

15:05 The mathematician style would be non-decreasing, but I prefer to say what I mean instead of not saying what I don't mean. So, weakly increasing means less or equal when when you make the parameter larger. And unbounded means for any value you want to reach, any threshold T, there is some N where you cross it.

15:29 Okay. Um I guess I would have wanted this to be my language Y again for the yes instances. So, if that is a decidable language, there is some algorithm that eventually decides for any input whether it's part of this language, whether it's a yes instance or no. So, there will be some computable function T that just gives an upper bound on the time that this machine takes. We know nothing about this other than that it's computable because, well, after all, this machine kind of computes it.

16:06 Now, this is only an upper bound for the running time, so I can make that upper bound even bigger, and it remains true as long as it's still computable, so I can make it weakly increasing and at least as big as its argument.

16:25 Now, the idea is um that we uh pick this this FPTF the function of the parameter so that to completely hide the running time of this arbitrary Turing machine inside it. And this is possible because our parameter is is so large. So, the the definition that works here is to pick this function uh H um which is the largest input um largest input size where our our function G of N this uh growing function from the from the assumption is at most K.

17:20 uh could look as follows. If you try to plot this this function uh G of N G is somehow weakly increasing, so it might be constant for a while, it might jump, can do many things. Uh but it's also eventually reaching every threshold, so if you want some specific point, there will be at some point there will be some some value. Sorry, the other way around. Uh for any value you pick on the Y axis, there will be some some time where it's crossed.

18:31 >> And so, if this is my my value g prime, then I want to know with my function f when is the first time that I cross this? So, this here would be this function h of g prime.

18:43 G prime is not the derivative. This is just a number. Okay, let's say g bar. I just want to distinguish it from from the function g. The point is this is some value that the function g will eventually go over. And when does it do that? Well, at this position h of g bar. Okay?

19:04 Now, let's um observe a few properties of this function that we've defined. Uh first of all, it's well-defined because um this eventually will have uh a well-defined maximum. Because g is is increasing and unbounded, so eventually it will cross above k and then I have a finite prefix that I'm picking the maximum from. Second, uh follows essentially from that. H is weakly increasing. If I make my threshold bigger, think about this picture again. If I make my g bar bigger, then I have to wait for a bit longer potentially. Never shorter before I can uh where I can draw my my red line down. Um because g is a computable function by assumption, h is also computable by essentially just computing this maximum from the bottom. And now the the observation we really need, if you take h and insert g of n, then the result is at least n. Why is that? Uh well, if I if you take any n and you take the actual value for g of n and you plug that in, then you're asking when is is uh g of n bigger than g of n? Well, at least at g of n.

20:29 The the threshold here this k is is the same function, so certainly at this point you are um you are uh still below less or equal that function. So, you go above yourself after yourself or I don't know.

20:48 Um it's just a from definition if you insert g of n here. So, this is always larger than n. All of this seems maybe a bit cryptic. Why do we need that? Um we can now do the following little trick. We simulate our machine A, that's the one that computes that decides our language, the language by we started with. And x is some um potential word in this language. The size of x is n and its parameter, that's the parameter of this problem, is k. Now, we know that this is also by assumption here. The parameter is larger than g of the length of x. So, all I've done here is just collect the assumptions. Then um if we just keep A running, this arbitrary Turing machine that decides the language, it'll take some time upper bounded by t of n, definition of t. Now, I'm inserting n inside the parameter because t is weakly increasing, I can do that.

21:52 I only make the value larger. And now I'm using that k is larger than g of n, so now I'm using that t is increasing and h is increasing. And I can upper bound this by t of h of k. And that now is a function that only depends on k, so it's some f of k. We just define it to be this thing. And you see how of course, how useless in general this is as a bound because t was already arbitrary. And now we're on top of that inserting some super linear function is not going to be well useful. Formally it's true the running time of this of this algorithm A happens to be an FPT algorithm this is f of k. Um you don't even need the polynomial.

22:49 Long story short if you make some maybe innocently looking assumptions that the parameters are always increasing then you cannot have any interesting parameter. You need to have parameters that can also go down if you make the input bigger. Okay.

23:15 It's somewhat of an obvious statement that we offer that we have this for most of the interesting parameters that you think about. If you have a say a graph and this threshold for a vertex cover of course you can make the graph bigger and make the threshold smaller like why not? Um to the separate parts of the input.

23:39 Okay, back to sensible choices. Um just a a long caveat that FPT is not in and of itself useful. Only when we have sensible parameter so it's time to see some some useful examples.