Lesson · Intractability and Approximation · Exact answers, still exponential

Parameterising the Budget

An exponential does not have to be an exponential in the size of the input. Ask whether a graph has a vertex cover of size at most k and there is a search tree of depth k: one end of an uncovered edge must be in the cover, so branching costs a factor of two per unit of budget and the size of the graph enters only as the cost of scanning for an edge. The lab prints 2^k · n against 2^n with both computed, and on one of its examples the first is larger.

Open the interactive lesson Practice

an uncovered edge uv: one of u, v is in the cover — there is no third option so branch on it, spend 1 of the budget either way, and the depth is at most k six-cycle, k = 3: a cover of 3 exists, 2 does not 9 nodes opened against a tree bound of 16, and the answer is right 2^k · n = 48 against 2^n = 64 on two triangles with k = 4: 2^k · n = 96 against 2^n = 64

A tree whose depth is the budget, and the two work figures side by side

Core ideas

What this lesson establishes

The first idea is the branching rule, which is a two-line argument and the whole method. The second is what “fixed-parameter tractable” asks for, which is a shape of running time rather than a speed. The third is the instance where the shape does not pay.

One end or the other, and no third option

Take an edge whose ends are both still uncovered. Any vertex cover must contain u or v, because the edge has to be touched and there is nothing else touching it. That is a complete case split, so branching on it loses no solution, and each branch has spent one unit of the budget. After k levels the budget is gone: if some uncovered edge remains the branch fails, and if none does the branch has a cover. The depth of the tree is the budget and not the graph.

Fixed-parameter tractable is a shape, not a speed

A problem is fixed-parameter tractable in a parameter k when it can be solved in time f(k) times a polynomial in the input size, for some function f depending on k alone. Here f(k) = 2^k and the polynomial is the cost of scanning the edges, so the running time is about 2^k · n. Nothing in that says the algorithm is fast: f is allowed to be monstrous. What it says is that the exponential has been moved off the input size and onto a quantity that may be small in practice.

The shape does not pay at every parameter

The panel prints 2^k · n and 2^n as two integers. On the six-cycle with k = 3 they are 48 and 64, so parameterising wins narrowly. On the two-triangles example with k = 4 they are 96 and 64, so it loses: the cover needs four vertices in a graph with six, and a budget almost as large as the graph buys nothing. Parameterising is worth doing when the parameter is genuinely small, and whether it is is a fact about your instances rather than about the method.

The material

The branching rule, the tree bound, and the two work figures

The rule, why it is exhaustive, the bound on the tree, what the lab counted at each budget, and the instance where the method costs more than brute force.

Definition · The parameterised problem

Vertex cover, parameterised by solution size: given a graph and an integer k, is there a vertex cover with at most k vertices? The parameter is k, chosen by whoever asks the question, and the algorithm's running time is allowed to depend on it in any way at all provided the dependence on the graph is polynomial.

Theorem · The bounded search tree is correct, and its depth is k

The branching algorithm returns a cover of size at most k if one exists and reports failure otherwise, and it opens at most 2^(k+1) nodes.

For correctness, induct on the budget. With budget 0 the algorithm succeeds exactly when no edge is uncovered, which is right. With budget b > 0, if no edge is uncovered the current set is already a cover. Otherwise pick an uncovered edge uv; every cover of size at most b more contains u or v, so one of the two recursive calls sees a sub-problem with a solution whenever the current node has one, and by induction finds it.

For the size, the recursion branches into two children and decreases the budget by one, so the tree has depth at most k and at most 2^(k+1) - 1 nodes. The work at each node is a scan for an uncovered edge, which is linear in the number of edges, so the whole search costs O(2^k · m).

□

What the lab counted

The loaded graph is the cycle on six vertices with k = 3. The panel reports a cover of size 3 — vertices 1, 3 and 5 — an exhaustive optimum of 3, the answer correct, 9 nodes opened, a tree bound of 16, and 2^k · n = 48 against 2^n = 64. Moving the budget down one at a time gives the shape of the search: k = 0 fails in 1 node, k = 1 fails in 3, k = 2 fails in 7, and k = 3 succeeds in 9.

Two of those numbers are worth pausing on. At k = 2 the search opens 7 nodes against a bound of 8 and fails, which is the bound almost exactly attained: when there is no cover the tree is explored in full. At k = 3 it opens 9 against a bound of 16, because it stops at the first cover it finds and does not enumerate the rest. Success is cheaper than failure here, and that is typical of a search with no bound to prune with.

Example · A budget that settles a graph of any size

Load the star on eight vertices with k = 1. The hub covers every edge, so one unit of budget suffices, and the panel reports 3 nodes against 2^k · n = 16 and 2^n = 256. A star with forty leaves would open the same 3 nodes, because the tree's depth is the budget and the graph enters only through the scan — though that is an argument rather than a measurement, since the panel's parser stops at eight vertices. That is the whole promise of parameterising, on the instance where it is most visible.

And the instance where it does not pay

Load the two disjoint triangles with k = 4. Each triangle needs two vertices covered, so 4 is the smallest budget that works, and 4 is large relative to the graph's 6 vertices. The panel prints 2^k · n = 96 against 2^n = 64: the parameterised bound is worse than checking every subset. The search still only opens 9 nodes, which is the honest measurement, but the two work figures are the ones that generalise and one of them is losing.

This is the same reading discipline as the previous page in a new costume. 2^k · n and 2^n are expressions evaluated at the instance on screen; they are not measurements, and the panel labels them as the expressions they are. The node count is the measurement. Neither is a claim about the other, and the interesting cases are exactly the ones where they disagree.

