Advanced Algorithms (Winter 2026-27) - 04-02 Fixed Parameter Tractability
Watch on YouTube →
Overview
Fixed-parameter tractability separates the cost of an algorithm into an arbitrary computable function of parameter k and a polynomial function of input size, written f(k)n^O(1). Sebastian Wild contrasts FPT with XP using SAT, Clique, Vertex Cover, and graph coloring, then shows why parameter choice matters: any decidable problem can appear FPT under an unbounded parameter that grows with input size.
Key takeaways
- FPT means runtime f(k)n^O(1): dependence on k may be superpolynomial, but the polynomial degree in input size must not depend on k.
- An n^k algorithm is in XP because it is polynomial for every fixed k, but it is not necessarily FPT because the input-size exponent increases with k.
- SAT parameterized by its number of variables is FPT by direct enumeration: a binary assignment tree has at most 2^k leaves, with linear formula processing per branch.
- Graph coloring illustrates a sharp complexity boundary: 2-colorability is polynomial-time bipartiteness testing, while 3-colorability is NP-hard.
- A parameter that necessarily grows with input size can make any decidable problem appear FPT by hiding the entire decision algorithm's runtime inside f(k); such a parameterization has no useful tractability guarantee.
Chapters
- For SAT parameterized by its k variables, exhaustive search checks 2^k assignments with linear work in formula size.
- For Clique, enumerating size-k vertex subsets takes roughly n^k candidates, each checked locally in about k² time.
- Brute force for Vertex Cover checks candidate subsets against m edges, while graph coloring can require examining k^n assignments.
- The examples show how the same input-size complexity can behave very differently as the parameter k grows.
- A bound such as 2^k n remains polynomial when k is O(log n), since 2^(C log n) is a polynomial in n.
- A runtime like n^k is polynomial for each fixed k, placing the problem in XP, but its polynomial degree depends on k.
- FPT requires polynomial input-size dependence with a degree independent of k, unlike the n^k-style XP bound.
- For coloring, brute force k^n is exponential even at fixed k; 3-colorability is NP-hard, whereas 2-colorability is testable in polynomial time because it is equivalent to bipartiteness.
- An FPT runtime has the form f(k)n^O(1), where f is any computable function and the exponent on input size is fixed.
- The function f may be very large, even Ackermann-like; its purpose is to isolate parameter dependence from input-size dependence.
- For SAT with k variables, recursively assign each variable true or false, producing a binary search tree of at most 2^k leaves.
- Each assignment step processes the formula in linear time, giving a total bound of 2^k times a polynomial, typically linear, in formula size.
- If a parameter is lower-bounded by a weakly increasing, unbounded function of input length, it can encode the input size.
- For any decidable language, a computable parameter-dependent bound can absorb the runtime of its deciding machine, making the problem formally FPT even without a polynomial input-size factor.
- This construction is mathematically valid but practically useless, so FPT claims require sensible parameters rather than parameters that inevitably grow with every larger input.
- Natural graph parameters such as a Vertex Cover size threshold can remain small as the graph grows, which avoids this particular pathology.
Transcript excerpt
0:00 In the next section, I want to formally introduce what we mean by this notion of fixed parameter tractability. So, an algorithm that is maybe in the worst case exponential or at least exponential is the best we know uh subject to P not equals NP. Uh but if you look at a second kind of hardness criterion, a parameter of the problem, then it becomes more solvable. What do we mean by that? Um different options from different problems where there is a specific algorithm with a running time. If we want to solve satisfiability, where the parameter is the number of variables, then we have an easy brute force 2 to the K times linear in the formula size algorithm that just tries all assignments.
0:46 So, it's kind of a a very uninteresting algorithm, but you could say in terms of the running time if K is small, this is actually fine, right? Um the next step up was when you have uh the the canonical parametrization of the clique problem. So, we're looking for cliques in a graph of a certain size, and this threshold that we give is our parameter. So, the larger the cliques we ask, the more tricky the problems get to solve. That's the assumption under this uh parametrization. Well, we can just go through all size K subsets of vertices and check if they form a clique. That check is indeed here cheap because it's just local to the subgraph. So, you could say this is in a way even better than this um next one
1:35 because here I have this n to the K as a theta class from the number of candidate subsets. And each just takes K squared to check. If K is small, that's faster than linear in the graph size, whereas for vertex
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).