= Vertex cover decision problem
{title2=$(G,k):\ \tau(G)\leq k$}
= VertexCover
{c}
{synonym}
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>.
Back to article page
