The vertex cover problem asks: does graph G have a vertex cover of size at most k? The bounded search tree algorithm solves this in O(2^k * n) time. Why is this fundamentally different from O(2^n) exhaustive search?
A2^k * n is always less than 2^n
BWhen k is small relative to n (e.g., k = 20 in a million-vertex graph), 2^k * n ≈ 10^6 * 10^6 = 10^12 is tractable, while 2^n is astronomical — the exponential blowup is confined to the parameter k, not the input size n
CThe bounded search tree algorithm uses polynomial space while exhaustive search uses exponential space
DThe bounded search tree algorithm always finds the optimal solution while exhaustive search may not
The key insight of FPT is that the exponential dependence is on the PARAMETER k, not the input size n. For vertex cover of a network with n = 10^6 vertices and k = 20, the FPT algorithm does about 10^6 * 2^20 ≈ 10^12 operations — feasible on modern hardware. Exhaustive search over all subsets of size 20 does C(10^6, 20) ≈ 10^99 operations — utterly infeasible. The FPT framework recognizes that many real-world instances have small parameter values, making the exponential dependence on k acceptable.
Question 2 True / False
Every NP-hard problem parameterized by its solution size is Fixed-Parameter Tractable.
TTrue
FFalse
Answer: False
This is the central negative result of parameterized complexity. The W-hierarchy classifies problems by their likely parameterized intractability. Clique parameterized by clique size k is W[1]-complete — believed not to be FPT. If k-Clique were FPT (solvable in f(k) * n^O(1) time), then every problem in W[1] would be FPT, which is believed false (analogous to P != NP for classical complexity). Other W[1]-hard problems include Independent Set (parameterized by solution size), k-Path, and k-Dominating Set. The distinction: vertex cover is FPT while clique and independent set are W[1]-hard, despite all being NP-hard.
Question 3 Short Answer
Explain what treewidth measures and why it makes NP-hard problems tractable.
Think about your answer, then reveal below.
Model answer: Treewidth measures how close a graph is to being a tree. A tree decomposition maps a graph into a tree of 'bags,' where each bag contains a subset of vertices, every edge is contained in some bag, and for each vertex the bags containing it form a connected subtree. Treewidth is the maximum bag size minus 1. Trees have treewidth 1; complete graphs have treewidth n-1; planar graphs have treewidth O(sqrt(n)). NP-hard problems become tractable on bounded treewidth because dynamic programming on the tree decomposition processes the graph one bag at a time, with state space exponential only in the bag size (treewidth). For example, maximum independent set on graphs of treewidth w is solvable in O(2^w * n) time — the DP tracks which subset of each bag is in the independent set, and the tree structure ensures only O(w) vertices interact at each step.
Courcelle's theorem generalizes this: every graph property expressible in monadic second-order logic is decidable in f(w) * n time on graphs of treewidth w. This is a sweeping meta-theorem — it shows that treewidth captures a fundamental barrier to computational hardness for graph problems.
Question 4 True / False
A kernelization algorithm for k-Vertex Cover produces an equivalent instance with at most 2k vertices. This kernel is known to be essentially optimal: no polynomial-time algorithm can produce a kernel with (2-epsilon)k vertices unless the polynomial hierarchy collapses.
TTrue
FFalse
Answer: True
The classical Crown Reduction and Buss kernelization for vertex cover produce a kernel with at most 2k vertices and k^2 edges. This means a million-vertex graph with a minimum vertex cover of size 100 can be reduced to at most 200 vertices in polynomial time, after which any algorithm (even brute force) runs fast. The lower bound of (2-epsilon)k vertices (under complexity-theoretic assumptions) shows this is essentially tight. Kernelization lower bounds use the framework of cross-composition and are one of the major tools in parameterized complexity theory.