PDF of Eric’s handwritten notes are here.
Greedy strategies are a very natural approach to solve a problem: we take the choice which looks locally optimal. However, we are generally concerned with a global optimum. So, when do these locally optimal moves produce a global optimum?
We can think of a greedy algorithm as: given the choices we have made so far, make the choice that provides the most benefit now. We will see one example of a problem (computing the minimum spanning tree of a graph) where a greedy algorithm works well.
Consider the following general framework for graph problems.
Input: An undirected graph with where each . We also have weights on all the edges, given by .
Problem: Find a subset of edges, vertices (i.e. a subgraph) of of minimum total weight that satisfies property .
Property could be one of many possibilities, e.g., “cycle” or “path” or “spanning”. Some will have efficient solutions, others will not. We consider a few special properties which are solvable via a greedy algorithm.
Minimum Spanning Tree (MST):
Suppose we consider : “minimal size, connected, spanning” subgraph. A connected subgraph means every vertex is reachable from every other vertex, and a spanning subgraph means that it includes every vertex from .
A “minimal size, connected, spanning” subgraph is in fact a spanning tree of .
Properties of a tree.
Claim: A minimal size subset of edges that connects every pair of vertices 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,
MST Problem: Find the minimum (or maximum) weight spanning tree of .
How to solve?
Let’s first consider a natural greedy algorithm to solve this problem. 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 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(Kruskal): Kruskal’s algorithm produces a minimum weight spanning tree of .
The proof of the theorem follows almost immediately from a few helpful observations. First, define a cut as the set of edges between a subset of vertices and its complement . That is,
Lemma 1: 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 2: Let be the tree found my Kruskal’s algorithm. For each edge , there exists a cut such that
- is the minimum weight edge of
- is the unique edge in .
Proof: Consider , with . Then, are in different components and is the only edge of in . Also, at the point when was added, and were not connected, which means that is the minimum weight edge on (otherwise, Kruskal’s algorithm would have added another edge before ).
Proof (of Theorem): Using Lemmas 1 and 2, we can now prove that Kruskal’s algorithm always produces an MST.
Suppose is not an MST, and let be an MST. Order the edges of by increasing weight. Take the first edge of that is not in . Thus has a cycle . Let be the cut for given by Lemma 2. Now, remove that crosses . We have that and is a spanning tree.
Repeat this process for all edges of not in , and thus is an MST.
The key idea of the proof is sometimes called the cut property.
Lemma 3 (Cut Property). Let be a subset of edges of an MST of a graph . For any edge such that (1) is a minimum-weight edge of a cut and (2) , there is an MST s.t. .
Using the cut property, we can prove that the following algorithm, called Prim’s algorithm, also produces an MST.
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: .