Polynomial time algorithm

Question

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

Answer 1

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).

Answer 2

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.