Let G (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is difficult in general; but here we'll see that it can be done efficiently if the graph is "simple" enough Call a graph G (V, E) a path if its nodes can be written as v1, v2,...,vn, with an edge between vi and vj if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight wi Consider, for example, the five-node path drawn in Figure 1. The weights are the numbers drawn inside the nodes The goal in this question is to solve the following problem Find an independent set in a path G whose total weight is as large as possible (a) Give an example to show that the following algorithm does not always find an independent set of maximum total weight The "heaviest-first" greedy algorithm t with S equal to the empty set Star while some node remains in G Pick a node v of maximum weight Add to S Delete and its neighbors from C Endwhile Return S (b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight Let S be the set of all1 v where i is an odd number Let S2 be the set of all v where is an even number (Note that Si and S2 are both independent sets) Determine which of Si or S2 has greater total weight, and return this one (c) Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights Figure 1: A paths with weights on the nodes. The maximum weight of an independent set is 14 6 Let G (V, E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is difficult in general; but here we'll see that it can be done efficiently if the graph is "simple" enough Call a graph G (V, E) a path if its nodes can be written as v1, v2,...,vn, with an edge between vi and vj if and only if the numbers i and j differ by exactly 1. With each node vi, we associate a positive integer weight wi Consider, for example, the five-node path drawn in Figure 1. The weights are the numbers drawn inside the nodes The goal in this question is to solve the following problem Find an independent set in a path G whose total weight is as large as possible (a) Give an example to show that the following algorithm does not always find an independent set of maximum total weight The "heaviest-first" greedy algorithm t with S equal to the empty set Star while some node remains in G Pick a node v of maximum weight Add to S Delete and its neighbors from C Endwhile Return S (b) Give an example to show that the following algorithm also does not always find an independent set of maximum total weight Let S be the set of all1 v where i is an odd number Let S2 be the set of all v where is an even number (Note that Si and S2 are both independent sets) Determine which of Si or S2 has greater total weight, and return this one (c) Give an algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights Figure 1: A paths with weights on the nodes. The maximum weight of an independent set is 14 6