Polynomial time algorithm

what could be a polynomial-time algorithm that finds [V / 2] vertices that collectively account for at least three-fourths (3/4开发者_运维知识库) of the edges in an arbitrary undirected graph??

kindly help

Here's a proof that it exists:

Consider the algorithm that picks half of the vertices randomly. For any given edge, the probability that at least one of its two endpoints was chosen is 3/4, so the expected number of edges covered is 3|E|/4. Thus, by the probabilistic method, there must exist at least one covering of >= 3|E|/4 edges using just 1/2 of the vertices. The nondeterministic algorithm follows immediately.

Coming up with a deterministic algorithm based on this is an exercise in derandomization (try using the method of conditional expectations).

Is there one? I suspect not but I honestly don't know; vertex cover is NP-complete and this is close (we're asking if G has a vertex cover of size at most |V| / 2 that covers three-quarters of the edges.

Obviously try the greedy algorithm picking off vertices with the highest degree first.

On second thought, this doesn't make sense. I still think a greedy solution would work, though; if you keep picking vertices with at least an average degree, it seems to me that you'd get most of the total edges by the end. But I'm not sure about the proof.