Advanced Algorithms (Winter 2026-27) - 04-04 Kernelization

Overview

Sebastian Wild introduces kernelization as polynomial-time preprocessing that preserves a problem’s yes/no answer while reducing an instance to size bounded by its parameter. For Vertex Cover, Buss’s rules yield an O(K²)-size kernel, and Wild proves that a problem is fixed-parameter tractable if and only if it has a kernelization. The lecture closes with an unfinished outline of a kernel for Max-SAT parameterized by the number K of clauses to satisfy.

Key takeaways

A kernelization is polynomial-time, preserves yes/no status, and bounds the output size by a function of the parameter alone.
For Vertex Cover with budget K, repeatedly selecting vertices of degree greater than K and applying degree-zero and degree-one rules yields an O(K²)-size kernel.
A kernelization implies fixed-parameter tractability by solving the parameter-bounded kernel with any computable decider.
An FPT algorithm with running time f(K)n^c implies a kernelization by simulating it for n^(c+1) steps: completion yields a fixed answer-instance, while timeout implies n is bounded in terms of K.
For any Boolean formula, an assignment and its complement together satisfy every non-tautological clause at least once, guaranteeing that one of them satisfies at least half the clauses.
The Max-SAT kernel outline must control total literal count, since bounding the number of clauses alone does not prevent very long clauses.

Chapters

0:00 Reduction Rules: Simplifying SAT and Vertex Cover Instances

A reduction rule transforms an instance in polynomial time without changing its yes/no status.
For Vertex Cover, a degree-zero vertex can be deleted, while a degree-one vertex’s neighbor can be chosen to cover its edge.
In SAT, a unit clause such as X forces X to true; resolution derives a clause combining the nonshared literals of clauses containing X and not X.

4:55 Buss’s O(K²) Kernel for Vertex Cover

The goal of kernelization is to reduce the full input to an equivalent instance whose encoding size depends only on K.
For Vertex Cover with budget K, a vertex of degree greater than K must be selected; select it, decrease K by one, and remove its incident edges.
After applying the high-degree, degree-zero, and degree-one rules, every remaining vertex has degree between 2 and K.
With at most K selected vertices and maximum degree K, a cover can cover at most K² edges; more remaining edges certify a no-instance, while the reduced graph has size O(K²).

13:00 Why Every Kernelization Gives an FPT Algorithm

A kernelization runs in polynomial time and returns an equivalent instance of size at most g(K), for some function g.
Run any computable decision procedure on the kernel; if its running time on size s is T(s), the second step takes at most T(g(K)).
The total running time is a function of K plus a polynomial in the original input size, so it is fixed-parameter tractable.

20:00 Turning an FPT Algorithm into a Kernelization

Assume an FPT algorithm runs in at most f(K)n^c time, then simulate it for only n^(c+1) steps to keep preprocessing polynomial.
If the algorithm finishes, output a fixed yes-instance or no-instance matching its answer.
If it does not finish within the timeout, f(K)n^c exceeds n^(c+1), which bounds the original input size n by a function of K; the unchanged input is then already a kernel.

26:00 Max-SAT: A Half-the-Clauses Guarantee

The next example parameterizes Max-SAT by K, asking whether some assignment satisfies at least K clauses.
Measure kernel size by the total number of literals, not just the number of clauses, because a few clauses could still be very long.
For any assignment and its bitwise complement, every clause is satisfied by at least one of the two assignments, so one satisfies at least half of the M clauses.
When K is at most the guaranteed half of M, the instance is immediately a yes-instance.

34:00 Bounding Max-SAT Clauses and Splitting Long from Short

Outside the easy half-clauses case, the relationship between K and M bounds the number of clauses in terms of K.
Few clauses do not by themselves bound the encoding size, so the argument separates clauses of length at least K from shorter clauses.
The lecture sets up a second case distinction based on the number of long clauses, with the aim of satisfying them using a pigeonhole-style selection of variables.

37:00 Max-SAT Kernel Outline and the Unfinished Proof

The proposed strategy uses the long clauses’ length to select variables that satisfy them, leaving only short clauses to represent in the reduced instance.
If the long-clause count is small, the lecture argues that their contribution can be handled directly; if it is large, variable selections are intended to satisfy them.
Wild ends by labeling this reasoning a claim and postponing its proof, so the Max-SAT kernel construction is not fully established in this lecture.

Transcript excerpt

0:00 Before we continue looking at some concrete algorithms, there's um uh a related notion to FPT algorithms, the notion of problem kernels, that you can already see from uh what we've looked at, and that's uh as you'll see is an equivalent formulation, but it somehow sometimes is much more natural to think about. Um that's the It comes from the idea of of a preprocessing uh step that um sometimes you can by uh looking at a specific input get this feeling, like in the example we've seen, picking that edge and then trying that vertex was clearly stupid. We should have when there was this um this edge in the tree and then here this

0:49 was the input graph, the algorithm selected this edge and then decided, "Oh, let's try to put this one in the solution." Like, why? It's just obvious. If you have a degree-one vertex, you want to take the other end point of that edge. Uh that's a simple insta- an instance of a reduction rule that in general says, "Here's a an input. I'm going to transform it to a slightly different input where um I can cheaply prove that it doesn't affect the uh feasibility, um but it's somehow a bit easier or smaller." Uh we want to do only things that can be done in polynomial time at this point, and they are not allowed to at all change the satisfiability or the yes-no character of the input. Um one one example for the

1:39 satisfiability problem again is uh clauses that are obviously satisfied. So, for example, here a clause that contains uh this is the other way around uh a single literal clause. If you have um a clause that contains only X, well, the only way to make that

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).