Video 4-1: Fixed-parameter tractability

0:02 In the next section, we'll talk about the goal. What uh what types of running times or what types of algorithms for these parameterized problems do we see as tractable as efficient and in general this is a bit up for debate. Um I'll present the solution that people have come up with because it has led to a round um a theory around around these problems or makes makes for nice classifications but it's maybe uh asn't the case for for P and NP is not without alternatives or you could debate it a bit. Um let's see some examples of what running times one could possibly uh achieve. So here uh I'm listing some exempl exemplary problems and I'm not trying to invent good algorithms. I'm just listing running times for the the most uh shallow stupid brute force method that just goes through all possible options and checks them one by one. Okay. Uh so don't uh I'm not I'm not claiming that these are the best running times for for any of these problems. uh if I have the uh p variables uh set problem, we'll we'll see this in more detail in a second. Um if I have k variables, the number of assignments is 2 to the k. I can assign each variable to true or false. And then for each of those 2 to the k assignments I have to evaluate the formula which is conceptually I have to replace every variable with its value in the assignment and then I have to simplify the resulting term. You can be uh more or less smart about this simplification. Um but you can do it in linear time if you have the formula parsed and then you can bottom up evaluate it. Uh that's not too hard. So that's one one type of running time. Uh we can get another parameterized problem, the peak click problem that we've seen before. Um if I were to check in a graph whether it has a a click of size k um the simplest thing to try is just go through all elements all subsets of k elements uh k case k case k case k case k case k case k case k case k case k case k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k ver vertices and uh check if all of the k choose two edges between them exist. Uh I might do this if I have the graph given as an adjacy matrix. I might do this in constant time for each edge.

2:39 Um then the total time is number of candidates to check times this this time for each candidate. And n choose k uh a little bit of refresher on combinotaurics. Not that this is super relevant here. is this falling factorial k terms and then we divide by k factorial which is k * k minus one all all the way down to one uh and this is asmtoically equal to um n to the k / k factorial where here this this tilda means if you divide this by this the the ratio uh converges to one. All that we need to know for this is um n choose k roughly grows like n to the k. So it's a polomial if a is if k is constant. Uh but of course if k is allowed to grow then this also grows very quickly. That's another type of running time we could we could get um in a slight variation if we look for vertex covers instead of uh clicks. Uh it's a similar game. The vertex cover is a collection of vertices. So if my uh threshold K means I'm I'm allowed to pick at most K vertices. Then uh I can check all the kvertex subsets and check if they cover all the edges. In this in this case the checking part is slightly more costly than before. Here the checking part only depended on K. Here it's the entire graph not just the subset but I get a very similar runtime in the end.

4:38 Uh and last um I could have the the coloring problem where I'm trying to assign colors to vertices and the question is can I do it with k colors where k again is the parameter and here the the brute force method of checking all possible colorings of vertices. Now this is this is incredibly wasteful because there's lots of symmetry but really you can't do that much better unless you try to be really smart. The possible number of candidates to check is every possible color for every vertex. So you have k to the n possible different colorings. Um checking them is not so hard. But of course this grows even for for small k this grows very quickly. And so one one way to look at these is uh to think about what values of k would make the resulting algorithm polomial time. And so if you look at this part maybe let's do maybe let's go bottom up it's easier. Uh this problem this running time really is is a is polomial only when k is one really right.

6:03 Uh even for k equals 2 um that time would be exponential. Now the question whether a graph is too colorable is actually in poly time because that's the question whether the part graph is bipartite but that's a different story. Um and indeed we know for k= 3 the problem is np times are a bit less uh less problematic. At least any constant K would still give uh polomial time. So we could debate whether these are good or not. Um now if K is is a large constant that's very questionable but this is certainly polomial. Uh and the last bit here we can't make K linear in N for sure but we could tolerate for example logarithmic in N then it's still polomial. So certainly better than than this case.

