Video 4-5: Kernel for p-MaxSat

0:03 We're in the middle of discussing a kernel for the max that max that problem. If you parameterize it by the canonical parame parameter, so the solution size, how many um how many clauses in your formula can you satisfy? And the claim here was that it has a small kernel. Again, kernel having any kernel that is bounded by just the parameter in size is equivalent to having an FPT algorithm. Was the result that we were have proven here. If you have a parameterized problem um then it's uh fixed parameter tractable. It has an FPT algorithm if and only if there is a kernelization and kernelization again I don't know how far that was a go. Uh the three properties um it translates yes instance instances into yes instances. They don't necessarily have to be of the same type of input. It be in principle very different from the original input that you start with. But you should think of it as a form of pre-processing.

1:04 That's um where the idea comes from. It should be efficient to compute and then the output of the input the encoding size of the instance we generate is bounded by a function of the parameter only and so in that sense um it's small.

1:22 Now often in in principle this function of the of the parameter can be arbitrarily bad as with FPT always but we'll see a few examples where indeed this function is rather modest and it can be polomial that doesn't make the problem easy because it's still um in general the parameter can be large and if the problem size is now dependent on the parameter only it might still be a hard problem. Okay, that's that's the case for satisfiability. The natural parameter that you would pick in the original problem would be all clauses and then the parameter is not small or the case that you're maybe interested in satisfying only a bunch of the clauses. Uh we already broke it down. The easy case is when you're asking for really not that many clauses to be satisfied. If it's less than half, then you can pick any assignment and either that assignment or its negation satisfies at least half of all clauses. And so that's trivial.

2:24 So the case that is interesting and the only one that that is is a kind of requiring some work is when you're actually asking for most in some quotes of the clauses to be satisfied, at least half, right? Um on the flip side this means that we don't have too many clauses just from this inequality. It means we can't have more than 2k clauses not even 2k clauses which means the number of clauses is already fine. It's already a function of the parameter. Uh what is not is the total encoding size because these clauses could in principle be large. And that led to another case distinction. Namely, if we have many large clauses, it's again it's again easy because in a large clause made up of at least k um literals, that was the definition of large. Then you can think of these aligning as as if they were strings. If they all have uh at least k entries, you must find some k columns where they um have where where you can um pick you can pick k columns and have at least one entry per per clause and the entry you pick is the literal you make true by setting the variable in this way. So here the columns are the variables and the clauses because they have at least k literals. You can find k columns so that you hit every clause and you can make these all true by picking one variable one literal that you force to be true.

4:06 So again uh a subcase that is easy. If you have many clauses if you have you want to satisfy many clauses uh but also many large clauses then you're again fine. What's left is the case in between. You're you want many clauses satisfied, but they're not all long. So you could say again the short clauses are kind of fine because they're short. They're a kernel. But we have to deal with the long clauses that may be left. And so that's the last little bit that we left open. Um the idea is to do a reduction at this point. Um but I left this as a claim. So the idea is [clears throat] to take take the long clauses and use that we can find unique literals there to satisfy them so that if there's uh L of these we can definitely do these L but we have to recursively take care of the short clauses but first observe that this this is bounded in size because the the clauses all have at most k literals and now I have at most um a function of k clauses from the first case distinction this was at most two k clauses each um in the short one at less than k literal That's where the squared comes from.

5:47 Less than 2k clauses and less than k literal in the short clauses fs. So if you multiply that you get the 2k ^ 2.

6:20 what remains to be shown is that the yes instance becomes a yes instance just to be on the safe on on the safe side. Maybe it's obvious. Um let's let's formally prove the claim.

6:42 if we can satisfy K of the clauses in all of the clauses long and short combined, well then uh if there's at most capital L long clauses, I can definitely satisfy K minus L of the short ones. I have to have it many at least as this many.

7:15 if we can satisfy from the kernel these k minus l short clauses then each of these um k minus l clauses This otherwise it wouldn't be satisfied. But then to satisfy these clauses, it's also enough to make some selection of these k of these literals true. these K minus L literal.

8:14 That means I can I can pick the variables from these literals, set them so that the literal becomes true. That satisfies all these K minus L short clauses and they cannot be false falsified by setting some of the other variables wrong. Right? This is a a disjunction. And that means I still have capital L variables that I can set for free for sure. And I can uh in my long clauses always find L columns because they're so long. They're more than more than K even. I can always find some L positions, some some L unused variables for making the long clauses true.

9:23 And so um if I can solve this one, I can solve this one is also a yes instance and vice versa. So with that um that concludes the proof because we've constructed an equivalent instance but one that is bounded in terms of uh function only the parameter k^ squ in this time in this case um as a corollery this of course also means that this problem the canonically parameterized maximum satisfiability problem is an FPT because having a kernel is the same as being an FPT.