Introduction

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.

Try It

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">
  Two graphs share the same 5 vertices (numbered 0–4) but have different edges. A set of edges is <b>independent</b> in a graph when it forms a <b>forest</b> (no cycles). The algorithm finds the largest set of edges that is a forest in <em>both</em> graphs simultaneously.
</p>
<div class="canvases">
  <div class="graph-wrap">
    <div class="graph-label">Matroid 1 (blue graph)</div>
    <canvas id="c1" width="220" height="180"></canvas>
  </div>
  <div class="graph-wrap">
    <div class="graph-label">Matroid 2 (red graph)</div>
    <canvas id="c2" width="220" height="180"></canvas>
  </div>
</div>
<div class="info-row">
  <div class="info-box" id="info-sol">Common independent set: <b id="sol-size">0</b> edge(s)</div>
  <div class="info-box" id="info-step">Step: <b id="step-num">0</b></div>
</div>
<div class="edge-list" id="edge-list"></div>
<div class="btns">
  <button id="btn-step">Step</button>
  <button id="btn-run">Run</button>
  <button id="btn-reset" class="ghost">Reset</button>
</div>
<div class="status" id="status">Press Step or Run to start the augmenting-path algorithm.</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Matroid Intersection demo
// Ground set: edges E = {0..8}. Two graphic matroids M1, M2 on 5 vertices.
// Independent set = forest (acyclic edge subset). Algorithm: augmenting paths.
//
// Vertices at fixed positions for two separate drawings.
const V = 5;
// Edges shared as ground set: each edge has (u,v) for cycle detection.
// We define two graphs: G1 (blue) and G2 (red), same edge *labels* but
// different (u,v) pairs -- so a forest in G1 need not be a forest in G2.
const EDGES = [
  // label: [u,v in G1, u,v in G2]
  // 0..8, nine candidate edges
  {id:0, g1:[0,1], g2:[0,2]},
  {id:1, g1:[0,2], g2:[0,3]},
  {id:2, g1:[1,2], g2:[1,3]},
  {id:3, g1:[1,3], g2:[1,4]},
  {id:4, g1:[2,3], g2:[2,4]},
  {id:5, g1:[3,4], g2:[3,4]},
  {id:6, g1:[0,3], g2:[0,1]},
  {id:7, g1:[2,4], g2:[2,3]},
  {id:8, g1:[0,4], g2:[0,4]},
];
const N = EDGES.length;

// Union-Find for cycle detection
function makeUF(n){ return Array.from({length:n},(_,i)=>i); }
function find(uf,x){ while(uf[x]!==x){uf[x]=uf[uf[x]]; x=uf[x];} return x; }
function union(uf,a,b){ a=find(uf,a); b=find(uf,b); if(a===b)return false; uf[a]=b; return true; }

function isForest(edgeIds, graphKey) {
  // graphKey: 'g1' or 'g2'
  const uf = makeUF(V);
  for(const id of edgeIds){
    const [u,v] = EDGES[id][graphKey];
    if(!union(uf,u,v)) return false;
  }
  return true;
}

function isIndepM1(S){ return isForest(S,'g1'); }
function isIndepM2(S){ return isForest(S,'g2'); }

// Augmenting-path algorithm for matroid intersection
// State machine: current solution S (array of edge ids), step count
let S = [];
let stepCount = 0;
let done = false;
let augPath = []; // last found augmenting path (for highlight)
let lastAdded = []; // elements added in last step
let lastRemoved = []; // elements removed in last step

// Find an augmenting path using BFS in the exchange graph.
// Exchange graph: bipartite. Left = E\S, Right = S.
// Edge from y (in S) to x (in E\S): (S - y + x) is indep in M1 and ...
// Actually standard algorithm:
//   D1(S,x) = {y in S : S-y+x independent in M1}  (can swap y out for x in M1)
//   D2(S,y) = {x in E\S : S-y+x independent in M2}  (can swap y out for x in M2)
// Search for path X1 - S1 - X2 - S2 ... ending at x where S+x is indep in M2, starting from x where S+x is indep in M1.
function findAugPath() {
  const inS = new Set(S);
  const notInS = EDGES.map(e=>e.id).filter(id=>!inS.has(id));

  // BFS. Nodes = edge ids. We alternate: start from X0 = {x: S+x indep in M1}
  // BFS labels track how we got there.
  // Even depth = x in E\S, odd depth = y in S
  // We find a path from x (even) to some z (even) where S+z indep in M2
  // alternating: x0 -> y1 -> x2 -> y3 -> ... -> xk where S+xk indep in M2

  const pred = {}; // pred[node] = {from, isInS}
  const visited = new Set();
  const queue = [];

  // Sources: x in E\S s.t. S+x is indep in M1
  for(const x of notInS){
    if(isIndepM1([...S, x])){
      pred[x] = null; // source
      visited.add(x);
      // Check if also indep in M2 -> augment directly
      if(isIndepM2([...S, x])){
        return [x]; // path of length 1
      }
      queue.push(x);
    }
  }

  while(queue.length){
    const x = queue.shift(); // x in E\S
    // From x, we can go to y in S if (S - y + x) is indep in M2
    for(const y of S){
      if(visited.has(y)) continue;
      const Smod = S.filter(e=>e!==y).concat([x]);
      if(isIndepM2(Smod)){
        pred[y] = x;
        visited.add(y);
        // From y, go to z in E\S if (S - y + z) is indep in M1
        for(const z of notInS){
          if(visited.has(z)) continue;
          const Smod2 = S.filter(e=>e!==y).concat([z]);
          if(isIndepM1(Smod2)){
            pred[z] = y;
            visited.add(z);
            // Is S+z (after removing y along path) indep in M2?
            // Reconstruct path to check
            // Build the augmented set by tracing path
            const path = tracePath(pred, z);
            const newS = applyPath(path);
            if(isIndepM2(newS)){
              return path;
            }
            queue.push(z);
          }
        }
      }
    }
  }
  return null; // no augmenting path
}

