算法高级教程3.4Thecoveringproblem.pptVIP

The vertex-cover problem The set covering problem The covering problem The vertex-cover problem Optimization problem: Given an undirected graph G = (V, E), find a minimum subset V of V such that if (u, v)∈E, then u∈V or v ∈V (or both). Decision Problem: Given an undirected graph G = (V, E) and an integer k, is there a subset V with size at most k? Maximal Matching Heuristic ApproxVertexCover(G) 1 C ← ? 2 E ← E[G] 3 while E ≠ ? do 4 let (u, v) be an arbitrary edge of E 5 C ← C∪{u, v} 6 remove from E every edge incident on either u or v 7 return C b c d g a e f b c d g a e f b c d g a e f b c d g a e f (a) (b) b c d g a e f b c d g a e f (c) (e) (f) (d) Theorem ApproxVertexCover(G) is a polynomial-time 2-approximation algorithm. Proof. The set C of vertices that is returned by ApproxVertexCover(G) is a vertex cover, since the algorithm loops until every edge in E[G] has been covered by some vertex in C. To see that ApproxVertexCover(G) returns a vertex cover that is at most twice the size of an optimal cover, let A denote the set of edges that were picked in line 4 of pproxVertexCover(G). In order to cover the edges in A, any vertex cover-in particular, an optimal cover OPT(I)-must include at least one endpoint of each edge in A. No two edges in A share an endpoint, since once an edge is picked in line 4, all other edges that are incident on its endpoints are deleted from E′ in line 6. Thus, no two edges in A are covered by the same vertex from OPT(I), and we have the lower bound |OPT(I)|≥|A| on the size of an optimal vertex cover. Each execution of line 4 picks an edge for which neither of its endpoints is already in C, yielding an upper bound (an exact upper bound, in fact) on the size of the vertex cover returned: |C|=2|A|. so, A(I)=|C| = 2|A|≤ =2OPT(I), thereby proving the theorem. Greedy Heuristic Pick a node u with maximum degree (it covers the most edges), add it to