A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A matroid is a combinatorial structure that captures the notion of "independence" — generalizing linear independence in vector spaces and acyclicity in graphs. The matroid intersection problem asks: given two matroids on the same ground set, find a maximum-weight common independent set. This elegant framework unifies many classical optimization problems: bipartite matching is the intersection of two partition matroids; colorful spanning forests arise from graphic and partition matroid intersection. While a single matroid's optimization is solved by greedy (this is essentially what defines matroids), intersecting two matroids requires augmenting-path techniques analogous to network flow. The matroid intersection theorem states that the maximum common independent set size equals the minimum of a certain dual quantity, yielding a min-max theorem generalizing König's theorem.
Matroids are the combinatorial structures that make the greedy algorithm work. Formally, a matroid is a pair (E, I) where E is a ground set and I is a collection of "independent" subsets satisfying three axioms: the empty set is independent, subsets of independent sets are independent (hereditary property), and if one independent set is larger than another, some element of the larger set can be added to the smaller (exchange property). The exchange property is what guarantees the greedy algorithm — always add the heaviest available element that maintains independence — finds a maximum-weight independent set.
Examples ground the abstraction. In a graphic matroid, E is the edge set of a graph and independent sets are acyclic subsets (forests). The greedy algorithm on a graphic matroid is Kruskal's MST algorithm. In a partition matroid, E is partitioned into groups and an independent set contains at most one element from each group. In a linear matroid, E is a set of vectors and independent sets are linearly independent subsets. Each captures a different flavor of "independence," but all satisfy the same axioms and all respond to greedy.
Matroid intersection asks for the largest (or heaviest) set that is independent in two matroids simultaneously. This is strictly harder than single-matroid optimization but still polynomial. The algorithm builds an exchange graph: nodes are ground set elements, and directed edges represent swaps that maintain independence in one matroid or the other. Augmenting paths in this exchange graph (from an element addable in M1 to one addable in M2) yield improved common independent sets via symmetric differences. This is the matroid generalization of augmenting-path algorithms for bipartite matching, and the connection is exact: bipartite matching equals partition-matroid intersection.
The matroid intersection theorem provides the min-max dual: max |common independent set| = min_{A subset E} (r_1(A) + r_2(E\A)), where r_1, r_2 are the rank functions. This generalizes König's theorem and provides optimality certificates. The polynomial tractability of 2-matroid intersection versus the NP-hardness of 3-matroid intersection is a fundamental boundary in combinatorial optimization — it shows that the structure of two matroids interacting is rich enough to capture bipartite matching, spanning trees, and arborescences, but adding a third matroid pushes into NP-hard territory (capturing Hamiltonian paths).