function tracePath(pred, end){
  const path = [];
  let cur = end;
  while(cur !== undefined && cur !== null){
    path.unshift(cur);
    cur = pred[cur];
  }
  return path;
}

function applyPath(path){
  // path alternates: x0(add), y1(remove), x2(add), ...
  // elements at even positions are added, odd positions removed from S
  const newS = new Set(S);
  for(let i=0;i<path.length;i++){
    if(i%2===0) newS.add(path[i]);
    else newS.delete(path[i]);
  }
  return [...newS];
}

function doStep(){
  if(done) return;
  stepCount++;
  const path = findAugPath();
  if(!path){
    done = true;
    lastAdded = [];
    lastRemoved = [];
    augPath = [];
    render();
    setStatus('✓ Optimal! No augmenting path exists — current set is maximum.','done');
    return;
  }
  augPath = path;
  lastAdded = path.filter((_,i)=>i%2===0);
  lastRemoved = path.filter((_,i)=>i%2!==0);
  S = applyPath(path);
  render();
  setStatus(fmt('Augmented along path [%map%] — size now %length%.', { map: path.map(id=>'e'+id).join('→'), length: S.length }),'working');
}

// Drawing
const pos1 = [ // vertex positions for graph 1 canvas (220x180)
  [110,20],[200,80],[160,160],[60,160],[20,80]
];
const pos2 = [ // same layout for graph 2 canvas
  [110,20],[200,80],[160,160],[60,160],[20,80]
];

function drawGraph(canvasId, graphKey, positions, color){
  const cv = document.getElementById(canvasId);
  const ctx = cv.getContext('2d');
  ctx.clearRect(0,0,cv.width,cv.height);
  const inS = new Set(S);

  for(const e of EDGES){
    const [u,v] = e[graphKey];
    const [x1,y1] = positions[u];
    const [x2,y2] = positions[v];
    ctx.beginPath();
    ctx.moveTo(x1,y1); ctx.lineTo(x2,y2);
    if(inS.has(e.id)){
      if(lastAdded.includes(e.id)){
        ctx.strokeStyle = '#16a34a'; ctx.lineWidth = 3.5;
      } else if(lastRemoved.includes(e.id)){
        ctx.strokeStyle = '#dc2626'; ctx.lineWidth = 3;
        ctx.setLineDash([5,4]);
      } else {
        ctx.strokeStyle = color; ctx.lineWidth = 3;
      }
    } else {
      ctx.strokeStyle = '#c5cdd6'; ctx.lineWidth = 1.5;
      ctx.setLineDash([3,3]);
    }
    ctx.stroke();
    ctx.setLineDash([]);
    // edge label
    const mx = (x1+x2)/2, my = (y1+y2)/2;
    ctx.fillStyle = inS.has(e.id) ? '#1d3557' : '#8a9bae';
    ctx.font = 'bold 10px system-ui';
    ctx.fillText('e'+e.id, mx+3, my-3);
  }
  // vertices
  for(let i=0;i<V;i++){
    const [x,y] = positions[i];
    ctx.beginPath(); ctx.arc(x,y,10,0,2*Math.PI);
    ctx.fillStyle='#fff'; ctx.strokeStyle='#1d3557'; ctx.lineWidth=1.8;
    ctx.fill(); ctx.stroke();
    ctx.fillStyle='#1d3557'; ctx.font='bold 11px system-ui';
    ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(i,x,y);
  }
}

function render(){
  drawGraph('c1','g1',pos1,'#2563eb');
  drawGraph('c2','g2',pos2,'#dc2626');
  document.getElementById('sol-size').textContent = S.length;
  document.getElementById('step-num').textContent = stepCount;
  const el = document.getElementById('edge-list');
  if(S.length){
    el.textContent = fmt('Current set S = {%map%}', { map: S.map(id=>'e'+id).join(', ') });
  } else {
    el.textContent = 'Current set S = ∅ (empty)';
  }
}

function setStatus(t, cls){
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + (cls||'');
}

let runTimer = null;
document.getElementById('btn-step').addEventListener('click',()=>{ clearInterval(runTimer); doStep(); });
document.getElementById('btn-run').addEventListener('click',()=>{
  if(done) return;
  clearInterval(runTimer);
  runTimer = setInterval(()=>{ doStep(); if(done) clearInterval(runTimer); }, 600);
});
document.getElementById('btn-reset').addEventListener('click',()=>{
  clearInterval(runTimer);
  S=[]; stepCount=0; done=false; augPath=[]; lastAdded=[]; lastRemoved=[];
  render();
  setStatus('Press Step or Run to start the augmenting-path algorithm.','');
});
render();
Result
Console

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.

The Real Complexity

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(r2⋅T)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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/matroid-intersection/Content licensed under CC BY-NC 4.0.