Matroid Theory — Matroid Intersection & Greedy on Matroids

January 2026 · 30 min read

What Is a Matroid?

A matroid is a combinatorial structure that abstracts the notion of independence common to linear algebra (linearly independent vectors), graph theory (acyclic edge sets), and many other domains. Formally, a matroid is a pair M = (E, Ι) where E is a finite ground set and Ι ⊆ 2^E is a family of subsets called independent sets satisfying three axioms:

1. (I1) Non-emptiness. The empty set is independent: ∅ ∈ Ι.
2. (I2) Hereditary property. Every subset of an independent set is independent: if B ∈ Ι and A ⊆ B, then A ∈ Ι.
3. (I3) Augmentation (Exchange) property. If A, B ∈ Ι with |A| < |B|, then there exists an element e ∈ B \ A such that A ∪ {e} ∈ Ι.

These axioms look deceptively simple, but they capture a powerful structural property: any greedy strategy that builds up an independent set one element at a time will find an optimal solution. Let us look at some classic matroid families.

Graphic Matroid (Cycle Matroid)

Given an undirected graph G = (V, E), let the ground set be E (the edges) and define a subset F ⊆ E as independent if F is acyclic (i.e., a forest). The resulting matroid is called the graphic matroid or cycle matroid M(G). A basis (maximal independent set) is a spanning forest of G, and the rank function gives r(A) = |V| − c(A) where c(A) is the number of connected components of (V, A).

Uniform Matroid U_k,n

The ground set has n elements and a set is independent iff its cardinality is at most k. Every subset of size ≤ k is independent, so any k-element subset is a basis. The rank function is simply r(A) = min(|A|, k).

Partition Matroid

The ground set E is partitioned into disjoint groups E₁, E₂, …, E_m with capacities k₁, k₂, …, k_m. A set I is independent iff |I ∩ E_i| ≤ k_i for every group i. This generalises the uniform matroid (m = 1) and appears in scheduling problems where each machine can handle at most k_i tasks.

Linear (Vector) Matroid

Given a set of vectors v₁, …, v_n in a vector space, a subset is independent iff the corresponding vectors are linearly independent. Every graphic matroid is representable as a linear matroid over any field (the incidence matrix serves as the representation). The converse does not hold — some linear matroids are not graphic.

Matroid Axioms and Properties

There are several equivalent ways to define a matroid. Each perspective is useful in different situations.

Independent Set Axioms (I1, I2, I3)

Already stated above. These are the most common in competitive programming because the independence oracle isIndependent(S) is what our algorithms call.

Basis Axioms

A basis is a maximal independent set. The bases of a matroid satisfy:

1. (B1) The set of bases is non-empty.
2. (B2) Basis exchange. For any two bases B₁, B₂ and any e ∈ B₁ \ B₂, there exists f ∈ B₂ \ B₁ such that (B₁ \ {e}) ∪ {f} is also a basis.

A crucial consequence: all bases have the same cardinality. This cardinality is the rank of the matroid.

Circuit Axioms

A circuit is a minimal dependent set. Circuits satisfy:

1. (C1) ∅ is not a circuit.
2. (C2) No circuit properly contains another circuit.
3. (C3) Weak elimination. If C₁, C₂ are distinct circuits and e ∈ C₁ ∩ C₂, then there exists a circuit C₃ ⊆ (C₁ ∪ C₂) \ {e}.

In the graphic matroid, circuits are exactly the simple cycles of the graph.

Rank Function

The rank function r : 2^E → ℤ is defined as r(A) = max { |I| : I ⊆ A, I ∈ Ι }. It satisfies:

1. (R1) 0 ≤ r(A) ≤ |A| for all A ⊆ E.
2. (R2) Monotonicity. If A ⊆ B then r(A) ≤ r(B).
3. (R3) Submodularity. r(A ∪ B) + r(A ∩ B) ≤ r(A) + r(B).

Submodularity is the key property that makes matroid optimisation tractable. Any function satisfying (R1)–(R3) is the rank function of some matroid.

The Greedy Algorithm on Matroids

The greedy algorithm is perhaps the most important algorithmic consequence of matroid theory. It solves the weighted matroid optimisation problem: given a matroid M = (E, Ι) and a weight function w : E → ℝ, find a basis B that maximises Σ_e∈B w(e).

Proof Sketch