One thing this course does not build: kernelisation, where the instance itself is shrunk to a size depending only on k before any search begins. A vertex of degree above k must be in any cover of size k, which is the first reduction rule, and there are others that leave a graph with O(k^2) edges. It is the other half of parameterised algorithms and it is named here rather than demonstrated.

Interactive

Parameterised: a search tree of depth k, whatever n is

One end of an uncovered edge must be in the cover, so the tree has 2^k branches and the graph's size enters only as a scan

Move the budget and watch the two work columns separate

Every budget from 0 upwards is run, and each answer is checked against an exhaustive search over the subsets. The last two columns are the point: one doubles with the budget and the other is fixed by the graph, and they cross where parameterising stops being worth it.

Worked example

Edges, as u-v

The budget k3

Step through the branchings1

Vertices and edges—

Is there a cover of size k—

The cover it found—

The optimum, by exhaustive search—

The answer is right—

Nodes the search opened—

The tree bound, 2 to the k plus one—

2 to the k times n, against 2 to the n—

Find any edge neither of whose ends is covered yet. One of the two must be in the cover — there is no third option — so branch on that, spending one unit of budget either way. The tree is therefore at most 2^k deep-branching nodes no matter how large the graph is, and the size of the graph only enters as the cost of scanning for an uncovered edge. That is what parameterising buys: the exponential is in k and not in n.

Method

Choosing a parameter, and checking it is doing work

The method is mechanical. Deciding whether it helps is a measurement on your instances.

Find a complete case split with few cases

The branching rule must cover every possibility: one end of an uncovered edge, or the other. A rule with a case missing loses solutions silently, and a rule with many cases gives a bigger base for the exponential. Two is the smallest interesting number and it is what this problem gives.

Check that every branch spends budget

The depth bound is the budget, so a branch that recurses without decreasing k destroys it and the search may not terminate. This is the invariant to state explicitly, and it is what makes the tree bound a bound rather than a hope.

Compare the two work figures at your own parameter

Evaluate 2^k · n and 2^n on the instance you actually have. If the parameter is a constant fraction of the input size, parameterising is not buying anything, and the panel has an example where it is measurably worse.

Check the answer against an exhaustive optimum

The bounded search answers a yes-or-no question about a budget, so it can be right for the wrong reason. The lab computes the true minimum cover separately and requires the search to say yes exactly when that minimum is at most k, at every budget the slider covers.

Say which numbers were counted and which were evaluated

The node count was counted. 2^k · n and 2^n are expressions evaluated at this instance's numbers. Mixing the two produces sentences of the form “the algorithm did 48 units of work”, which nothing on the page measured.

Parameters, trees and two kinds of number

Score 0 / 0

Choose the answer you can justify.

The six-cycle at four budgets

The graph is 1-2, 2-3, 3-4, 4-5, 5-6, 6-1, and the exhaustive minimum cover has 3 vertices. One row per budget: whether a cover of that size exists, how many nodes the search opened, and the bound on the tree.

k cover of size k? nodes opened tree bound 2^(k+1) 2^k · n 0 no 1 2 6 1 no 3 4 12 2 no 7 8 24 3 YES 9 16 48 4 yes 9 32 96 2^n for this graph 64 exhaustive minimum cover 3 vertices {1, 3, 5} the search says yes exactly when the minimum is at most k every k two disjoint triangles instead, k = 4: nodes 9, 2^k · n = 96, 2^n = 64 the parameter is too large to pay

The failing budgets are the expensive ones. At k = 2 the search opens 7 nodes against a bound of 8, which is the tree explored almost in full — there is no cover to find, so every branch runs to the bottom of its budget before failing. At k = 3 it opens 9 against a bound of 16 and stops at the first cover, so the extra budget costs almost nothing.

The rows at k = 3 and k = 4 have the same node count and different work figures, which is the distinction this page keeps insisting on. The search did the same amount of work in both because it found a cover at the same depth; the expression 2^k · n doubled because k did. One of those is a fact about the run and the other is a fact about the formula.

For a faded rehearsal, load the path on seven vertices with k = 3 and predict the node count before running it. The supplied first move: a path with six edges needs three interior vertices, so the budget is exactly enough and the search cannot afford a single wrong turn. Say whether you expect the count to be nearer 9 or nearer the bound of 16, and then check.

Common mistakes

Reading fixed-parameter tractable as fastThe definition permits any dependence on the parameter whatever, and for some problems f(k) is a tower of exponentials. What the definition buys is that the input size appears polynomially, which is a structural statement about where the hardness lives.

Quoting 2^k · n as work doneIt is an expression evaluated at two numbers from the instance, and the panel prints it beside a node count that was actually measured. On the six-cycle they are 48 and 9. Naming which is which is the difference between a measurement and a label.

Choosing a parameter without checking it is smallVertex cover parameterised by solution size is a good idea when covers are small and a bad one when they are half the graph. The two-triangles example is the smallest case where the method measurably loses, and the check costs one evaluation of two expressions.

Check your understanding

✓

Finish when you can design a bounded search tree and say at which parameter it stops paying.

You should be able to state a complete case split, prove every branch spends budget, derive the 2^(k+1) node bound, check the yes-or-no answer against an exhaustive minimum at every budget, and evaluate 2^k · n against 2^n on your own instance before recommending the method.

Note: Exactness has been kept in both of the strategies so far, and paid for in an exponential. Everything after this page gives up exactness instead, and the first question is what a guarantee can possibly be a guarantee against when nobody knows the optimum.