= Depth-first approximation for connected vertex cover
{title2=$|I|\leq2\,\mathrm{OPT}$}
For a nontrivial <connected graph>, return the <internal vertices of a rooted tree> in a <depth-first search> tree. Undirected <depth-first search> has only ancestor-descendant <edges>, so every <edge> meets an internal <vertex>; the internal <vertices> are connected along parent paths. For a maximum-size <proper matching in a rooted tree> $M$ of that tree, existence of which is assumed, $|I|=|V|-|L|\leq|V|-|U(M)|=2|M|$. Every <vertex cover> has size at least $|M|$, proving the factor two. The implementation needs only <depth-first search>, hence linear <time complexity>; it does not compute the analysis <matching in a graph>.
Back to article page
