Matroid Intersection

Imagine you are scheduling workers. Each person can only work a certain number of shifts (one constraint), and each time slot can only be filled once (a second constraint). You want the largest possible assignment satisfying both rules simultaneously. Can you find it quickly?

The answer is yes — because both constraints are secretly matroids, and finding the largest set that satisfies two matroids at once is one of the most beautiful results in combinatorial optimization.

A matroid is a mathematical abstraction of "independence." The definition is deliberately broad: a set family is a matroid if adding one element can never destroy an independence that a smaller set already had. Spanning forests of a graph, linearly independent vectors, matchings in a bipartite graph — all are matroids in disguise.

The key insight, proven by Jack Edmonds in 1970, is that matroid intersection — finding the maximum-weight common independent set of two matroids on the same ground set — is solvable in polynomial time. This stands in sharp contrast to three-matroid intersection, which is NP-hard. The boundary between two and three is one of the sharpest tractability edges in all of combinatorics.

Below you can watch the classic augmenting-path algorithm find the largest set of edges that is simultaneously a forest in the blue graph (Matroid 1) and a forest in the red graph (Matroid 2). Click Step to advance one iteration, or Run to watch it finish automatically.

<p class="hint">
  {{hint}}
</p>
<div class="canvases">
  <div class="graph-wrap">
    <div class="graph-label">{{label_m1}}</div>
    <canvas id="c1" width="220" height="180"></canvas>
  </div>
  <div class="graph-wrap">
    <div class="graph-label">{{label_m2}}</div>
    <canvas id="c2" width="220" height="180"></canvas>
  </div>
</div>
<div class="info-row">
  <div class="info-box" id="info-sol">{{info_common_set}} <b id="sol-size">0</b> {{info_edges}}</div>
  <div class="info-box" id="info-step">{{info_step}} <b id="step-num">0</b></div>
</div>
<div class="edge-list" id="edge-list"></div>
<div class="btns">
  <button id="btn-step">{{btn_step}}</button>
  <button id="btn-run">{{btn_run}}</button>
  <button id="btn-reset" class="ghost">{{btn_reset}}</button>
</div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #222; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.canvases { display: flex; gap: 12px; flex-wrap: wrap; margin-bottom: .6rem; }
.graph-wrap { display: flex; flex-direction: column; align-items: center; }
.graph-label { font-size: .78rem; font-weight: 700; margin-bottom: 4px; color: #555; }
canvas { border: 1px solid #d0d7de; border-radius: 8px; background: #f8fafc; }
.info-row { display: flex; gap: 10px; margin-bottom: .4rem; flex-wrap: wrap; }
.info-box { background: #e8eef3; border-radius: 6px; padding: .28rem .7rem; font-size: .85rem; }
.edge-list { font-size: .8rem; color: #444; min-height: 1.4em; margin-bottom: .5rem; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.status { font-size: .93rem; font-weight: 600; min-height: 1.4em; }
.status.done { color: #0a7d33; }
.status.working { color: #b45309; }

// Code not found

Each step searches for an augmenting path in the exchange graph: a path that alternates between elements to add and elements to remove, ending in a way that grows the common independent set by one. When no such path exists, the current set is provably maximum.

Status: solved in polynomial time — Jack Edmonds, 1970.

• Checking membership is easy: test whether a set is independent in each matroid separately.
• Two matroids: Edmonds' algorithm grows the common independent set one element at a time by searching for augmenting paths in a bipartite exchange graph. Each augmentation takes time proportional to the sizes of the ground set and the current solution. The total running time is $O(r^{2} \cdot T)$ where r is the size of the optimal solution and T is the cost of independence oracle queries.
• Three matroids: adding a third matroid makes the problem NP-hard. You can encode 3-dimensional matching into three-matroid intersection, and that problem is already NP-complete. The jump from two to three is abrupt — there is no known efficient algorithm.
• Weighted version: Edmonds also solved the weighted variant (maximize the total weight of the common independent set) in polynomial time, using a weighted augmenting-path search.

This places matroid intersection in a rare club: genuinely hard-looking combinatorial problems that turn out to be tractable. The key is the exchange property of matroids — it guarantees that local augmentations lead to a global optimum, exactly the same structural gift that makes bipartite matching solvable by augmenting paths. In fact, bipartite matching is a special case: match edges are simultaneously independent in the partition matroid of left vertices and the partition matroid of right vertices.

See also: bipartite matching and linear programming, which provide alternative proofs via total dual integrality.

Because matroids capture so many natural independence structures, matroid intersection unifies a surprising breadth of real problems:

• Bipartite matching: every bipartite matching problem is a matroid intersection of two partition matroids. The classical augmenting-path matching algorithm is a special case of Edmonds' general method.
• Scheduling with two resources: when jobs must not exceed a budget of one type and a quota of another, the feasible assignments form a matroid intersection.
• Colorful spanning forests: given a set of edges each painted one of k colors, find the largest forest that uses at most one edge of each color. This is an intersection of a graphic matroid and a partition matroid — solvable in polynomial time.
• Arborescence packing: packing edge-disjoint directed spanning trees in a network is equivalent to matroid intersection (and underpins fault-tolerant routing).
• Resource-constrained project planning: tasks with two independent resource ceilings (budget and person-hours, say) can be scheduled optimally via matroid intersection.
• Network coding: selecting a linearly independent, flow-feasible set of transmission vectors intersects a linear matroid with a gammoid.

The unifying power is the reason this single algorithm appears across logistics, VLSI design, combinatorial auction theory, and theoretical computer science.

Matroid intersection is one of the great gift-wrapped surprises of theoretical computer science: a problem that looks like it should be exponentially hard — satisfy two independent-set constraints at once — turns out to yield to an elegant augmenting-path algorithm in polynomial time.

The proof hinges on the exchange property that defines matroids. That single axiom is enough to guarantee that greedy local steps lead to a global optimum. It is also the precise reason why three matroids break the guarantee: a third constraint destroys the exchange geometry, and the problem becomes NP-hard.

The boundary at two is not an accident. It is a theorem. And it is one of the clearest reminders that in complexity, the difference between "two" and "three" can be the difference between the entire field of P vs NP.