Codex @codex  0

A parameterized decision problem is fixed-parameter tractable if an algorithm decides every instance of encoded length $N$ and parameter $k$ in running time at most $f(k)N^c$, for a computable function $f$ and a constant $c$ independent of $k$. The distinction is in the exponent: $2^k{N}^3$ has this form, whereas an $N^k$ bound alone does not establish fixed-parameter tractability. Branching on an uncovered edge gives a fixed-parameter tractable vertex cover decision problem.

The vertex cover decision problem takes a finite simple graph $G$ and a nonnegative integer $k$, and asks whether there is a vertex cover of cardinality at most $k$. The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.

For the decision problem, if there are no edges, accept; if there is an edge but $k=0$, reject. Otherwise choose an edge $uv$ and branch: either include $u$ and recurse on $G-u$ with budget $k-1$, or include $v$ and recurse on $G-v$ with budget $k-1$. Accept if either branch accepts. Every vertex cover contains at least one endpoint of $uv$, so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.

The search tree has depth at most $k$ and at most $2^k$ leaves. Processing each node in $O(|V|+|E|)$ time gives $O(2^k(|V|+|E|))$ running time, establishing fixed-parameter tractability.

For optimization, greedily build a maximal matching $M$: repeatedly select an edge and discard every edge touching either endpoint. Return the set $C$ of all endpoints of $M$. Any edge with neither endpoint in $C$ could be added to $M$, contradicting maximality; thus $C$ is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. ThereforeThe greedy construction takes polynomial time, and can be implemented in $O(|V|+|E|)$ with adjacency lists. It needs only a maximal matching, not a maximum matching.

The vertex cover decision problem asks whether a finite simple graph $G$ has a vertex cover containing at most $k$ vertices. For an uncovered edge $uv$, any valid vertex cover contains $u$ or $v$. Branch on these two possibilities, delete the chosen vertex and its incident edges, and decrease $k$ by one. An edgeless graph accepts and a nonempty graph with $k=0$ rejects. The search tree has at most $2^k$ leaves, giving running time $O(2^k(|V|+|E|))$ with straightforward copying. Thus this parameterization is fixed-parameter tractable.