7:23 Um you can make it slightly bigger. I guess uh log n* log log n it's also still uh still polomial. Uh you cannot allow log squar n then it would be n to the log n that's not polomial anymore. Okay. Um the exact boundary is not my point here. The question is which of these running times should we uh should we accept as good? Maybe a priory is not even uh it's even not even so clear. Um but you'll see the definition is essentially drawing the line between those two. The top is okay and the uh bottom three we don't like. So let me draw this in here. But there's a twist to the definition. So formally um uh what we like a fixed parameter tractable algorithm. So an algorithm that we consider efficient for a parameterized problem um is defined as follows. We have a a parameterization and we have an algorithm that works on this alphabet.

8:42 Now the the algorithm doesn't need to know the parameterization. We're just analyzing it using that. Um and we say the algorithm is is fixed parameter tractable if it has this running time. I can somehow split the running time into a product of some part that only depends on K and some part that is polomial.

9:21 And crucially that's also the only restriction we put there. Uh this function of the parameter is allowed to grow as as quickly as as it can get. Uh technically the restriction that is that it has to be a computable function but it could be uh an Acurman function or anything. Uh it could be completely crazy. Uh and in a way that's that's one thing to watch out for. If that function grows um beyond beyond any reasonable bounds maybe the algorithm isn't as useful.

9:58 But that's the definition that led to the uh led to the round theory and um in many practical examples that we'll see f is reasonable. Okay. So again uh polomial in the overall input size just as before multiplied by some part that only depends on the parameter but is allowed to grow as quickly as possible as a function of k as we like.

10:30 Okay. Then um there's a complexity class that goes alongside with this definition. The class FPT contains all the parameterized problems for which there is an FPT algorithm. Hopefully not surprising. um you should think of FPT maybe think of the P here to play the role of P of of efficient algorithms but with this caveat that uh because this parameter needs to be chosen and the function of the parameter can be arbitrary it doesn't always mean polomial time okay uh I probably gave this away I wanted to ask continue without much further [Music] um Asia essentially answer this question using the knowledge we've covered so far. Uh not using any uh more sophisticated algorithms that might exist.

12:20 So, show results is a really clear picture. Um, that's right. And, uh, so here's the corresponding theorem. um it's basically just uh applying the definition and things I've said before but uh good to see that people are following um I just for specificity spelled out the actual algorithm and let's go through this one more time uh just to make sure this is this is super clear I'm not trying to sell this as an exciting result um you can formulate it as a recursive algorithm so you're given some formula And uh I don't actually care what form it is in. It doesn't need to be conjunctive normal form here. And as a second parameter just to make it convenient to write down, I'm given the list of variables of the formula. So you would have some pre-processing that extracts the all the variables uh and calls this function. Um now if the number of variables is zero, there's no more variables in the formula, then it has a specified value. It's either true or false. And so I can evaluate it and this equals equals is supposed to simplify the formula or evaluate it. So this might not be constant time right but it will be um at most linear in the size of the formula. Uh if you find the formula is true then you return the empty set which is the satisfying assignment for the variables that are still in this formula. Uh and that does is empty because there's no variables. Otherwise, we return unsatisfiable because it's just false. That's the base case. Um, if I have some variables, then I'm going to pick the two options for the first variable and recursively solve with both options. So, I'm iterating over the two choices I have for uh x1. Then I'm constructing this partial assignment. just this notation here written as a kind of a function um that maps variables to some uh boolean value.

14:30 Then I evaluate the formula with this um with this substitution. I'm replacing x1 by its value. I guess this is logic speak for substituting the notation is not so important.

