Given a graph G(V,E) a set I is an independent set if for every u, v...

 

Transcribed Image Text:

Given a graph G(V,E) a set I is an independent set if for every u, v I, uv, uv E. A Matching is a collection of edges {e;} so that no two edges in the matching share a common vertex. A vertex cover is a collection U CV of vertices so that for every edge uv E either u EU or v EU. 1. Show that the largest size matching in a graph is no larger than the size of an arbitrary vertex cover in the graph. 2. Show that if I is an independent set then G(V - I) (namely, the graph with vertices V-I, restricted to edge with both endpoints in V - I is) a Vertex Cover. 3. Give an example for a graph so that the Maximum Matching is strictly smaller than the minimum Vertex Cover 4. A clique is a collection C of vertices U so that for every u, v C, uv E. Say that we are given an algorithm that finds a clique of maximum size in time f(n). Give an O(n) + f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graph Given a graph G(V,E) a set I is an independent set if for every u, v I, uv, uv E. A Matching is a collection of edges {e;} so that no two edges in the matching share a common vertex. A vertex cover is a collection U CV of vertices so that for every edge uv E either u EU or v EU. 1. Show that the largest size matching in a graph is no larger than the size of an arbitrary vertex cover in the graph. 2. Show that if I is an independent set then G(V - I) (namely, the graph with vertices V-I, restricted to edge with both endpoints in V - I is) a Vertex Cover. 3. Give an example for a graph so that the Maximum Matching is strictly smaller than the minimum Vertex Cover 4. A clique is a collection C of vertices U so that for every u, v C, uv E. Say that we are given an algorithm that finds a clique of maximum size in time f(n). Give an O(n) + f(n) time algorithm to find the maximum independent set and the minimum vertex cover in the graph