= Solution
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 \b[$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. Therefore
$$
\boxed{|C|=2|M|\leq2\tau(G)=2\operatorname{OPT}.}
$$
The 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>.
Back to article page
