Parameterized complexity studies how the difficulty of a computational problem depends on both the total input size and a chosen parameter, such as the number of changes allowed or the size of a requested solution. Its central practical question is whether a large problem becomes manageable when one meaningful feature remains small. A useful answer must identify that feature precisely and show where it appears in the running-time bound.
The gold standard is a correct algorithm with an explicit parameter, a proof that its reductions preserve the answer, and a realistic account of what its guarantee does and does not promise. This guide builds those habits through an original graph example: choosing a small set of vertices that touches every edge. You will trace a search, reduce an instance safely, check a returned solution and discover why a small parameter is helpful only when the right theorem applies.
Start with the Gold Standard collection or How X Works hub. The Computational Complexity Theory guide explains the wider resource-based perspective. The Education guide supplies our learning test: can you repair the reasoning when the assumptions change?
Choose your parameterized complexity route
Chapters 1–3: Understand the parameter
Chapters 4–6: Search and reduce
Chapters 7–9: Prove and connect
Chapters 10–12: Interpret and transfer
Chapter index
Understand the parameter · Chapters 1–3
1. Give the parameter a precise meaning
Search and reduce · Chapters 4–6
4. Replace unrestricted guessing with bounded branching
Prove and connect · Chapters 7–9
7. Turn preprocessing into a bounded kernel
Interpret and transfer · Chapters 10–12
10. Understand parameterized hardness without overstating it
Diagnose and practise · Chapters 13–14
Two measurements describe different things
Suppose a graph records pairwise conflicts among proposed activities. A vertex represents one activity and an edge says that its two endpoints cannot both remain in the selected collection. Removing a set of vertices that touches every edge leaves no recorded conflict among the remaining vertices. Such a set is a vertex cover. We ask whether a cover using at most k vertices exists.
The graph may have thousands of vertices, but the allowed number of removals might be five. These are different measurements. The input length describes the data that must be read. The parameter k describes the removal budget. An algorithm can exploit a small budget even when the graph itself is large, provided its expensive search depends principally on k.
This is a mathematical illustration, not a recommendation to remove real people, records or activities automatically. A conflict graph represents only the relationships supplied to it. If the actual problem includes priorities, protected activities, group conflicts or uncertain observations, the plain unweighted vertex-cover model may be inadequate. Establish the meaning of a vertex and an edge before trusting an answer.
Specify the question before the technique
Our graphs are finite, simple and undirected: no loops, no repeated edges, and no edge direction. The budget is a nonnegative integer. The decision question is whether a cover of size at most k exists. A search version must also return the vertices. An optimisation version asks for the smallest possible cover. These related tasks should not be silently interchanged.
A parameter is not necessarily a tuning knob in software. It may be a structural property, a threshold supplied in the question, or a quantity whose value must itself be found. A statement that an algorithm is fast for small treewidth, for example, is incomplete as an implementation plan unless it explains how the needed structural information is obtained. Counting that preparation is part of honest algorithm analysis.
CHAPTER 2 OF 14 · Understand the parameter
2. Read the difference between FPT and XP
Where the parameter occurs matters
Write N for the encoded input length. Fixed-parameter tractability, abbreviated FPT, means that some algorithm has a running-time bound f(k) times N raised to a constant power c. The function f must be computable and may grow rapidly. The crucial restriction is that c does not grow with k. Increasing the parameter may enlarge a separate factor, but it does not continually raise the input-size exponent.
Compare this with a bound such as N to the power k. For every fixed k this is polynomial in N, yet the exponent changes with the parameter. Such slice-wise polynomial bounds belong to the broader XP viewpoint. Merely saying “polynomial when k is fixed” misses the distinction that makes parameterized analysis useful.
For a numerical comparison, ignore constants and interpret the expressions only as illustrative operation counts. At N = 1,000 and k = 5, N to the power k equals 10 to the power 15. The expression 2 to the power k times N squared equals 32,000,000. These are not measured runtimes, and the two formulas need not describe equally optimised implementations. They show why separating the parameter from the polynomial exponent can matter.
A classification is not a stopwatch
FPT does not mean every small-looking parameter is practical. A factor of 2 to the power 100 is enormous. A factor with several nested exponentials may be unusable for much smaller values. Even a friendly parameter dependence can be outweighed by memory use, expensive preprocessing or large implementation constants. Read the actual bound before turning a classification into an engineering promise.
For formal definitions and the distinction between FPT and XP, see the Cornell introduction to parameterized complexity. When comparing methods, record the parameter, the input encoding and the required output next to each bound. Otherwise two algorithms that appear to solve the same problem may actually be answering different questions.
CHAPTER 3 OF 14 · Understand the parameter
3. Build a small graph whose answer can be checked
The running example
Use five vertices A, B, C, D and E. The edges are AB, AC, BC, CD and DE. The first three edges form a triangle on A, B and C; the final two extend a path from C through D to E. We ask whether a cover with at most three vertices exists, and then whether two vertices could suffice.
The set {A,C,D} covers every edge. AB touches A, AC touches A and C, BC touches C, CD touches C and D, and DE touches D. Its size is three. That gives an upper bound of three on the minimum cover size. Listing three vertices without checking every edge would not establish even this modest claim.
To prove that two vertices cannot suffice, first observe that a triangle requires at least two of its three vertices in any cover. Selecting only one leaves the edge between the other two uncovered. The separate edge DE requires D or E, neither of which belongs to the triangle. Therefore at least three vertices are necessary. The upper and lower bounds agree, so the minimum is exactly three.
Distinguish a certificate from an optimality argument
The three-vertex set certifies feasibility at budget three. It does not by itself prove that budget two fails. The triangle-plus-edge argument supplies that additional lower bound. Keeping these two pieces separate prevents a frequent error: finding a plausible answer and immediately calling it the best answer.
Try a misleading candidate, {A,B,D}. It actually is a valid cover: A and B cover the triangle, D covers CD and DE. Now try {A,C,E}; it is also valid. The minimum need not be unique. A correct solver can return any minimum cover unless the task includes a specified tie-break. A checker should reject invalid covers, not valid answers that differ from a favourite example.
CHAPTER 4 OF 14 · Search and reduce
4. Replace unrestricted guessing with bounded branching
Every uncovered edge creates a justified choice
Choose an uncovered edge uv. Any vertex cover must contain u or v, possibly both. This gives two branches: include u, delete u and its incident edges, and reduce the remaining budget by one; or do the corresponding operation with v. Solve the residual instance in each branch. Accept if at least one branch succeeds.
The rule is complete because every valid cover satisfies at least one of the two alternatives. It is sound because a cover of the residual graph, together with the chosen endpoint, covers the original graph. Notice that this is a logical disjunction, not an exclusive choice. Some covers appear in both branches, which is harmless for deciding whether a solution exists.
The base cases deserve equal care. If the remaining budget is negative, reject. Otherwise, if no edges remain, accept with the vertices already chosen. If edges remain and the budget is zero, reject. Testing an empty graph before detecting an overspent budget can incorrectly accept a branch that has selected too many vertices.
Trace the example at budget two
Branch on AB. In the A branch, the remaining edges are BC, CD and DE and the remaining budget is one. No single vertex touches all three edges: C misses DE, D misses BC, and every other vertex misses still more. This branch fails. In the B branch, the residual edges are AC, CD and DE. Again no single vertex covers all three, so it fails too.
At budget three, the A branch has two choices left. Selecting C removes BC and CD; selecting D then covers DE. The reconstructed cover is {A,C,D}. The trace exposes exactly why increasing the budget changes the answer. It also gives a small regression case for an implementation: budget two must fail, while budget three must succeed.
CHAPTER 5 OF 14 · Search and reduce
5. Prove the search bound and preserve branch state
Count the search tree
Each nonterminal branching step spends one unit of budget. A branch can therefore make at most k selections before either finishing or exhausting its allowance. With at most two children at each node, the full tree has no more than 1 + 2 + 4 + … + 2 to the power k nodes, which equals 2 to the power (k + 1) minus one.
At k = 3 the bound is fifteen nodes. At k = 10 it is 2,047. These are worst-case tree-size bounds for the simple branching scheme, not promises that every input reaches every node. Propagation, early success and contradictions often stop exploration sooner. A deliberately straightforward implementation that scans or copies a graph at each node has a bound of O(2^k times (n + m)), where n and m count vertices and edges.
The important conclusion is the separation: the exponential term depends on k, while graph processing is polynomial in the input. MIT’s fixed-parameter tractability notes discuss bounded search trees and kernelization as complementary techniques. Faster vertex-cover algorithms exist; this elementary version is valuable because its correctness and resource accounting are visible.
Restoration is part of correctness
When the A branch fails, the B branch must start from the parent graph, not the graph after A was deleted. Otherwise the implementation benefits from removals it has not paid for in the second branch. Copying a small state is an easy teaching implementation; reversible updates can be more efficient, but every change must be undone reliably.
This is the same discipline developed in the Constraint Satisfaction guide: distinguish deductions from assumptions and restore the parent state before exploring another case. Correctness depends on what remains true in each branch, not on whether one execution happens to produce an attractive answer.
CHAPTER 6 OF 14 · Search and reduce
6. Force high-degree vertices for a stated budget
A safe preprocessing rule
Suppose a vertex v currently has more than b distinct neighbours, where b is the remaining budget. If a cover excludes v, it must include every neighbour to cover the edges incident to v. That would require more than b vertices. Consequently every cover within the current budget must include v. Record v, remove it and its incident edges, and decrease b by one.
The inequality is strict. A vertex with degree exactly b is not necessarily forced. For a three-leaf star and budget three, selecting all three leaves covers every edge without choosing the centre. The centre provides a smaller cover, but that does not make it mandatory in every cover of size at most three.
After a forced selection, recompute the relevant degrees and compare them with the new remaining budget. Using the original budget after spending several selections weakens the rule and can invalidate a claimed size bound for the final reduced instance. The budget is part of the changing state, not a constant label to be copied through every step.
A complete reduction trace
Take a four-leaf star with centre H and leaves L1 through L4. Add a disjoint edge XY and allow two selections. H has degree four, greater than two, so H is forced. Remove H and its edges. The leaves become isolated; remove them because they cover no remaining edge. The residual problem is edge XY with budget one.
Selecting X solves the residual problem and reconstructs the original cover {H,X}. Selecting Y gives another valid reconstruction. The optimum is two because the star has an edge and the disjoint XY edge needs a separate endpoint. This example illustrates why a reduction log matters: the residual answer alone omits H and therefore does not cover the original star.
Small is a theorem, not an impression
A kernelization is a polynomial-time transformation of an instance and its parameter into an equivalent instance whose total size and parameter are bounded by a function of the original parameter. Equivalence means that the original decision answer is yes exactly when the reduced answer is yes. Deleting a few convenient rows is not a kernelization proof unless that equivalence and the size bound are established.
For our elementary vertex-cover procedure, repeatedly remove isolated vertices and apply the high-degree rule. If the budget becomes negative, the answer is no. Otherwise let b be the residual budget. Every remaining vertex has degree at most b. Any set of at most b vertices can then touch at most b squared edges, because the sum of their degrees is at most b times b.
If more than b squared edges remain, reject. Overlap among incident edges can only reduce how many distinct edges the selected vertices cover; it cannot rescue the bound. If at most b squared edges remain and isolated vertices have been removed, there are at most 2b squared vertices, since each remaining vertex is an endpoint of some edge.
What the bound guarantees
Because b never exceeds the original k, the residual graph has O(k squared) vertices and edges. Relabel the remaining vertices compactly and store the reconstruction mapping separately. This avoids allowing arbitrarily long original labels to masquerade as a small encoded instance. A formal kernel concerns representation size as well as the picture of a graph.
The Otago lecture on parameterized complexity presents this elementary quadratic bound. It is not the strongest known vertex-cover kernel. Jansen and Bodlaender’s research paper on vertex-cover kernelization discusses stronger bounds and refined parameters. The simple construction here remains useful because every deletion and rejection can be justified by an argument a learner can reproduce.
Forward preservation
Consider the high-degree rule again. Suppose the original residual graph has a cover S of size at most b and degree(v) exceeds b. We have proved that v belongs to S. Removing v from S leaves a set with size at most b minus one that covers every edge surviving deletion of v. Therefore an original yes-instance becomes a reduced yes-instance.
For the reverse direction, suppose the reduced graph has a cover T of size at most b minus one. Add v back. All deleted edges touched v, so they are now covered, and every surviving edge is covered by T. The reconstructed set has size at most b. This proves reduced yes implies original yes. Both directions are necessary; preserving only one can introduce false answers.
Removing an isolated vertex is simpler: it participates in no edge and is unnecessary for the at-most-budget question. However, if the requested output were every cover of exactly a specified size, isolated vertices could contribute to those outputs. A reduction safe for one question may need additional bookkeeping for another.
A reduction log is an explanation
Record the removed vertex, its degree at removal, the budget before and after, and the reason for the rule. At reconstruction, replay the required additions in a controlled order and check the final set against the original graph. This record is useful even for tiny examples because it distinguishes a logical consequence from an arbitrary simplification.
Do not claim that every convenient preprocessing rule preserves the entire set of optimal solutions. Our high-degree rule preserves the budgeted decision question and supports reconstruction of a feasible cover. Stronger statements about all solutions, uniqueness, weights or counting require separate proofs. A small, correctly stated guarantee is more useful than a broad claim that fails under a slightly different task.
CHAPTER 9 OF 14 · Prove and connect
9. Use matching as a lower bound and a special-case route
Disjoint edges require distinct selections
A matching is a set of edges with no shared endpoints. If a graph contains a matching of size r, every vertex cover has at least r vertices: each matching edge needs an endpoint, and one vertex cannot cover two of these disjoint edges. Thus a matching larger than the current budget immediately proves that the budget is insufficient.
In the five-vertex running example, AB and DE form a matching of size two. This proves only that the minimum cover is at least two. The actual answer is three. A lower bound can be valid without being tight. The triangle argument supplied the stronger conclusion in this particular graph.
A greedy maximal matching is one to which no further edge can be added; a maximum matching has the greatest possible size. These are different claims. Either gives a valid lower bound from its size, but a small maximal matching may miss a stronger bound available from a maximum matching.
Recognise when general search is unnecessary
For bipartite graphs, Kőnig’s theorem equates the maximum matching size with the minimum vertex-cover size. The existing Bipartite Matching specialist guide explains the assignment structure and this connection. A suitable polynomial-time matching method can therefore replace the general exponential search when the graph meets the bipartite assumptions.
The triangle in our example prevents that shortcut: a triangle is not bipartite. Applying the equality to an arbitrary graph is a substantive modelling error. On a triangle the maximum matching size is one and the minimum cover size is two. This tiny counterexample is an effective diagnostic for remembering the theorem’s domain.
CHAPTER 10 OF 14 · Interpret and transfer
10. Understand parameterized hardness without overstating it
A familiar problem can behave differently under another parameter
The fact that vertex cover is FPT in the cover budget does not mean every graph-selection problem is FPT in its requested solution size. The standard k-Independent Set problem, asking for at least k vertices with no edges between them, is W[1]-complete. This is evidence against an FPT algorithm under the usual assumption that FPT differs from W[1], not an unconditional proof that no such algorithm can exist.
The parameter belongs in the statement. Changing it can change the classification. For example, a procedure exponential in the number of vertices gives an FPT bound when that total vertex count is used as the parameter, but this says little about a large graph with a small solution budget. A useful parameter captures something expected to remain small in the intended instances.
Parameterized reductions must control the new parameter by a function of the old parameter, as well as preserve the answer and satisfy their time requirements. A classical reduction that produces a new budget depending on the entire original input size may not establish the parameterized hardness claim someone wants to make. Read what happens to k, not just what happens to the graph.
Hardness guides choices rather than ending investigation
If the chosen parameter has a conditional hardness barrier, practical responses include exploiting a different structural parameter, restricting the input family, changing the required output, or using heuristics with clearly stated limits. None of these actions changes the theorem. They change the question or the information available to the algorithm.
The Cornell reference gives a route into the W-hierarchy. For a first project, mastery does not require memorising every class. It requires recognising the logical status of the claim: an upper bound supplied by an algorithm, a conditional obstacle supplied by a reduction, and an empirical runtime observation are different kinds of evidence.
CHAPTER 11 OF 14 · Interpret and transfer
11. Choose a parameter that reflects the actual workload
Small budgets and small structure
A small repair budget is useful when the original instance is nearly acceptable. A structural parameter is useful when the interaction pattern has a restricted form. These are different reasons for tractability. A large star has many vertices but a cover of size one; a long path has simple structure but a minimum cover that grows with its length.
That contrast explains why no single parameter should be expected to describe every easy instance. If a method performs poorly because k is large, the graph may still have another property worth exploiting. Conversely, a small data file can contain a difficult combinatorial core. Total size remains important, but it is not the only useful predictor.
Before adopting a parameterized solver, inspect representative inputs. Record graph size, edge density, budget, reduction counts, residual size, explored nodes and memory use. Include failed searches and timeout cases. Reporting only successful small-budget cases can conceal how quickly the method deteriorates as the parameter grows.
Account for the whole pipeline
The elapsed work includes parsing, graph construction, parameter or decomposition discovery, preprocessing, search, reconstruction and validation. If graph construction compares every pair of records, that cost may dominate an efficient solver. An attractive search bound does not erase the work performed before the search begins.
Use the asymptotic analysis to form a hypothesis, then test the implementation on the intended workload. Keep the worst-case guarantee and measured behaviour side by side. A heuristic can outperform a guaranteed algorithm on a particular collection, but successful trials do not prove completeness. A guaranteed algorithm can also be too slow for a deadline despite eventually returning the correct answer.
CHAPTER 12 OF 14 · Interpret and transfer
12. Transfer the reasoning when the problem changes
Change one assumption at a time
Return to the four-leaf star. With unit costs and a budget of two vertices, its centre is forced by the degree rule. Now assign the centre a cost of ten and each leaf a cost of one, and minimise total cost. Selecting all four leaves costs four, while selecting the centre costs ten. The unit-count rule cannot be reused as a cost-optimality argument.
This does not contradict the original proof. The original proof counted how many vertices a cover used, not their total weight. The modified task needs a weighted formulation and rules justified for that formulation. The correct transfer is to identify the changed assumption and rebuild the argument, rather than keeping the same deletion because the picture looks familiar.
Next replace pairwise conflicts with a requirement that at least one member of each specified triple must be removed. The natural object is a hypergraph and the covering task is a hitting-set problem. Branching on the members of an uncovered triple gives three alternatives, not two. If every set has size at most three, the elementary depth-k branching tree has at most three children per step; if set sizes are unbounded, that branching factor is no longer a constant independent of the input.
Change the requested output
Suppose the user asks for all minimum covers of the five-vertex example. A decision algorithm that returns after its first successful branch is insufficient. The two branches may also produce the same cover, so enumerating outputs requires duplicate handling. Proving existence, finding one witness, finding an optimum and enumerating all optima are different contracts.
Finally add one isolated vertex F and ask for covers of exactly four vertices. F can now appear in valid outputs even though it covers no edges. Removing isolated vertices remains safe for the earlier at-most-budget decision question, but output reconstruction must change for this new task. These exercises test whether you understand why a rule works rather than merely remembering its name.
CHAPTER 13 OF 14 · Diagnose and practise
13. Diagnose mistakes and answer common questions
Why is my supposedly safe reduction rejecting valid cases?
Check whether the high-degree condition uses greater than rather than greater than or equal to. Test the three-leaf star at budget three: the leaves form a valid cover without the centre. Then check whether the remaining budget decreases after a forced choice. Finally verify that the input graph really is simple and that repeated records are not being counted as distinct neighbours.
Why does the returned cover fail on the original graph?
The likely causes are a lost reconstruction record, leaked branch state or validation against the reduced graph only. Preserve the original edge list. Independently check every original edge for at least one selected endpoint, check that every selected label is a real vertex, and count distinct selected vertices against the original budget. A duplicate label must not be treated as two different choices.
Does a small kernel mean the answer is yes?
No. It means the remaining question has bounded size. A triangle at budget one is small and still impossible. Conversely, if the elementary size test rejects because more than b squared edges remain after all degree reductions, that is a proved no-answer under the stated assumptions. It is not merely a warning that the instance looks too large.
Does FPT imply a polynomial-size kernel?
No. The standard relationship between FPT and kernelization permits a kernel-size bound that is an arbitrary computable function of the parameter. Requiring a polynomial function of k is a stronger demand. Keep the phrase “polynomial-time preprocessing” separate from “polynomial-size kernel”: the first refers to transformation time, the second to the parameter dependence of output size.
What should a timeout report say?
It should say that the search did not finish within the resource limit, unless an independently valid certificate already settles the requested question. A feasible cover found before timeout can establish yes for that budget. Failure to find one does not establish no. For optimisation, distinguish a best-known cover from a proved minimum and report any valid lower bound separately.
CHAPTER 14 OF 14 · Diagnose and practise
14. Build an independent four-week learning project
Week one: model and certify
Draw the five-vertex graph and list every subset of its vertices. Check each subset against the five edges and record the smallest valid size. Compare the result with the triangle-plus-edge lower bound. Then repeat with a star, a path, a triangle and an empty graph. The point is to build a small trusted reference set before adding cleverness.
Write the input contract beside the results: simple undirected graph, unit vertex costs, at-most budget, one witness required. Each later experiment should identify whether it preserves that contract. This makes errors easier to locate because a changed model will not be confused with a faulty implementation of the old model.
Week two: implement and test branching
Implement the two-endpoint branching rule with explicit base cases and reliable state restoration. Compare its yes/no result with exhaustive enumeration on every labelled simple graph up to a small vertex count, for several budgets. Validate every witness independently. Include budget zero and empty graphs, where poorly ordered base cases often fail.
Instrument node counts. Predict the full binary-tree bound and compare it with actual visits. Explain why some instances terminate much earlier. Do not adjust the correctness test to match the solver’s favourite answer: different valid witnesses are acceptable when the contract requests only one.
Week three: reduce and reconstruct
Add isolated-vertex deletion, forced high-degree selections and the residual edge-count rejection. Log every reduction. Compare the decision result before and after preprocessing, then reconstruct and validate a cover against the original graph. Use the star-plus-edge example as a hand-worked trace and tiny exhaustive graphs as a broader consistency check.
For each rule, write the forward and reverse proof in your own words. Search for a counterexample after deliberately weakening an assumption, such as changing the strict degree inequality or switching to weighted costs. Finding the boundary of a rule is a stronger demonstration of understanding than reproducing only its successful example.
Week four: compare methods and explain limits
Compare enumeration, branching and preprocessing-plus-branching across graphs with different sizes and budgets. Include bipartite instances and investigate the matching-based alternative using the linked specialist guide. Report preparation, solving and checking costs separately, together with the parameter values and machine conditions used in the experiment.
Finish with a short explanation that another learner can audit: what the parameter means, why every branch is necessary, why every deletion is safe, how the kernel bound is obtained and how the final answer is checked. The durable skill is recognising which part of a large problem causes the combinatorial explosion, then proving that a chosen method confines or avoids it under explicit assumptions.