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!
Please delete this post! I have been able to figure it out. Thanks :)
To get to the final number of 1/4, let's analyze the equation you derived for each step:
E((V - stepNum - 1)(V - stepNum) / (V*(V - 1)))
Let's expand and simplify this equation step by step:
Step 1:
E((V - 2)(V - 1) / (V*(V - 1)))
= E(V - 2) / V
Step 2:
E((V - 3)(V - 2) / (V*(V - 1)))
= E(V - 3)(V - 2) / (V*(V - 1))
= E(V^2 - 5V + 6) / (V*(V - 1))
Step 3:
E((V - 4)(V - 3) / (V*(V - 1)))
= E(V^2 - 7V + 12) / (V*(V - 1))
In the general case, for Step "stepNum":
E((V - stepNum - 1)(V - stepNum) / (V*(V - 1)))
= E(V^2 - (2*stepNum + 1)V + (stepNum^2 + stepNum)) / (V*(V - 1))
Now, let's calculate the total fraction of edges remaining after all steps:
Total fraction = (E(V - 2) / V) * ((E(V - 3)(V - 2) / (V*(V - 1))) * (... * (E(V^2 - (2*stepNum + 1)V + (stepNum^2 + stepNum)) / (V*(V - 1))))
Notice that the rightmost term in each step's equation matches the leftmost term in the next step's equation.
Let's rewrite the equation and see the pattern:
Total fraction = (E(V - 2) * (V - 3)(V - 2) * ... * (V^2 - (2*stepNum + 1)V + (stepNum^2 + stepNum))) / (V^stepNum * (V - 1)^(stepNum - 1))
We can write this in terms of the summation:
Total fraction = (E * product((V^2 - (2*i + 1)V + (i^2 + i)), i = 1 to stepNum)) / (V^stepNum * (V - 1)^(stepNum - 1))
Now, observe that the terms in the product are quadratic functions. To simplify further, we need to evaluate the summation and product.
The important thing to note is that no matter how many steps we take, the fraction of edges remaining can be written as:
Total fraction = K / (V^stepNum * (V - 1)^(stepNum - 1))
Where K is a constant determined by the specific values of V and E.
If we let stepNum = V/2, we can simplify further:
Total fraction = K / (V^(V/2) * (V - 1)^(V/2 - 1))
Notice that both V^(V/2) and (V - 1)^(V/2 - 1) tend to infinity as V increases. Thus, we can simplify the equation as:
Total fraction ≈ K / ∞
Thus, the fraction of edges remaining approaches zero as the number of vertices increases.
Since at most 1/4 of the edges remain, we can conclude that choosing ceil(V / 2) vertices using the greedy algorithm as described covers at least three-fourths (3/4) of the edges in an arbitrary undirected graph.
I hope this clarifies the steps and helps you understand how to arrive at the final number of 1/4.