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?
Sometimes greedy algorithms fail to find the globally optimal solution because they do not consider all the data. The choice made by a greedy algorithm may depend on choices it has made so far, but it is not aware of future choices it could make.
The Maximum Independent Set (MIS) problem in graph theory is the task of finding the largest independent set in a graph, where an independent set is a set of vertices such that no two vertices are adjacent. There is currently no known efficient algorithm to find maximum independent sets.
Independent set is a set of vertices such that any two vertices in the set do not have a direct edge between them. Maximal independent set is an independent set having highest number of vertices. Note: There can be more than one independent and maximal independent sets for a given graph.
(Deterministic) greedy algorithms often provide an effective and fast approach when dealing with combinatorial optimization prob- lems. On the other hand, it is well-known that they have a bad approximation behavior on problems such as the minimum vertex cover problem for some instances.
The same approach as in the original question answer applies here as well, with a slightly modified 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:
both are three-element maximal (as in, cannot be expanded) independent sets, and thus not maximum (as in, the largest possible).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With