12.5

Let the DFS visit the graph and let T be the resulting DFS-tree. Denote by C the set of internal (non-leaf) vertices of T. 1. C really is a vertex cover • If an edge e is a tree-edge of T, its parent endpoint lies in C, so e is covered. • If e is a back/forward/cross edge, one endpoint is an ancestor of the other in T; every ancestor is internal, hence also covered. 2. |C| ≤ 2·OPT –– a 2-approximation Build a matching M that uses (at least) half of the vertices of C. M ← ∅ , S ← ∅ # vertices that are already incident to M for every vertex v in preorder of T: if v ∉ S and v has a child u in T: add edge (v,u) to M S ← S ∪ {v,u} • Every time the loop adds an edge (v,u) it “consumes” at most two internal vertices (v and possibly u) and places one edge into M. • Thus after processing all vertices we have     |M| ≥ |C| ⁄ 2. • Since the edges of M are disjoint, any vertex cover – in particular the optimum cover OPT – must contain at least one endpoint of every edge of M, so     OPT ≥ |M| ≥ |C|⁄2. Rearranging gives |C| ≤ 2·OPT. 3. Tightness On an n-vertex path the algorithm selects n−1 internal vertices, whereas OPT = ⌊n⁄2⌋, so the factor 2 cannot be improved. Therefore deleting the leaves of a DFS-tree yields a vertex cover whose size is never more than twice the size of an optimal cover.

Back to Chapter 12