Video 4-0: Parameterized problems

0:03 In unit four, we'll look at fixed parameter algorithms, which will be focusing on problems where you can hope that one certain parameter is small and then exploit that in designing algorithms. In the worst case, these algorithms will be exponential in time in running time because we're dealing with NP-hard problems. That seems inevitable, but we'll try to squeeze that bad polynomial that that bad exponential time as much as possible and contain it to some some part of the problem that hopefully is in in applications that we care about not not too big. Uh you'll see what this is like. Uh I'll introduce some of the concepts, then we look at two uh design techniques. This um depth-bounded exhaustive search and and and kernelizations. And we'll see a bunch of examples starting uh from very superficial examples and then digging through a few that exploit the problem at hand a bit more.

1:10 The philosophy of this uh approach of fixed parameter tractability uh really can be seen as a generalization of what we discussed last time about uh pseudo polynomial algorithms. There we said we have an input size n, but we also care about this largest integer value in the input that we called max int. And the hope was that maybe um in general you can't avoid exponential time, but if your integers are small, then you can still do a polynomial time algorithm. And so we had algorithms that were ex- parameter that were were polynomial in n and k. Um that's what we called pseudo polynomial time. Now here uh we'll try to set up things a bit more uh more broadly or more with a bit more general uh scope. And uh we'll look at at inputs where there's always some specified second parameter um apart from the input size or the encoding length.

2:14 The goal will always be to find a parameter that is on the one hand uh so that you can solve the problem efficiently if if that parameter is small and hopefully also that parameter is small in the cases where we care about. For the second part, we'll usually just appeal to some uh cartoon applications. Uh the goal in in the theoretical side here is is to sketch out this the vast space of possible parameters.

2:50 Let's make this a bit more concrete and also motivate a bit why this might make sense. Um and we'll we'll look at again the satisfiability problem of uh propositional logic, specifically again these conjunctive normal forms uh formulas. And uh well, if you um if you have some some background from biology, there's there's the notion of model organisms that people study in detail as representatives for a whole range of different possible animals or or plants. And this the fruit fly here, Drosophila melanogaster, is one of those model organisms. So a lot is known about these fruit flies that you may not care about per se because it's maybe not the most important animal on Earth, but they're it's studied to represent other animals uh and so many things can be translated from there. And a bit you can think of satisfiability uh as well like this. We don't always care about just the result we prove about satisfiability, uh but it turns out to be a good proxy for other problems.

4:01 Okay, of course we know the general uh problem is NP-complete, uh but if we say we fix the number of literals per clause, then if k is really small, this is actually an easy problem. I don't know if people know this. That's the the two-sat problem.

4:20 Um this is sometimes shown as an application of uh strong components in graphs. Uh the deal with two-sat is that if you have a a clause with just two literals, so say xi or not xj, this is the only thing that can happen. You can always transform that into an implication. An implication a implies b as a logical statement is the same as saying not a or b. And so this is a two-sat clause. So I could I could translate any such clause into in this case it's convenient to say xj implies xi.

5:04 Or you could have also turned it around. You could have also said it's same as uh not xi implies not xj. So you can you can uh write any formula that has only two variable two literals per clause as a conjunction of implications, which says if one variable is fixed, the other is determined in uh in many cases. And so these are essentially edges in a directed graph. And if you have a strong component in such a in this in this graph, then you have a essentially a contradiction. So um uh well, this I'm I'm I'm uh shortcutting here one bit where you uh introduce where how you define the graph. But in essence, if you can if you can solve uh strong components in graphs, which is in polynomial time, you can solve these uh formulas with two uh literals per clause. On the other hand, if k is at least three, we know the problem is NP-complete because it's one of Karp's uh famous problems, three-sat.

6:16 So in a way this parameter does make a difference, but uh the transition is very abrupt and sharp and at a very small value. So it's maybe not a good parameter in uh in our sense. Uh but there's many others um you could try. Uh you could take the number of variables. Then um you can essentially try all possible uh assignments. And if the number of variables is small, maybe this runtime is good. Uh you could also try the number of clauses in the formula. That's closely related to the length, so um maybe also not a not a parameter to ex- that we can expect to be small. Same if you take the number of literals. Just to make the point that yes, this can be a very general thing. You could also take as k the number of variables that you have to set to true in a satisfying assignment. That one sounds a bit crazy, but uh can actually make uh make for a sensible algorithm.

