Courcelle's theorem states that for every property P expressible in Monadic Second-Order Logic (MSO) and every graph of treewidth at most w, checking whether a graph satisfies P is FPT in w and n. However, the dependence on w is non-elementary (a tower of exponentials). Is Courcelle's theorem still practically useful despite this super-exponential dependence?
ANo, because the super-exponential dependence makes the algorithm impractical for any reasonable treewidth
BNo, but the theorem is theoretically important for showing which problems are FPT; for practice, explicit algorithms (like DP on tree decompositions) yield much better bounds
CYes, because the tower-exponential is in w, not n, and many real-world graphs have small treewidth (under 5)
DCourcelle's theorem is only applicable to very restricted graph classes and has no relevance to general graphs
Courcelle's theorem is a meta-theorem: it proves existence of FPT algorithms for an enormous class of problems without specifying algorithms. The hidden constant tower is astronomical. In practice, researchers design explicit DP algorithms on tree decompositions that give polynomial dependence on w or small exponentials like 2^w, running in milliseconds for small w. Courcelle's theorem is invaluable for determining which problems are 'in principle' solvable on bounded-treewidth graphs, guiding algorithm design. The explicit algorithms then provide practical versions. For instance, Maximum Independent Set is MSO-expressible, so Courcelle guarantees it's FPT in treewidth; explicit DP solves it in O(2^w * n) which is much better than the tower.
Question 2 Short Answer
Iterative compression is an FPT technique: to find a solution of size k, first find any solution of size k+1, then 'compress' it to size k by removing vertices and re-optimizing. Why does this yield FPT algorithms, and for which problems is it particularly effective?
Think about your answer, then reveal below.
Model answer: Iterative compression often reveals structure unavailable to direct approaches. The algorithm finds a solution S of size k+1, then branches over subsets T of S with |T| = k, checking whether removing T and running a subroutine yields a valid solution not intersecting T. If the subroutine is polynomial, the compression step is FPT in k (2^k * poly(n) branches). This is particularly effective for vertex deletion problems like Feedback Vertex Set (remove k vertices to make the graph acyclic), where direct branching is hard but compression exploits the intermediate solution as a 'target.' For Feedback Vertex Set, iterative compression yields O(3^k * poly(n)), a major improvement over naive branching.
Iterative compression was discovered for Feedback Vertex Set but has since been applied to many vertex deletion problems. The technique shifts the search space from 'find k special vertices' to 'refine a known size-(k+1) solution' — a subtle but algorithmically powerful reframing.
Question 3 True / False
The lower bounds for kernelization state that certain problems (like Clique, parameterized by clique size) do not admit polynomial kernels (i.e., kernel of size poly(k)) under complexity assumptions. This suggests there is a fundamental gap between FPT algorithms and 'small' kernels.
TTrue
FFalse
Answer: True
A polynomial kernel would allow reducing an instance of size n to one of size k^c in polynomial time. If many problems had polynomial kernels, they could all be solved by: reduce to poly(k)-sized kernel in poly(n) time, then solve exhaustively in f(k) * poly(k) = f(k) * poly(k) time. But for problems like Clique (W[1]-hard), even FPT algorithms are believed unlikely to have polynomial kernels. The composition framework (by Bodlaender et al.) proves that k-Clique does not have a polynomial kernel unless the polynomial hierarchy collapses. This separates FPT from kernelizable: a problem can be FPT but hard to kernelize, meaning you cannot reduce the instance compactly even though you can solve it efficiently on small parameters.
Question 4 Short Answer
The algebraic techniques in FPT use rank arguments to prove lower bounds on kernel size. For instance, some parameterized problems are shown to have no small kernels by exhibiting a 'hard family' of instances whose kernel size lower-bounds are proved via matrix rank. What is the intuition for why rank-based arguments work?
Think about your answer, then reveal below.
Model answer: A kernelization algorithm accepts instances of arbitrary size n and outputs a kernel of size at most g(k). If you have a family of instances I_1, I_2, ..., I_m that are pairwise 'distinct' in a specific sense (no two can be in the same kernel without losing information), then any kernel must distinguish them, so the kernel has size at least the logarithm of the number of distinct instances. Using algebraic properties — representing instances as vectors and showing they are linearly independent over finite fields — researchers prove that certain instance families have super-polynomial size kernels required. The rank of the associated matrix lower-bounds the information content needed to distinguish instances, and thus the kernel size.
Rank-based kernelization lower bounds connect complexity theory to linear algebra, showing that some computational problems have intrinsic information requirements that cannot be compressed below poly(k) size.