CODEWITHSUNDEEP
algorithmgraph-theory
Slaven Glumac
Slaven Glumac

Reputation: 553

Why is greedy algorithm not finding maximum independent set of a graph?

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?

Upvotes: 8

Views: 9251

Answers (1)

gms7777
gms7777

Reputation: 452

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.

Upvotes: 10

Related Questions