7:21 Uh or you can ask other properties about the the formula. If you somehow represent it as a graph, uh can you say something about the structure? These are all possible parameters. They may or may not help. Um the point is to set out the theory broadly enough that you can study all of them and decide uh which ones are are helpful or which ones don't make the problem easy even if they're small. Uh then we also looked at this maximum sat where you wanted to satisfy as many clauses as possible even if it's not possible to do all of them. Uh there you could say k could be the number that you want to satisfy. So if you're happy with just satisfying clauses, maybe that makes the problem easier. Okay. Uh many of these um will come back to us in some point or some form or another. Uh here basically just the point of the slide is many ways to choose parameters.

8:28 Uh so let's define this um a little bit. Uh first of all, uh we say again we start with languages, so there's an alphabet and uh there's a language as a subset of of uh sigma star over this alphabet. Now a parametrization is is some function. Uh we'll I'll write kappa for these functions and k for the parameter so that hopefully that's mnemonic. It's just a function that maps these strings from from that um from all possible strings to numbers. Um and we would want would like that this is efficiently computable. So there's a an algorithm that computes this mapping in polynomial time. And then we can define a parameterized problem. That's a pair of a language, subset of of this alphabet, and a parametrization. Okay?

9:25 So far completely general. Um Sometimes it's convenient because the language already has the form of a pair where you have a a word and a number. So uh if the language already has this specific form, you could say we uh we don't need to specify the parametrization. It's just take the second number as your parameter. And uh I'll call this the canonical parametrization. Um you'll see in a minute where where this pops up.

9:59 Uh let's see two examples uh just to make it clear. Uh, one option is uh this problem where we say the input is is a Boolean formula and the parameter is the number of variables. So, one of the bullets from the introduction slide. Uh, the question remains unchanged. So, we're not talking about max sat. This is standard satisfiability. We still ask the yes no question, is there a satisfying assignment for the entire formula? Um, and this is called P variables sat where this prefix P stands for a parameterized problem just so that we can always distinguish, is this only a language or is it a language and a parameter? Uh, and variables obviously for the parameter here. Um, second example, P click um is the click problem where we're given a graph and a threshold. And now the parameter is just the threshold. So, in this case, I'll just write P click for using the canonical parameterization.

11:01 And well, you remember what the click problem is, find uh a complete subgraph of at least K vertices. Uh, indeed this canonical parameterization always makes sense uh when you talk about optimization problems. Click was one example. Um, in general, we set up this this uh formalization for optimization problems um uh in unit two. So, whenever you're given such a problem, you can say the parameterized version of this problem, the canonically parameterized version, is the this the threshold language. So, again, this was pairs of uh uh an instance for the optimization problem and a threshold K, a number. And um it was uh the language contains all those pairs where the optimal solution for X is at least as good as K. Right? That's the natural decision problems associated with an optimization problem.

12:13 And now the parameter is also just set to the same number K. Now, this means uh this this problem contains instances where this this threshold is exactly the optimal value, uh but it could also be the threshold that is loose, right? Uh it doesn't need to be the the exact optimal answer. It's just this pair of numbers um that make up the parameterized problem. Uh just to reiterate, that's precisely what's written here for the click problem. We're given a graph and an arbitrary number and the question is open. It may or may not the graph may or may not contain a click of at least uh K vertices. Um, but that's the parameter no matter whether the graph contains a click or not, the given number is your parameter. Okay?

13:15 That's the basic setup. Um, and of course, this is not the only way to parameterize an optimization problem. It's a natural thing to ask for this this specific number as a parameter, but you could also define whatever else you can think of. Uh, parameterizations can be anything.

13:32 Anything that maps the input to a number. Uh, of course, we've seen many optimization problems and the canonical parameterization exists for all of them. Um, where it where it's clear what we mean, uh I'll write the specific parameter between P and the problem name. That's a nice nice shorthand notation. So, we could use this to mean CNF sat problem where I'm parameterizing by the number of clauses. I've seen the one with variables before.

14:23 Are there any questions about the general setup? Again, so far, we haven't talked about running times. I've just defined languages and parameterizations as a mapping from from words to integers.

14:39 Uh, plus a few naming conventions for problems. Nothing interesting has happened so far.