(⇒) Suppose (E, Ι) is a matroid. We prove greedy is optimal by an exchange argument. Let G = {g₁, …, g_r} be the greedy solution (elements added in that order) and O = {o₁, …, o_r} be any optimal basis sorted by decreasing weight. We show w(g_i) ≥ w(o_i) for every i by induction. If w(g_i) < w(o_i) for some i, the augmentation axiom would let us extend {g₁, …, g_i−1} with some o_j of weight ≥ w(o_i) > w(g_i), contradicting the greedy choice.

(⇐) If (E, Ι) is not a matroid, the augmentation axiom fails for some A, B. A carefully chosen weight function makes greedy get stuck at A while the optimal solution is B.

Classic Example: Kruskal’s Algorithm

Kruskal’s algorithm for minimum spanning trees is exactly the greedy algorithm on the graphic matroid! The ground set is the edge set E, the independent sets are forests, and the weight function is the negated edge weight (since we want minimum total weight, we maximise negated weights). The independence oracle “does adding this edge create a cycle?” is answered with a Disjoint Set Union (DSU) structure in near-constant amortised time.

Weighted Matroid Optimisation

More generally, for any weighted matroid, the greedy algorithm runs in O(|E| log |E| + |E| · T_oracle) time, where T_oracle is the cost of the independence oracle. For the graphic matroid with DSU, T_oracle = O(α(n)), giving the familiar O(m log m) for Kruskal’s algorithm.

Matroid Intersection

While a single matroid yields to greedy, many problems require finding a maximum-weight set that is independent in two matroids simultaneously. This is the matroid intersection problem.

Problem Statement

Given two matroids M₁ = (E, Ι₁) and M₂ = (E, Ι₂) on the same ground set E, find a set S ⊆ E of maximum cardinality (or maximum weight) such that S ∈ Ι₁ and S ∈ Ι₂.

Unlike the greedy algorithm which runs in polynomial time for one matroid, intersection of three or more matroids is NP-hard in general. But for exactly two matroids, Edmonds (1970) showed a beautiful polynomial-time algorithm exists.

The Exchange Graph

Let S be the current common independent set. Build a directed bipartite graph D_S = (S, E \ S, A) as follows:

• For each y ∈ E \ S and x ∈ S: add arc (y → x) if S − {x} + {y} ∈ Ι₁.
• For each x ∈ S and y ∈ E \ S: add arc (x → y) if S − {x} + {y} ∈ Ι₂.

Define X₁ = { y ∈ E\S : S + {y} ∈ Ι₁ } and X₂ = { y ∈ E\S : S + {y} ∈ Ι₂ }. Find a shortest path from any vertex in X₁ to any vertex in X₂ in D_S. If such a path P exists, augment: S ← S Δ V(P) (symmetric difference). This increases |S| by exactly 1.

If no augmenting path exists, S is a maximum common independent set.

Complexity

Each augmenting-path search takes O(|E|²) oracle calls (BFS over the exchange graph). We do at most r augmentations where r is the final rank. Total: O(r · |E|²) oracle calls. For weighted matroid intersection, shortest augmenting paths with a potential function give O(r · |E|² · log |E|).

Applications

C++ Implementation

Matroid Base Class and Graphic Matroid with DSU

We start with an abstract matroid interface and the graphic matroid that answers independence queries using a Disjoint Set Union structure.

#include <bits/stdc++.h>
using namespace std;

// Abstract matroid: ground set is {0, 1, ..., n-1}
struct Matroid {
    int n;
    Matroid(int n) : n(n) {}
    // Returns true if adding element e to the current independent set is ok.
    // The current set is encoded externally; concrete matroids manage their own state.
    virtual void clear() = 0;
    virtual bool canAdd(int e) = 0;
    virtual void add(int e) = 0;
    virtual void remove(int e) = 0;
    virtual ~Matroid() = default;
};

