Kruskal's algorithm for minimum spanning trees always adds the lowest-weight edge that doesn't create a cycle. Why does this greedy strategy provably find the optimal solution?
AMinimum spanning trees have a special symmetry property that makes any greedy approach correct for graph optimization
BThe set of acyclic edge sets (forests) in a graph forms a matroid — the graphic matroid — and the exchange axiom guarantees that greedy finds the maximum-weight basis in any weighted matroid
CThe algorithm works because cycles can be detected in polynomial time, allowing backtracking when greedy makes a wrong choice
DGreedy algorithms always produce optimal results for graph problems involving real-valued edge weights
The graphic matroid has acyclic edge sets as its independent sets. These satisfy the matroid axioms: the empty set is independent; every subset of an acyclic set is acyclic (hereditary property); and if two forests have different sizes, an edge from the larger can always be added to the smaller without creating a cycle (exchange axiom). The exchange axiom is what guarantees greedy optimality: at each step, the greedy choice (lowest-weight edge that keeps independence) can always be extended to an optimal basis without losing anything. Kruskal's algorithm is correct because spanning trees are matroid bases, not because of any special property of graphs beyond the matroid structure.
Question 2 Multiple Choice
You are designing a greedy algorithm for a combinatorial optimization problem. Under what condition should you be most suspicious that greedy will fail to find the optimal solution?
AWhen the element weights are very large or unevenly distributed across the ground set
BWhen the ground set has more than a few hundred elements, making the search space too large for greedy to explore
CWhen the independence system violates the exchange axiom — if smaller independent sets cannot always be extended by elements from larger ones, there is likely no matroid structure and greedy will typically produce suboptimal results
DWhen there are ties in element weights, forcing arbitrary tiebreaking choices
The exchange axiom is the precise condition that makes greedy optimal. If your independence system satisfies it, greedy provably works. If it doesn't — if there exist independent sets I and J with |I| < |J| such that no element of J can be added to I while preserving independence — the system is not a matroid and greedy typically fails. In fact, a theorem states that an independence system is a matroid if and only if greedy finds the maximum-weight basis for every weight assignment. So when you observe greedy failing on some weight function, you've proven the structure lacks the exchange property. Recognizing when the exchange axiom fails is how algorithm designers know to seek other approaches.
Question 3 True / False
The exchange axiom states that if I and J are both independent sets and |I| = |J|, then some element of J can be added to I to produce a larger independent set.
TTrue
FFalse
Answer: False
The exchange axiom requires |I| < |J| (strictly less than), not |I| = |J|. The statement is: if I and J are both independent and the size of I is strictly less than the size of J, then there exists some element x in J but not in I such that I ∪ {x} is independent. When |I| = |J|, no such extension is possible (they're already the same size) — though a symmetric exchange property does hold separately. The strict inequality is what gives the exchange axiom its power: it ensures all bases of a matroid have the same cardinality and that smaller independent sets can always be grown toward a basis.
Question 4 True / False
Wherever a greedy algorithm provably finds the optimal solution to a weighted combinatorial problem, a matroid structure underlies the independence constraints.
TTrue
FFalse
Answer: True
This is the matroid characterization theorem: a weighted greedy algorithm finds the maximum-weight basis for every possible weight function if and only if the independence system is a matroid. The 'if' direction is standard — the exchange axiom implies greedy works. The 'only if' direction is the surprising part: if greedy works for all weight functions, the system must satisfy the exchange axiom and therefore be a matroid. This means recognizing where greedy works is equivalent to recognizing matroid structure. Kruskal's spanning tree algorithm and Gaussian elimination are both correct for all weights, confirming that graphic and linear matroids are indeed matroids.
Question 5 Short Answer
What is the exchange axiom, and why does it guarantee that a greedy algorithm will find the maximum-weight basis of a matroid?
Think about your answer, then reveal below.
Model answer: The exchange axiom states: if I and J are both independent sets and |I| < |J|, then there exists an element x ∈ J \ I such that I ∪ {x} is also independent. This means any smaller independent set can always be extended by an element from a larger one — no independent set is a 'dead end' that can't grow. For a greedy algorithm building a maximum-weight basis, this guarantees that at every step, choosing the highest-weight element that preserves independence will lead to a basis that is globally optimal: if a greedy choice later seems suboptimal, the exchange axiom ensures there is always a way to swap elements between the greedy basis and any other basis without losing independence, proving by exchange argument that the greedy basis is at least as good.
The exchange argument is: suppose the greedy basis G has lower weight than some other basis B. Take the highest-weight element b ∈ B \ G. By the exchange axiom applied to G and B (since they have the same size as bases, actually the argument is more subtle — you apply exchange incrementally to show every element of B not in G can be swapped in while maintaining independence). The key is that the exchange axiom prevents any situation where the greedy choice irrecoverably forecloses the optimal solution — the independence structure is 'continuous' enough that local optimal choices aggregate to a global optimum.