Suppose that we are given an undirected graph, and we know that the maximum edge

Question

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.

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.