Reference no: EM13164825
Let G = (V,E) be an undirected graph with nnodes. Recall that a subset of the nodes is called an independentset if no 2 of them are joined by an edge. Finding largeindependent sets is difficult in general; but here we'll seethat 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 vjif and only if the numbers i and j differ by exactly 1. With eachnode vi, we associate a positive integer weightwi.
Consider for example the five-node path drawn below. The weightsare the numbers drawn inside the nodes, and the total weight is14.
The goal in this question is to solve the following problem: Findan independent set in a path G whose total weight is as large aspossible.
For the exercises(a) and (b), give your counterexample. For the exercise (c), showthe optimal structure (with an explanation), give the bottom-updynamic programming algorithm, and show the running-timeanalysis.
a) Give an example to show that the followingalgorithm does not always find an independent set of maximum totalweight.
The "heaviest-first" greedy algorithm
Start with S equal to the empty set
While some node remains in G
Pick a node vi of maximum weight
Add vi to S
Delete vi and its neighbors from G
Endwhile
Return S
b) Give an example to show that the following algorithm alsodoes not always find an independent set of maximum totalweight.
Let S1 be the set of all vi where i is an odd number
Let S2 be the set of allvi where i is an even number
(Note that S1 and S2 are bothindependent sets)
Determine which of S1 or S2 hasgreater total weight, and return this one
c) Give an algorithm that takes an n-node path G with weightsand returns an independent set of maximum total weight. The runningtime should be polynomial in n, independent of the values of theweights