// DSU (Union-Find) for the graphic matroid
struct DSU {
    vector<int> par, rnk;
    DSU() = default;
    DSU(int n) : par(n), rnk(n, 0) { iota(par.begin(), par.end(), 0); }
    int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        par[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

// Graphic matroid: independent sets are forests
struct GraphicMatroid : Matroid {
    int V;
    vector<pair<int,int>> edges; // ground set: edges[i] = (u, v)
    DSU dsu;
    vector<bool> inSet;

    GraphicMatroid(int V, vector<pair<int,int>>& edges)
        : Matroid(edges.size()), V(V), edges(edges),
          dsu(V), inSet(edges.size(), false) {}

    void clear() override {
        dsu = DSU(V);
        fill(inSet.begin(), inSet.end(), false);
    }

    // Rebuild DSU from current set (needed after remove)
    void rebuild() {
        dsu = DSU(V);
        for (int i = 0; i < n; i++)
            if (inSet[i]) dsu.unite(edges[i].first, edges[i].second);
    }

    bool canAdd(int e) override {
        return dsu.find(edges[e].first) != dsu.find(edges[e].second);
    }

    void add(int e) override {
        inSet[e] = true;
        dsu.unite(edges[e].first, edges[e].second);
    }

    void remove(int e) override {
        inSet[e] = false;
        rebuild();
    }
};

Partition Matroid

Each element belongs to a group, and each group has a capacity. A set is independent iff no group exceeds its capacity.

// Partition matroid: ground set partitioned into groups with capacities
struct PartitionMatroid : Matroid {
    vector<int> group;      // group[e] = which group element e belongs to
    vector<int> capacity;   // max elements per group
    vector<int> count;      // current count per group

    PartitionMatroid(int n, vector<int>& group, vector<int>& capacity)
        : Matroid(n), group(group), capacity(capacity),
          count(capacity.size(), 0) {}

    void clear() override { fill(count.begin(), count.end(), 0); }

    bool canAdd(int e) override {
        return count[group[e]] < capacity[group[e]];
    }

    void add(int e) override { count[group[e]]++; }

    void remove(int e) override { count[group[e]]--; }
};

Greedy Algorithm on a Weighted Matroid

The following function finds a maximum-weight independent set (basis) using the greedy strategy.

// Greedy algorithm: maximum-weight independent set in a matroid
vector<int> greedyMatroid(Matroid& M, vector<double>& weight) {
    vector<int> order(M.n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b) {
        return weight[a] > weight[b];
    });

    M.clear();
    vector<int> result;
    for (int e : order) {
        if (weight[e] <= 0) break; // skip non-positive weights
        if (M.canAdd(e)) {
            M.add(e);
            result.push_back(e);
        }
    }
    return result;
}

Matroid Intersection (Augmenting Paths)

The following implementation finds a maximum-cardinality common independent set of two matroids using the augmenting-path approach on the exchange graph.

// Matroid intersection: max cardinality common independent set of M1, M2
vector<int> matroidIntersection(Matroid& M1, Matroid& M2) {
    int n = M1.n;
    vector<bool> inS(n, false);

    // Helper: set up matroid state from current inS
    auto buildState = [&](Matroid& M) {
        M.clear();
        for (int i = 0; i < n; i++)
            if (inS[i]) M.add(i);
    };

    while (true) {
        // Collect elements in S and outside S
        vector<int> S, outside;
        for (int i = 0; i < n; i++) {
            if (inS[i]) S.push_back(i);
            else outside.push_back(i);
        }

        // X1 = {y not in S : S + y in I1}
        // X2 = {y not in S : S + y in I2}
        buildState(M1);
        vector<bool> X1(n, false);
        for (int y : outside)
            if (M1.canAdd(y)) X1[y] = true;

        buildState(M2);
        vector<bool> X2(n, false);
        for (int y : outside)
            if (M2.canAdd(y)) X2[y] = true;

        // BFS on the exchange graph to find shortest augmenting path
        // Nodes: all elements 0..n-1
        // Arcs from y (outside) to x (in S): S-x+y in I1
        // Arcs from x (in S) to y (outside): S-x+y in I2
        vector<int> prev(n, -2); // -2 = unvisited, -1 = source
        queue<int> q;

        // Start BFS from all elements in X1
        for (int y : outside) {
            if (X1[y]) {
                prev[y] = -1;
                q.push(y);
            }
        }

        int target = -1;
        while (!q.empty() && target == -1) {
            int cur = q.front(); q.pop();

            if (!inS[cur]) {
                // cur is outside S, try arcs to elements in S (via M1 exchange)
                for (int x : S) {
                    if (prev[x] != -2) continue;
                    // Check: S - x + cur in I1?
                    buildState(M1);
                    M1.remove(x);
                    if (M1.canAdd(cur)) {
                        prev[x] = cur;
                        q.push(x);
                    }
                }
            } else {
                // cur is in S, try arcs to elements outside S (via M2 exchange)
                for (int y : outside) {
                    if (prev[y] != -2) continue;
                    // Check: S - cur + y in I2?
                    buildState(M2);
                    M2.remove(cur);
                    if (M2.canAdd(y)) {
                        prev[y] = cur;
                        q.push(y);
                        // If y is in X2, we found an augmenting path!
                        if (X2[y]) { target = y; break; }
                    }
                }
            }
        }

        if (target == -1) break; // no augmenting path: S is maximum

        // Trace back and augment: flip membership along the path
        int v = target;
        while (v != -1) {
            inS[v] = !inS[v];
            v = prev[v];
        }
    }

    vector<int> result;
    for (int i = 0; i < n; i++)
        if (inS[i]) result.push_back(i);
    return result;
}

Usage Example: Colourful Spanning Tree

Given a graph with coloured edges, find a spanning tree using at most one edge of each colour. We intersect the graphic matroid with a partition matroid.

int main() {
    int V, E;
    cin >> V >> E;

    vector<pair<int,int>> edges(E);
    vector<int> colour(E);
    int numColours = 0;

    for (int i = 0; i < E; i++) {
        cin >> edges[i].first >> edges[i].second >> colour[i];
        numColours = max(numColours, colour[i] + 1);
    }

    // M1: graphic matroid (forests)
    GraphicMatroid M1(V, edges);

    // M2: partition matroid (at most 1 edge per colour)
    vector<int> cap(numColours, 1);
    PartitionMatroid M2(E, colour, cap);

    vector<int> tree = matroidIntersection(M1, M2);

    if ((int)tree.size() == V - 1) {
        cout << "Colourful spanning tree found:\n";
        for (int e : tree)
            cout << edges[e].first << " -- "
                 << edges[e].second << " (colour "
                 << colour[e] << ")\n";
    } else {
        cout << "No colourful spanning tree exists.\n";
    }
    return 0;
}

CP Applications

Matroid theory shows up more often in competitive programming than you might expect. The key skill is recognising matroid structure in a problem.

Pattern 1: Minimum Spanning Forest = Graphic Matroid

Any problem that boils down to building a minimum-cost acyclic edge set is a weighted optimisation on the graphic matroid. This includes MST, minimum spanning forest, and any “connect components at minimum cost” variant. Kruskal’s algorithm is the canonical greedy solution, running in O(m log m).

Pattern 2: Scheduling as Partition Matroid

Consider the classic job scheduling problem: you have n jobs, each with a deadline d_i and a profit p_i. Each job takes one time unit. Maximise total profit. The time slots form a partition: group g contains jobs with deadline = g, and the capacity of each group is 1 (or the number of available machines). This is exactly a weighted partition matroid, solvable by greedy in O(n log n).

Pattern 3: Colourful / Rainbow Spanning Tree

As shown in the implementation section, finding a spanning tree that uses at most one edge per colour is a matroid intersection of a graphic matroid and a partition matroid. The matroid intersection algorithm solves this in O(V · E²) oracle calls.

Pattern 4: Arborescence and Transversal Problems

A transversal matroid (also called an assignment matroid) arises when you want to select a system of distinct representatives from a bipartite graph. Matroid intersection can solve transversal problems that combine two different notions of independence. For example: select a set of edges forming both a forest and a system of distinct representatives.

How to Recognise Matroid Structure

Ask yourself these questions when reading a CP problem:

1. Is there a notion of “independence”? Can you define which subsets of the objects are “valid” or “feasible”?
2. Is the system hereditary? If a set is valid, is every subset also valid?
3. Does augmentation hold? Given two valid sets of different sizes, can you always add an element from the larger to the smaller and stay valid?
4. Are there two independent notions of feasibility? If so, matroid intersection may apply.

Summary

Matroid theory provides a unifying framework for understanding when and why greedy algorithms work. Here are the key takeaways:

1. A matroid is defined by the hereditary and augmentation axioms on independent sets. Key examples: graphic (forests), uniform (size-bounded), partition (group capacities), and linear (vector independence).
2. Equivalent formulations via bases, circuits, and the rank function provide different angles for proofs and algorithm design.
3. The Rado–Edmonds theorem states that greedy works for all weight functions if and only if the structure is a matroid.
4. Kruskal’s algorithm is the greedy algorithm on the graphic matroid — the quintessential example.
5. Matroid intersection finds a maximum common independent set of two matroids in polynomial time via augmenting paths in the exchange graph.
6. Applications in CP include MST, scheduling, colourful spanning trees, bipartite matching, and transversal problems.

When you encounter a problem that asks for a maximum-weight feasible set, always check whether the feasibility structure is a matroid. If it is, you have a clean and provably correct algorithmic approach.