14:46 uh you basically iterate through the formula and whenever you see the variable x1 you replace it with the constant value. Then we recursively call this algorithm uh on this simplified formula and with the set of variables without x1 because that's now eliminated. So we will eventually reach this base case if we do the recursion. And now uh what we get back from this recursive call is either this flag unsatisfiable. You gave me something that's false or it's a satisfying assignment. And uh if it's the latter then we add our assignment for a because for for x1 because it seems to have led to a satisfying assignment as well. Okay. I hope this is roughly what you had in mind when I earlier said we just try all possible uh variable assignments. You could split it and first assign all variables in one big uh loop or in in k nested for loops or whatever. Uh there's different ways to write this down. Uh but uh that's one one rather compact way. If you analyze this then um the worst case running time is the time we need or the base case that dominates that's uh linear in the number of in the the size of the formula and the number of recursive calls that we make is 2 to the k in the worst case we might stop earlier if if one of the recursive calls already returns a satisfying assignment we wouldn't actually try the other option uh so it might terminate early but at most it's 2 to the k recursive calls and what we're doing in here is uh it's also bounded by linear time. So that proves this problem is in FPT because we found an algorithm whose running time has exactly this form right there's a a part that depends on the parameter only and then there's the simplest of all polomials the identity function or linear that's certainly a FPT running time now uh a problem with this is that the number of variables is probably not small in in real instances. If the formula is very big but only uses a small number of variables, there's a lot of redundancy in there. Uh so I mean this is this is a true theorem but it's not a very useful theorem. Uh it's not super exciting. Okay, this was basically to test out the definitions.

17:33 Um now I want to make one one uh cautionary remark here that as I said the definition of FPT is chosen in a specific way because it makes for a round theory. uh but it has a few rough edges and in particular it means if you pick your parameter sufficiently stupid everything is in FPT and by everything I really here mean everything everything. So uh formally this statement says if you pick the parameter in a specific way then any decidable language anything you could possibly compute on any computer is actually an FPT or this uh specific parameterization of course is only the parameterized problem that we're talking about. So what is this uh this broken uh way to define a parameter? Um uh this is the attempt to make it minimally broken or not obviously stupid. Of course you can enforce this by making the parameter just an insanely fast growing function. But even that is not so easy to do because uh what's the worst possible running time any touring machine can have? Huh? That's a side problem that we're not so interested in in this class. But uh this is a busy beaver kind of question. Can you make a Turing machine that produces as many output cells? And this I think is an open problem. So maybe it wouldn't even be so easy to write down the worst possible parameterization. Uh but actually something relatively simple and innocent looking uh is enough. You just need that your parameter is bigger than some function of the input where this function is is weekly increasing. So it means it doesn't go down if you increase the uh input and it's unbounded. So it it doesn't just uh stop at some constant value. Um it eventually reaches any possible value. But that's that second part I guess is very natural for uh most most types of parameters. Uh it's the first part that you should be wary about. And we also need this function to be computable. But that's a weak requirement. Okay.

20:00 Um the proof is a little technical, but I want to go through it just to illustrate where these things break. Uh I think it's insightful um to look at this. Yeah. No zooming, please.

20:33 I'll try to keep the theorem here. So first of all, uh if L is decidable, that means um there's some Turing machine that uh some algorithm that computes it.

21:02 And um we can assume that it has some running time right uh let's say in time at most t of t of x the length of x is the worst case running time. um and um without loss of generality I'm assuming that this function is is also weakly increasing and uh larger than x itself. So these are these are technical requirements but they're easy to achieve. You can just take because we only need an upper bound, you can just take the larger of uh the size of x and t if it ever was faster and it's a weird decider that doesn't read the input. Uh and the weekly increasing you could just take the maximum over all running times up to uh sizes up up to this point. So these are uh easy to easy to achieve.

22:09 Um now the proof will essentially try to uh hide this arbitrary running time t in the parameterized part of the function. This f of k part, right?

22:37 Now the question is how to do this because all we have is this uh requirement that the parameter is at least this function g which uh let me stress this again um g could be a reasonable function it could be log of the size right so or let's let's be more more generous it could be log log of of the input size that would still satisfy these requirements.

23:21 So the the trick to do this is to define some think of it as an inverse function is essentially something like an inverse function of uh of g. But because we're dealing with with a function that is maybe not uh bjective so it doesn't exactly exist. But let me still write this as a function in the parameter just called called G as a a variable. And we take the the largest input n such that uh okay it's a bit annoying. Let let me let me say G prime because we also need the function G. that the function g of n is at most this g prime. Now sometimes this set is empty if there is no n for which this function is small enough. So let me formally take the union with one. So it's a base case. If your um g prime is too small then uh h will just output one.

