Suppose that we are given an undirected graph, and we know that the maximum edges covered by $k$ vertices is $n$. If we let the greedy algorithm choose these $k$ vertices for us, I am told that it is capable of covering at least $n/2$ edges. Is there a way to prove this? If so, how should it be done?

Since the greedy algorithm removes the vertex with the maximum degree still left in the original graph (along with its incident edges) in each iteration, is it possible to find a connection between the minimal number of edges removed each time by the greedy algorithm to the optimal solution $n$?

I am truly clueless about how such a problem should be solved.

Hints or references are both welcome. Many thanks.

  • 1
    $\begingroup$ Try to use the fact that each edge can be covered by at most two vertices. $\endgroup$ – Yuval Filmus Dec 27 '14 at 21:10
  • $\begingroup$ In your first statement, you probably mean "at least" rather than "at most". $\endgroup$ – Yuval Filmus Dec 28 '14 at 7:35
  • $\begingroup$ Actually, I do mean "at most", if it's an optimal cover. $\endgroup$ – user23245 Dec 28 '14 at 9:31
  • $\begingroup$ If $k$ vertices can cover at most $n$ edges, then for all you know the graph has no edges at all. What you want to say is that the maximal number of edges covered by $k$ vertices in $n$. The performance guarantee of the greedy algorithm, however, would work with the wording I suggested. $\endgroup$ – Yuval Filmus Dec 28 '14 at 9:41

You haven't fully specified the greedy algorithm, so let's assume that at each step you select a vertex covering the most new edges. In that case, this is the greedy algorithm for the more general problem of Maximum Coverage, whose approximation ratio is known to be roughly $1-1/e$, which is even larger than $1/2$. For a proof, see for example here. There is also a less classical proof that doesn't use elements at all, but only the monotonicity and submodularity properties of the coverage function (the function getting ass input a set of vertices and outputting the number of edges covered).

There are somewhat better algorithms that use the fact that each edge is covered by only two vertices. Examples are the LP-based algorithm and the non-oblivious local search algorithm. It is also possible that the greedy algorithm performs better in this case.

| cite | improve this answer | |
  • $\begingroup$ These are not my notes, but rather the first hit on a popular search engine. $\endgroup$ – Yuval Filmus Dec 28 '14 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy