8

Given a graph G, why is following greedy algorithm not guaranteed to find maximum independent set of G:

Greedy(G): S = {} While G is not empty: Let v be a node with minimum degree in G S = union(S, {v}) remove v and its neighbors from G return S

I am wondering can someone show me a simple example of a graph where this algorithm fails?

Improve this question
2
  • I am wondering, If this algorithm fails, What is the right algorithm for solving the problem? Commented Dec 25, 2012 at 21:27
  • @TravelingSalesman I think you can find the answer in the same wikipedia article. As I see it, this greedy algorithm finds an independent set and that set is relatively large, so you can use it to find suboptimal solution. I'm not really an expert, so please don't trust me :) Commented Dec 26, 2012 at 14:29

1 Answer 1

Reset to default
11

I'm not sure this is the simplest example, but here is one that fails: https://i.sstatic.net/ZPuHR.jpg

For the first step, you can choose B, C, D, or F since they all have degree 2. Suppose we remove B and its neighbors. That leaves F and D with degree 1 and E with degree 2. During the next two steps, we remove F and D and end up with a set size of 3, which is the maximum.

Instead suppose on the first step we removed C and its neighbors. This leaves us with F, A and E, each with a degree size of 2. We take either one of these next, and the graph is empty and our solution only contains 2 nodes, which as we have seen, isn't the maximum.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Thank you very much! I am not sure if this is according to Q&A rules, but I have another question. Suppose that every vertex of a graph has a different number of incident edges. Would that assumption be enough for greedy algorithm to work correctly?
That's an impossible condition, actually (except in the degenerate case of 1 node). Its pretty easy to prove. Suppose that there are n nodes, all of which have a different degree. The largest degree a node can have is n-1. That means the nodes must have degrees {0, 1 ... n-1}. However, its not possible for there to be a node with degree 0, and a node with degree n-1 (a node that isn't connected to any nodes and a node that is connected to every node). Therefore in any graph with at least 2 nodes, at least 2 of the nodes must have an equal number of incident edges.
Thank you! I wasn't thinking when I posted a comment :)
The greedy algorithm doesn't work for bipartite graphs either

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.