Vertex Cover Instance:An undirected graph G(V,E). Find the smallest C Vthat intersects all edges. Linear Program(LP)relaxation: minimize ∑x v∈V subject to ∑x≥1， e∈E v∈e x∈[0,1]， v∈V fractional domains linear programs are solvable in polynomial time!• Linear Program (LP) relaxation: Vertex Cover Instance: An undirected graph . Find the smallest that intersects all edges. G(V, E) C ⊆ V minimize subject to ∑ v∈V xv ∑ v∈e xv ≥ 1, xv ∈ {0,1}, e ∈ E v ∈ V • linear programs are solvable in polynomial time! [ ] fractional domains