Video 4-4: Problem kernels: p-MaxSAT

0:02 There's one last bit in in that section left where we'll look at the max problem again. So specifically P max which means it's parameterized by the second uh the threshold that you give it. So K is the number of clauses that you would like to satisfy.

0:40 And um what we'll show is that you can for this problem pax you can construct a kernelization and also the resulting kernel of the problem is is bounded by a reasonable function of K not just some arbitrary uh potentially very fast growing function but just K square. So let's um pick some example just to make it a bit explicit um of some formula. So this is remember maxad um it doesn't need to have a strict form for the literals for for for the classes but it has to be in conjunctive normal form. So maybe it looks like this.

1:28 And there can be stupid and redundant clauses in general. I'm just using this short notation with a bar on top to denote the negated literals.

1:46 So we'll often think of a formula like this to be given as a a set of sets namely replace the outer and by one um by one uh set and then each clause is also a set of the literals that are contained in it. Uh the reason for that is just we don't actually care about the order of the literals in a clause and also the ordering of the clauses is not really important although we sometimes need to give them names but um so you you represent a formula like this as a set of sets. The outermost is the set of all classes. The innermost sets are the set of literals one clause each. Okay. To make um as a first first simple step you can say it's an assumption or you can enforce it. Say each variable only occurs once uh per clause.

3:11 This is kind of implicit with the set notation. Uh if um if you talk about literals and if a clause ever contains uh a variable and its negation, you just cross the two off because they're um the literal will always be satisfied, right? Then you can remove that um standard notation we had before I think is the number of clauses is n is m. Sorry, I'm using m because n is reserved for the input size, right? Uh so n is the total input size and we'll have to encode this in binary at at the end in some form. But uh really the the main thing you could think of it as uh the total number of literals in all clauses and maybe there's a log factor missing or specifying which which variable you mean in each case. Okay. Now uh let's do something um about the actual proof. The first observation is if k is small the whole problem is trivial and we can uh get rid of that case. If k is specifically less than half at most m half rounded down then I can always satisfy at least half of the clauses because you pick an arbitrary Uh, does that need a name? Maybe not.

5:27 Let's call it A. And now what's going to happen? A is going to satisfy a certain number of clauses, right? And we don't know what L is, but clearly if L is at least K, then we're done. We can just output a yes. It's a yes instance. We found a satisfying assignment for that instance.

6:10 Um the other option if L is less than K then it's specifically less than M half then you you're doing the opposite of whatever A does because if A does not satisfy uh these other clauses it means every single lit neutral in these clauses must be false. Right? So if you uh just invert the variable assignment, those clauses turn true.

7:18 it satisfies m minus l of the clauses. And then if you um if l was smaller than half of them, this has to be greater than half and so greater than k. And so we could uh again turn it into a yes instance. So indeed whenever that's the case we can output yes without doing anything. So uh if you um want to be strict about the kernelization you just output a trivially satisfiable a satisfiable formula of constant size.

8:09 So for the rest we can assume that K is not tiny. So the second case is K is at least M half rounded up. And so can we use that somehow? Well, you could just turn it around to bound M. The number of clauses then can't be too large in terms of of K. Right? Then m is strictly less than 2 * k. Um just because of the rounding sorry the I guess the case should be raised like this.

8:51 Um because that's the negation of that and that also works in the even case. If if if m is even then this is exactly m half and here we have strictly greater than m half. If m is odd then this was rounding down but then this is rounding up and then again k is strictly greater than m half. So maybe uh if you want make this more explicit.

9:28 Okay, so we already have the number of clauses is not too big. That's not a kernel yet because each of the clauses could be really big and the kernelization needs this overall size of the formula to be small.

10:10 up into those clauses that are already small enough. And we're aiming for a kernel size of k squared. So if we have roughly k clauses, k literal per clause is okay. That gives us a k squ size. Uh, but the clauses with more than k literal we have to take care of. And so we have the large literal L. There'll also be the small literal. These are all the clauses C in the formula. So that uh C has K or more literals. And conversely, this is all the others. And now uh again an observation if we have a lot of these large clauses then that's an easy case.

11:23 So we say capital L is the number of large of long gloss clauses or large clauses. Now if this is greater than K then we have these really long clauses and K of them. So it's enough if we satisfy only these K clauses uh only long clauses. Now because they each have um at least K literal they also have to talk about more than K variables at least K variables. That was our assumption up here. Right? Uh the variables occur only once in these in each of these So we have k clauses right k large clauses uh each with k variables in them. So we can pick a disjoint collection. We can pick one variable per clause and assign it so that that clause becomes true without making any of the other clauses false because there's uh we can pick this one here, this variable here, this one here uh and they're disjoint.

12:58 I guess unique bit important. So if we're in this case uh many long clauses, we immediately output a yes instance and we're again done. So if if we detect this case again, output a trivial yes instance and you're you're done. So what's left is the case L is less than case? In this uh this case we have to work a bit harder but uh we can use the the following. uh we consider now the instance where we just look at the short formulas with the parameter reduced so that uh we only have to satisfy where so we're kind of satisfying all the long clauses by the same argument um and we try to satisfy the from the short clauses enough clauses to uh in total get to k Okay.

15:22 And the reason for that is [Music] um so there's this is uh it's an if and only if statement. So we're we're proving the two directions separately. If there's a satisfying assignment for K minus L clauses in FS among the short clauses. Now we're trying to extend this so that uh at least that that all the long clauses are satisfied.

16:12 um, each of the each of these short clauses has to be satisfied because of some literal otherwise it wouldn't be satisfied. Now the point is we don't have to satisfy more than one literal. So we could uh pick one true literal from each of these short clauses. And so that fixes at most k minus l different variables because there's only k minus l clauses. So we pick k minus l literals that have to be So what I mean by fixing here is I can I can take the assignment and I can flip the value of the remaining variables without making these k minus l short clauses false. And so that means uh I have a lot of variables left that I I haven't used. in particular for the L long clauses. They're each at least K variables long. K minus L might already be taken, but I'm I'm left with L variables that I can still assign. And uh I have to be able to find a disjoint set for the same reason as before. The clauses are long enough. They must contain many different variables. There must be a selection of L different ones.

18:36 Okay, that proves one direction. Uh if we look at the other direction, it's actually easy. If we can satisfy K clauses in the all of F, then uh I only have L big clauses. So even if I satisfy all of them, I must leave K minus L clauses to be satisfied among the small ones. So I'll save myself the ink there. So now that we've established this again, um this case was easy. In this case, um we've reduced the problem to something smaller. Now we only have small clauses, right?

19:33 again. Only the short clauses with a slightly different parameter. Um what's the size of this problem? Well, it has clauses. But remember what we learned about that. If we're not in the boring case, then this is at most 2 * k and each has uh at most well strictly less than k uh variables indeed literals because we're only looking at the short ones. So if you multiply this up the total number of literals or the overall size number of literals is order k^ squ and if you want the encoding size then maybe there's a log factor needed to specify the variables but maybe this would be the more true answer. Um, but we're often not fuzzy about the encoding in binary specifically. Uh, so we'll we'll be happy with a natural parameter like the number of literals in the entire formula. And that's that's the end of the proof. Um, we've output a kernel in each of the cases. You can trace the steps. Again, there's only one where the kernel is non-trivial. In all the other cases, it was just a a constant size yes instance that you can arbitrarily pick. And because of our previous theorem, the last one we proved before, we have a kernelization for P max. That also means P max is an FPT. This uh the complexity class of all problems that have an FPT algorithm.