Polynomial time algorithm

Question

what could be a polynomial time algorithm that finds [V / 2] vertices that collectively account for at least three quarters (3/4) of the edges in an arbitrary non-oriented graph ??

kind help

Answer 1

Here's the proof that it exists:

Consider an algorithm that selects half the vertices at random. For any given edge, the probability that at least one of its two end points has been selected is 3/4, so the expected number of edges covered is 3 | E | / 4. Thus, according to the probabilistic method , there must be at least one edge covering> = 3 | E | / 4, using only 1/2 of the top. A non-deterministic algorithm follows immediately.

To come up with a deterministic algorithm based on this is an exercise in derandomization (try using the conditional expectation method ).

Answer 2

? , ; NP-, ( , G |V| / 2, .

, , .

Answer 3

On the other hand, it does not make sense. I still think that the greedy solution will work; if you keep a selection of vertices with at least an average degree, it seems to me that you will get most of the common edges by the end. But I'm not sure about the proof.