When does greedy work?
Observe the following property of forests:
Lemma: Forests on a graph such that then such that is a forest.
Proof: Notice that cannot be a tree and so it has atleast two components. Let be the components of . We claim that all the edge of cannot be contained in since each is a tree on vertices. Since , there must be an edge and two components of , and such that and . Thus is still a forest.
Let be a universe and be a collection of subsets of . We say that is a matroid if:
- and .
- and such that .
A set is called independent. Notice that the set where is the set of all forests such that is a matroid.
Suppose is a matroid and we have a weight function and we want to find a maximum weight independent set. Consider the following greedy algorithm:
- Sort the elements of in decreasing order of their weight, so that .
- Initialize where is the first element such that .
- Iterate till you can no longer add any element while still remaining in .
Theorem: This algorithm gives us the maximum weight independent set in .
Proof: We first observe that the size of the set returned by the algorithm is the same as the size of , where is a maximum weight independent set in . Let the elements picked by greedy be in order. Let the elements of (in decreasing order of weight) be . Suppose greedy fails; then there exists a such that since otherwise since . We know that and . By the property of matroids, we get that there must be an element such that . Since which contradicts the choice of the greedy algorithm!
Notice that this same proof would have worked for proving the correctness of the greedy algorithm for finding a minimum (or maximum) weight spanning tree. Another example of matroid is , where is a set of vectors in and is a collection of all linearly independent subsets of . Thus the greedy algorithm would also work for finding a maximum weight linearly independent set of vectors.