I am working on this problem from the book, Data Structures & Algorithm Analysis in C++.
The problem is:
9.40 Give a polynomial-time algorithm that finds ceil(V /2) vertices that collectively cover at least three-fourths (3/4) of the edges in an arbitrary undirected graph.
The solution from the manual is as follows:
Use a greedy algorithm: At each step, choose the vertex with the highest connectivity to vertices not already chosen. Proof that only 1/4 of the edges are not touched can be done with a straightforward calculation of edges that remain after each step. With E edges and V vertices, the total connectivity is 2E at the start, so at most (V - 2)/V of the edges remain after the first step. Then at most (V - 3)/(V - 1) of those edges remain after the second step, and so on. Multiply it out, and you get about 1/4 of the edges remaining.
I cannot get to the last step. Here is my work:
Total connectivity is 2E.
In first step we take out the vertex the highest connectivity to vertices not already chosen. We know that it has to have at least connectivity equal to average which is the total connectivity divided by the # vertices 2E/V.
Step 1:
Multiply 2E/V by 2 for sake of both in and out
2E - 2*(2E/V)
= E(V-2/V)
this means that at most (V - 2)/V of the edges remain after the first step.
Step 2:
Vertices count jumped by one and connectivity is now what was calculated by above
E(V-2/V) - 2( E(V-2/V) / V-1)
= E((V-3)(V-2)/V(V-1))
at most (V - 3)/(V - 1) of those edges remain after the second step
Then Step 3:
...
= E((V-4)(V-3)/ (V(V-1)) )
So how do I get to the final number of 1/4. Every further iteration gives me something of the form:
Say step number = stepNum
= E (V-(stepNum+1))(V-stepNum) / (V*(V-1))
I do not see where the 1/4 comes from. Help would be greatly appreciated!
1 answer
2 answers