Advanced Algorithms (Winter 2026-27) - 04-01 Parameterized Problems

Overview

Sebastian Wild introduces parameterized complexity as a way to explain why some large instances of hard problems remain tractable when a meaningful input parameter is small. Using SAT, 2-SAT, 3-SAT, clique, vertex cover, and knapsack, he contrasts useful and unhelpful parameters, then defines parameterizations and canonical threshold parameterizations for decision problems.

Key takeaways

FPT analysis supplements input size with a parameter that captures which instances are practically manageable, such as the size of a vertex cover.
The number of SAT clause literals is not a useful gradual parameter because complexity jumps from polynomial-time 2-SAT to NP-complete 3-SAT.
With k variables, SAT can be decided by testing all 2^k assignments, giving an exponential dependence on k even when the formula has many clauses.
A parameter should be both small on relevant real-world instances and algorithmically useful; selecting one is a substantive modeling choice.
For optimization problems such as vertex cover, the canonical parameterization treats the decision threshold k as the parameter.

Chapters

0:00 Why Parameterized Complexity Looks Beyond Input Size

Fixed-parameter tractability (FPT) asks whether a parameter can better predict problem difficulty than total input size alone.
Some large vertex cover instances can still be solved practically when their structure is sparse or their optimal cover is small.
A useful parameter should stay small on the instances of interest while still enabling efficient algorithms.
Choosing a parameter involves a tradeoff: poor choices can make the problem either uninformative or nearly as hard as the unrestricted version.

3:40 SAT Examples: Useful and Unhelpful Parameters

The number of literals per clause is a poor SAT parameter: 2-SAT is solvable in linear time using implications and strongly connected components, while 3-SAT is NP-complete.
The number of variables gives a brute-force algorithm with a 2^k assignment factor, regardless of how many clauses the formula contains.
The number of clauses or total literals is roughly tied to formula size, so those values need not remain small as the input grows.
Max-SAT offers other candidate parameters, such as the maximum number of clauses that can be satisfied.

10:36 Formal Parameterizations and Canonical Thresholds

A parameterization maps each possible instance to a number and must be computable in polynomial time.
A parameterized problem pairs an ordinary decision problem with a chosen parameterization; examples include SAT parameterized by variable count and clique parameterized by target size.
For optimization problems, the canonical parameterization uses the threshold in a decision question, such as whether a graph has a vertex cover of size at most k.
The notation places the parameter after P and before the underlying problem name, as in P_variables-SAT.

Transcript excerpt

0:01 In the next unit, we'll look at the generalization of pseudo polynomial time algorithms and the much larger complexity theory attached to it as well. That's called the the fixed parameter algorithms or fixed parameter tractability and then the corresponding hardness. Uh this will keep us busy for a bit longer. Um basically, I'll I'll show you some of the definitions today and then we'll see some more examples uh later. It's a very active area of research which has a a good breadth. You can work on many different problems and on many different parameters. Uh and that's bringing us a lot closer to the current current frontier of research there. Um FPT again stands for fixed parameter tractable. I'll tell you what that

0:48 means. But um first a bit high-level, what's the what's the idea behind it? Uh when you study hard problems, it often happens that they are not equally hard. Some are still rather tame to solve in practice. My hope is that with this vertex cover game that we played together in the first week, you've experienced this as well, that often even these initially scary-looking large instances, you could actually tease out an optimal solution with not too much effort. Now, there's of course several things going on. This were They were large for fiddly fingers on a phone, but not really large. Uh and also they had a certain because of their size um

1:34 a certain property still that they're somewhat sparse and uh there's not too many hideous things you can you can hide in a small instance. So, maybe it doesn't completely generalize. But still, it seems uh some problems and vertex cover will be one of them. Um at least the the hard instances have a certain quality. And so, FPT tries to tease out

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