Advanced Algorithms (Winter 2026-27) - 04-05 Kernel for p-MaxSat

Overview

The kernelization argument for canonical p-MaxSat, parameterized by the target K clauses to satisfy, reduces the instance to at most 2K clauses of fewer than K literals each, giving an encoding-size bound of O(K²). The case split handles easy instances directly, then removes long clauses while lowering the target; the resulting kernel implies that p-MaxSat is fixed-parameter tractable.

Key takeaways

Canonical p-MaxSat parameterizes by K, the requested number of satisfied clauses, and its kernel has encoding size at most 2K².
When K is at most half the formula's clauses, an assignment and its full negation together satisfy every clause across the pair, so one of them satisfies at least half.
In the nontrivial case, requiring more than half the clauses implies that the formula has fewer than 2K clauses.
Long clauses can be removed while reducing the target by their count: variables used to satisfy the remaining short clauses can be avoided when selecting variables for the long clauses.
A kernel whose size is bounded solely by K establishes that canonical p-MaxSat is fixed-parameter tractable.

Chapters

0:00 Kernelization and the Canonical p-MaxSat Parameter

The parameter K is the number of clauses the solution must satisfy, rather than the total number of clauses.
A kernelization efficiently maps an instance to an equivalent instance whose encoding size depends only on K.
A parameterized problem is fixed-parameter tractable if and only if it has a kernel, although the kernel-size function can still grow substantially with K.

2:00 Easy Cases: Half the Clauses and Long-Clause Matching

If K is at most half the clauses, an assignment or its complete negation satisfies at least half, making the instance immediately a yes-instance.
For the remaining case, the total number of clauses is less than 2K, so clause count is already bounded by the parameter.
A long clause has at least K literals; for a collection of long clauses, distinct variables can be selected to satisfy them, leaving only the short-clause case to kernelize.

4:18 Removing Long Clauses and Bounding the Kernel by 2K²

If there are L long clauses, remove them and reduce the target from K to K minus L; the short-clause instance is equivalent to the original.
Satisfying K minus L short clauses requires choosing at most K minus L variables, leaving enough unused variables to satisfy all L long clauses.
The reduced instance has fewer than 2K clauses, each with fewer than K literals, so its encoding size is bounded by 2K².
The kernel bound yields an FPT algorithm for canonical p-MaxSat.

Transcript excerpt

0:01 We're in the middle of discussing uh a kernel for the max that max that problem if you parameterize it by the canonical parameter so the solution size, how many or 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. That was the result that we were uh 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 um I don't know how far that was a go. Uh the three properties

0:48 um it translates yes instance instances into yes instances. They don't necessarily have to be of the same type of input. They could 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. 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. 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 polynomial.

1:36 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 uh satisfiability. The natural parameter

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Sebastian Wild (Lectures).