The greedy algorithm finds a maximum-weight independent set in any single matroid. Why does greedy fail for matroid intersection, and what technique replaces it?
AGreedy fails because matroid intersection is NP-hard
BGreedy optimizes for one matroid but may violate independence in the other. Matroid intersection uses an augmenting-path algorithm on an exchange graph: vertices are ground set elements, edges represent exchange pairs where adding one element and removing another maintains independence in both matroids, and augmenting paths increase the common independent set size
CGreedy fails because matroid intersection requires dynamic programming
DGreedy works for matroid intersection if you alternate between the two matroids
A greedy element that is optimal for matroid M1 may not be independent in M2. The exchange graph captures the structure of feasible swaps: for current common independent set I, element y not in I, and element x in I, there is a directed edge from y to x if (I - x + y) is independent in M1, and from x to y if (I - x + y) is independent in M2. An augmenting path from a free element (addable to M1's span) to another free element (addable to M2's span) yields a symmetric difference that increases |I| by 1. This is the matroid analog of augmenting paths in bipartite matching.
Question 2 True / False
Bipartite matching can be formulated as the intersection of two partition matroids. This means the Hopcroft-Karp algorithm is a special case of matroid intersection.
TTrue
FFalse
Answer: True
Given a bipartite graph with parts L and R, define matroid M1 on the edges: a set of edges is independent if no two share an L-vertex (partition matroid on L-partition). Define M2 similarly for R-vertices. A common independent set is a set of edges sharing no endpoints on either side — a matching. Maximum matroid intersection finds a maximum matching. The augmenting-path structure of matroid intersection, specialized to partition matroids, recovers exactly the augmenting-path algorithm for bipartite matching. This reveals matching as a special case of a deeper combinatorial structure.
Question 3 Short Answer
Explain the matroid intersection min-max theorem and its relationship to König's theorem for bipartite graphs.
Think about your answer, then reveal below.
Model answer: The matroid intersection theorem (Edmonds) states: the maximum size of a common independent set of matroids M1, M2 on ground set E equals min over all subsets A of E of (rank_M1(A) + rank_M2(E\A)). This says you can 'certify' the optimality of a common independent set by finding a partition of the ground set where the sum of ranks is minimized. For bipartite matching (partition matroids), this specializes to König's theorem: max matching = min vertex cover. The A-partition corresponds to choosing which side's vertices are in the cover, and rank_M1(A) + rank_M2(E\A) counts the cover size. The matroid min-max theorem thus generalizes König's theorem from bipartite graphs to arbitrary matroid pairs.
This min-max theorem is a cornerstone of combinatorial optimization. It demonstrates that matroid intersection, despite being more general than bipartite matching, retains the beautiful duality property where the primal optimum equals the dual optimum — a property that fails for general 3-dimensional matching (which is NP-hard).
Question 4 True / False
The intersection of THREE or more matroids can always be optimized in polynomial time, just like two-matroid intersection.
TTrue
FFalse
Answer: False
3-matroid intersection is NP-hard. This is proved by reducing Hamiltonian path to the intersection of three matroids: a graphic matroid (independent sets are forests), a partition matroid (each vertex has at most one outgoing edge), and another partition matroid (each vertex has at most one incoming edge). Their intersection is a set of edges forming a Hamiltonian path. The jump from 2 to 3 is a sharp complexity boundary — two-matroid intersection is polynomial (augmenting paths), three-matroid intersection is NP-hard. This is one of the cleanest examples of a phase transition in combinatorial optimization complexity.