Vertex cover decision problem ($(G,k):\tau (G)\le k$)

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.