24:47 Okay. Um, let's sketch a bit what this function looks like. And let's start with drawing our function G. It might be low at some point then it might jump. It might stay constant for a while but it will eventually uh go above any any kind of bound that you set for it. So say that is g of n and our function h will be if we put some some threshold here of g bar. Our function h would pick uh the the largest n so that g is still smaller than this. So it would pick this one as that would be okay it's inconvenient now should have planned better in the drawing. So this is h of g prime. Okay. So it's kind of an inverse uh inverse function of G except that because it can jump it's not necessarily a smooth and um doesn't attain all values. Uh but let's collect a few properties of this function h. Uh first of all because G is weakly increasing this was from the assumption and unbounded we get the same we get that age is well defined. There's always a a well- definfined maximum here. How could it not be? Well then this set would be infinite. That that could be how it breaks. But we we say g go go goes above any bound at some for some uh values. So it will always be a finite set of n where g of n is below this bound. That's part one. That's always good when you define something. It's good if it's well defined.

27:03 uh age is also weakly increasing um which you can effectively see from the picture. I mean you're you're making the set if you increase the bound G prime you're just including more elements in the set. So taking the maximum cannot give you a smaller result. Uh that's I think very intuitive.

27:31 Um also because g is a computable h. And how would you do this? You can just go by definition. We don't need to be smart or fast. You can just keep increasing n and if g eventually goes above your bound g prime then you stop. So uh again no claim on the running time it's just needs to be computable. Um and now the important part uh what if you take I said it's a somewhat inverse function so you would expect if this was exact inverses you should get back n um the way it's defined here if we uh if we insert g of n for g prime you see that this is this is really g of n lesser equal g of n uh except that the inner n is a free variable so Certainly um picking the same n always works right um so let let me write n prime here so that we don't confuse it right if you uh it's a greater equal if you insert g of n for g prime then you're trying to find the largest n prime. So that g of n prime is at least g of n. This is at most g of n. Uh certainly if you put n prime to n that always works. Maybe uh because g is constant for a while you can put in larger values than n or n prime. That's fine. Uh but it won't be smaller.

29:27 Okay. And so now the rest is just uh putting things together. the time to decide whether any uh any uh okay decide whether any string in our alphabet star is in the language L. Remember this is what we're talking about. It's a we're trying to solve this parameterized problem LC kappa. So we're asking is a certain word in this language L and I'm claiming that this is an FPT. So that there should be an FPT time algorithm. That's where we are.

30:17 So the time to do this uh by definition was bounded by t of the size of x. We said that's the definition. uh t was the running time of this algorithm that decides l and now we're using that t is increasing which means I can make the argument bigger and the overall function will only grow and so we use this and condition four to replace instead of n let me write n instead of this so n for the size of of X and this becomes uh even more obvious. Okay, I'm just inserting. Now I'm using that both T and H are increasing. So I can make the argument inside H bigger and only the bound goes up. and uh g was a lower bound for our parameter.

31:31 So if I write k for kappa of x then um that is greater than g of of n and so that's upper bounded by h of k and then that's all we need because that is a a function just of k. We haven't defined that function but here it is. Okay. So the the overall the total time that whatever this algorithm is that decides L however long it takes uh we can hide that in a function that depends only on the par on the parameter if that parameterization is chosen according to these conditions it's uh it's lower bounded by a function that's never in never in decreasing. So whenever you define parameters, you probably need to tolerate that sometimes a smaller problem has a larger parameter than a larger problem. That shouldn't be too surprising or too hard. Okay? So take it as a as a long caveat to say the theory is a little broken if you allow arbitrary parameters. Uh it doesn't always make sense. FPT doesn't imply anything unless you also pay attention what the parameter is.

33:04 Uh but for now let's forget about this. Um as I said the definition is to make the theory round and you have to uh use it wisely.

33:14 Um FPT doesn't even relate to NP in general. Uh any computable function can be in FPT. Good.