(Algorithms chapter 5)
Greedy strategies take a very natural approach to solve a problem. Given the choices that we have made so far, make the choice that provides the most benefit going forward. We can think of a greedy algorithm as taking the choice that looks locally optimal. However, generally our goal is to find a global optimum. When do these locally optimal moves produce a global optimum? We start by seeing some examples.
Def 1. (Matching) Given a graph , a subset of edges is a matching if every two edges in has disjoint endpoints.
Maximum Matching Problem
Given a graph , find a matching of maximum cardinality.
A greedy approach: Pick any available edge that extends the current matching.
Does the above algorithm always output a maximum matching of the graph? No. Consider the example below which is a path of length three. If the green edge is chosen as the first edge by the algorithm, the algorithm stops there. The optimal solution though is a matching of size 2 (red edges).
Shortest Path Problem
Given a graph with weights on the edges, and vertices , find a path between with minimum total weight.
A greedy approach: Start with and at each step choose the neighbour that gives the shortest path to .
Does the above algorithm always find a shortest path? No. Consider the example below. At the first step, the algorithm chooses the neighbour cause the distance of to is 6 versus the distance of to which is 8. Therefore the greedy algorithm outputs the path . However, the shortest path is .
Minimum Spanning Tree (MST) Problem
The next example is a problem (computing the minimum spanning tree of a graph) where a greedy algorithm finds the optimal solution. Before getting into the problem, we need to introduce some definitions of a graph .
Def 2. (Connected Component) A connected component is a subset of vertices such that there is a path between any two vertices in .
Def 3. (Spanning Subgraph) A subgraph that includes every vertex in .
Def 4. (Tree) A tree is a connected component of with no cycles.
Claim 5: A minimal weight spanning connected component is a spanning tree. That is,
- has no cycles
- has edges; i.e. .
Proof: (1) Suppose had a cycle. Then, we can remove any edge on the cycle while maintaining connectivity between every pair of vertices. Therefore, there can be no cycles if is minimal.
(2) We prove by induction that . It’s clearly true for the base cases . Now, for , remove any edge in . Then, has components (otherwise was not minimal), and each component has vertices with . By induction,
Minimum Spanning Tree (MST) Problem. Given a graph and weights on the edges, find a spanning tree of with minimum total weight.
A greedy approach: One possible approach is to simply select the lightest weight edge. Locally, this seems like the best edge to select. However, there is a potential problem: what if the lightest weight edge creates a cycle? Well, then we simply ignore that edge and proceed to the next lightest edge. We have essentially described Kruskal’s Algorithm:
Kruskal’s Algorithm for solving MST:
- Sort edges in increasing order of weight; so have an ordering such that .
- for to
- Add to if it doesn’t create a cycle.
- Return .
Theorem 6 (Kruskal): Kruskal’s algorithm produces a minimum weight spanning tree of .
Before proving this theorem, we need to first introduce some definitions and lemmas.
Def 7. (Cut) A cut is the set of edges between a subset of vertices and its complement . That is,
Lemma 8. Fix any edge whose weight is the minimum in some cut . Then, there exists an MST containing .
Proof: Suppose is not in an MST. Consider an MST and add to . Then, induces a cycle (since has two paths between endpoints of ).
Consider the cut for which is a minimum weight edge. Then must cross in some other edge with .
Set . Note that , which means is an MST (since it connects every pair of vertices and is minimum weight).
Lemma 9 (cut property). Let be a subset of edges of an MST of a graph . For any edge such that is a minimum-weight edge of a cut and , there is an MST s.t. .
Proof. Take some MST that contains . Let be a cut in which is a minimum cost edge and assume that . Add to . This creates a cycle. At least one other edge of the cycle must be in . Since was the edge of the cut with the smallest weight, has lower weight than . This contradicts being an MST.
Proof (of Kruskal Theorem): Using Lemmas 8 and 9, we can now prove that Kruskal’s algorithm always produces an MST. When the next edge
When the next edge is added, we can identify a cut such that is the first edge across this cut. Let be the edges that has been added so far. According to Lemma 9, belongs to some MST. We add to and repeat the process.
Running time of Kruskal’s algorithm: .
Sorting the edges once up front takes .
However, we also have to keep track of whether an added edge creates a cycle, i.e. when an edge connects two vertices in the same connected component. We can do this via a simple data structure.
For each vertex, introduce a component number, which is initially just the index of that vertex. When Kruskal’s algorithm adds an edge which connects two vertices with the same component number, we skip that edge because it creates a cycle. If the component numbers of the two vertices are different, then we relabel the vertices in the smaller component to the label of the larger component. Since we relabel the smaller component, the size of a vertex’s component at least doubles each time it is relabeled. Therefore a vertex’s label changes at most times. Thus the total cost of this data structure is .
Another algorithm to find the MST of a graph is Prim’s algorithm.
- Start with any vertex, and mark it as visited.
- Add the lightest weight edge from some visited vertex to an unvisited vertex; repeat until all vertices are visited.
As with Kruskal’s algorithm, its correctness follows from the cut property given above.
Running time of Prim’s algorithm: .
Can we define a more general class of problems that could be solved by the above greedy algorithm?
Def 10. (Matroid) A matroid consists of a universe of elements and a collection of independent subsets of with the following properties
A Greedy approach. Sort elements of in increasing order of weights. Add the next element in the list that preserves the independency.
Theorem 11. The above greedy algorithm finds the maximum weight independent set.
Proof. We prove by contradiction. Let be the elements in the output greedy algorithm in descending weight order and let be the elements in the maximum independent set in descending weight order. Since the total weight of the optimal is higher than the total weight of the greedy solution, consider to be the first index that . Then and both are independent. By the matroid property such that is an independent set. But and this contradicts the fact that the greedy algorithm chose and not .
Observation 12. Spanning trees form a matroid. Let’s define and as the subset of edges with no cycles (forests). It is simple to see that this satisfies the two matroid properties. Given this, Theorem 11 states that the greedy algorithm stated above finds the maximum spanning tree. This can be used to solve the MST problem by simply defining the weights . Then finding an MST on a graph with weights is equivalent to finding the maximum spanning tree on the same graph with weights .