83
Vertex Cover
(cont)
Theorem.
The approximation algorithm returns a vertex cover
at most twice the size
of an optimal cover.
Proof.
Any (optimal) cover must include at least one endpoint of each chosen edge.
Cost analysis …
repeatedly select an edge from
E
add endpoints to
C
delete all edges in
E
covered by endpoints
Time complexity:
O(V+E)
(adjacency list representation)
![[prev]](icon/prev.gif){kind=icon}
83
![[next]](icon/next.gif){kind=icon}