6

I was trying to solve the maximum independent set problem on bipartite graphs using the greedy method. So came across this post which does exactly what i was trying to do. But am concentrating only on the bipartite graphs. The counter case in the answer is not a bipartite graph. Are there any bipartite graphs that this one wont work?

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

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

Improve this question
1
  • Please quote the algorithm here. Interesting question, though. Commented Apr 8, 2013 at 7:17

1 Answer 1

Reset to default
7

The same approach as in the original question answer applies here as well, with a slightly modified graph:

(2,2,4)theta 7-vertex bipartite graph

Start by removing #5, What's left is a paw graph (nodes (1,3,4,7)). Remove its leaves in any order. You discover a four-node independent set: (1,3,5,7)

Start by removing #6. What's left is a 4-cycle. Removing any node forces either of these sets:

  1. (1,3,6)
  2. (2,4,6)

both are three-element maximal (as in, cannot be expanded) independent sets, and thus not maximum (as in, the largest possible).

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

3 Comments

Now, finding a graph where this algorithm is forced to make a mistake is an interesting task. I don't know about one, though
@j_random_hacker adding (5, 4) and (7, 2) doesn't force the choice of 6, you can still choose 1 or 3. The smallest graph where the greedy algorithm is forced to fail is pasteboard.co/8Ni6WmJXXEAZ.png
@meblum: You're right, thanks. I've removed by comment.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.