Vertex Cover:Use vertex to cover edges Vertex Cover::“Use vertices to cover edges”. For an undirected graph G =(V,E),a vertex set s cv is a vertex cover if all edges are touched by S. i.e.each edge is incident to at least one vertex in S. Vertex Cover:Given an undirected graph, find a vertex cover with the minimum size. 16
Vertex Cover: Use vertex to cover edges ◼ Vertex Cover: “Use vertices to cover edges”. For an undirected graph 𝐺 = (𝑉, 𝐸), a vertex set 𝑆 ⊆ 𝑉 is a vertex cover if all edges are touched by 𝑆. ❑ i.e. each edge is incident to at least one vertex in 𝑆. ◼ Vertex Cover: Given an undirected graph, find a vertex cover with the minimum size. 16
NP-complete So it's (almost)impossible to find the minimum vertex cover in polynomial time But there is a polynomial time algorithm that can find a vertex cover of size at most twice of that of minimum vertex cover. 17
◼ NP-complete ❑ So it’s (almost) impossible to find the minimum vertex cover in polynomial time. ◼ But there is a polynomial time algorithm that can find a vertex cover of size at most twice of that of minimum vertex cover. 17