CS 573: Algorithms, Fall 2013

Document Content and Description Below

. Greedy algorithm do not work. (40 pts.) Anaturalalgorithm, GreedyIndep, forcomputingmaximumindependentsetinagraph, istorepeatedly remove the vertex of lowest degree in the graph, and add it to the i... ndependent set, and remove all its neighbors. (A) (5 pts.) Show an example, where this algorithm fails to output the optimal solution. Solution: Consider the example depicted below. The algorithm would choose the vertex 1 and one vertex out of 4,5,6, or 7. Namely, generating an independent set of size two. However, the maximal independent set has size three; namely, {2,3,7}. 1 2 3 4 5 6 7 (B) (5 pts.) Let G be a (k,k +1)-uniform graph (this is a graph where every vertex has degree either k or k +1). Show that the above algorithm outputs an independent set of size Ω(n/k), where n is the number of vertices in G. Solution: Since G is (k,k+1)-uniform, at most k+2 vertices are removed from the graph on each iteration of the algorithm. Therefore, it takes at least n k+2 to all vertices to be removed from the graph. This means that the algorithm outputs an independent set of size Ω(n/k). This argument implies a more general result. If the maximum degree in the graph G is ∆, then there is an independent set in G of size |V(G)|/(∆+1). (C) (5 pts.) Let G be a graph with average degree δ (i.e., δ = 2|E(G)|/|V(G)|). Prove that the above algorithm outputs an independent set of size Ω(n/δ). Solution: Form a new graph G′ by removing all vertices in G that have degree greater than 10δ. Let U be the number of vertices in G that are of degree larger than 10δ. Clearly, 10δ ·U ≤ 2|E(G)|≤ nδ, which implies that U ≤ n/10. Thus, at most n/10 vertices are removed from G when creating G′. Now, an independent set in G′ will be an independent set in G. Since all vertices in G′ have degree at most 10δ, the same argument as in part (B) can be used to show that our algorithm outputs an independent set for G′ of size Ω(|V(G′)| 10δ )=Ω(0.9n 10δ)=Ω(n δ) [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages