Matroids, in depth: independence oracles, rank and circuits, duality and minors, and greedy algorithms you can prove

Four views of one structure

A matroid is a finite ground set E with a family I of subsets called independent sets. Three rules define it: the empty set is independent; every subset of an independent set is independent (the hereditary rule); and if A and B are independent with |A| greater than |B|, some element of A minus B can be added to B and keep it independent (the augmentation rule). Four equivalent views exist.

Two consequences matter in practice. First, every basis has the same size, so the rank r(E) is a property of the matroid, not of the algorithm. Second, when you add an element e to an independent set I and the result is dependent, I plus e contains exactly one circuit, called the fundamental circuit of e. That is what a cycle check in Kruskal's algorithm finds, and it is what lets exchange arguments swap one element for another. The rank function is also submodular: r(S) + r(T) is at least r(S union T) + r(S intersect T). Matroid rank functions are the textbook family of submodular functions, and that link comes back at the end of this article.

The matroid catalogue and its oracles

In code, a matroid is an independence oracle: a function that answers whether a set is independent, or, more usefully, whether one more element can be added to the current set. Recognising the matroid in a problem mostly means recognising the oracle. The common ones are below, with the incremental cost per query when you keep state between calls.

The graphic oracle is union-find: an edge is addable exactly when its endpoints are in different components. The linear oracle keeps a reduced basis and asks whether a new vector reduces to zero. The deadline matroid is a special case of a transversal matroid, where jobs are matched to time slots; it is the structure behind job scheduling with deadlines. Nested product caps, such as 3 per brand and 10 in total, are laminar.

One greedy for every matroid

Because every matroid is just an oracle, one greedy serves all of them. Sort by weight, stop at the first non-positive weight, and add each element the oracle accepts. The early stop gives a maximum-weight independent set. If you need a maximum-weight basis instead, such as a spanning tree that must connect everything, drop it and take every addable element.

def greedy(items, oracle):
    """items: (weight, element) pairs. Returns a max-weight independent set."""
    chosen = []
    for w, e in sorted(items, key=lambda t: t[0], reverse=True):
        if w <= 0:
            break                        # omit for a max-weight basis
        if oracle.can_add(e):
            oracle.add(e)
            chosen.append((w, e))
    return chosen


class GraphicOracle:                     # forests, via union-find
    def __init__(self, nodes):
        self.parent = {v: v for v in nodes}
    def find(self, v):
        while self.parent[v] != v:
            self.parent[v] = self.parent[self.parent[v]]
            v = self.parent[v]
        return v
    def can_add(self, e):
        u, v = e
        return self.find(u) != self.find(v)
    def add(self, e):
        u, v = e
        self.parent[self.find(u)] = self.find(v)


class GF2Oracle:                         # vectors as int bitmasks over GF(2)
    def __init__(self):
        self.basis = {}                  # leading bit -> basis vector
    def reduce(self, x):
        for bit in sorted(self.basis, reverse=True):
            if x >> bit & 1:
                x ^= self.basis[bit]
        return x
    def can_add(self, e):
        return self.reduce(e) != 0
    def add(self, e):
        x = self.reduce(e)
        self.basis[x.bit_length() - 1] = x

The total cost is one sort plus n oracle queries. For the graphic matroid that is O(E log E), which is exactly Kruskal's algorithm; negate the weights and you get a minimum spanning tree. The GF(2) oracle uses exact integer arithmetic, which matters: an oracle that answers wrongly even occasionally turns a proof into a heuristic.

Worked example: tracing the greedy

Take vertices A to E and edges AB 9, BD 8, AC 7, BC 6, CD 5, CE 4 and DE 3, already in descending order. The greedy keeps AB, BD and AC because each joins two components. BC is rejected: B and C are already joined through A, and its fundamental circuit is {AB, AC, BC}. CD is rejected for the same reason, with circuit {CD, AC, AB, BD}. CE joins E for the first time and is kept. DE closes a cycle and is rejected. The result has 4 edges and weight 28.

Check it against the theory. The rank of the whole edge set is 5 vertices minus 1 component, so 4, and every basis has 4 edges. The weight is optimal by the cycle property: each rejected edge is the lightest edge in its fundamental circuit, so swapping it in for any edge of that circuit would lower the total. The same trace on a linear matroid over GF(2) with vectors 1100 (weight 5), 0110 (4), 1010 (3), 0011 (2) and 1001 (1) keeps 1100, 0110 and 0011. It rejects 1010 because it equals 1100 XOR 0110, and rejects 1001 because it equals the XOR of all three kept vectors. The rank is 3.

Why the greedy is optimal

The correctness proof is short and worth knowing, because the same argument is how you check a new oracle. Let the greedy pick g1, g2, and so on in the order it takes them, so their weights are non-increasing. Let I be any independent set of positive-weight elements, sorted as i1, i2, and so on by descending weight. The claim is that w(g_j) is at least w(i_j) for every j. Summing over j then shows the greedy total is at least w(I).

Suppose the claim fails, and let j be the first position where w(i_j) is greater than w(g_j). Let A be {i1, ..., i_j}, with j elements, and B be {g1, ..., g_(j-1)}, with j - 1 elements. Both are independent, and A is larger, so augmentation gives some i_t in A minus B for which B plus i_t is independent. Its weight is at least w(i_j), which is greater than w(g_j), so the greedy examined i_t before g_j. At that moment the chosen set was a subset of B, and by the hereditary rule that subset plus i_t was independent. The greedy would have taken i_t. Contradiction. The same augmentation step also rules out I having more positive elements than the greedy's set.

The converse explains the failures. If a downward-closed family violates augmentation, there are independent sets A and B with |A| greater than |B| and no element of A that extends B. Give B's elements weight just above A's elements, and everything else zero. The greedy takes B first, gets stuck, and loses to A.

Duality and minors: forced and forbidden items

Every matroid M has a dual M*. Its bases are the complements of M's bases, and its rank function is r*(S) = |S| - r(E) + r(E minus S). Duality turns problems inside out. In a network whose links form a graphic matroid, the cographic dual answers which links can be decommissioned without disconnecting anything. The maximum-weight basis of M* is the complement of a minimum-weight basis of M, so the largest set of removable links by saved cost is everything outside a minimum spanning tree. One greedy answers both questions.

Minors handle the business rules that otherwise break a clean greedy. Deleting an element removes it from the ground set, which is how you forbid an item. Contracting an independent element forces it into every solution: the independent sets of the contraction M/e are the sets S with S plus e independent in M. In code, contraction means calling oracle.add(e) for every mandatory element before the greedy loop starts. Deletion means filtering the item list. Both keep the structure a matroid, so the optimality proof still holds for the remaining choices. Mandatory items that are dependent among themselves are an infeasible input; detect that and report it rather than silently dropping one.

Beyond one matroid

The intersection of two matroids is usually not a matroid. In bipartite matching, each side's at-most-once rule is a partition matroid, but matchings fail augmentation. With edges a1-b1 of weight 3, a1-b2 of weight 2 and a2-b1 of weight 2, the greedy takes a1-b1 and stops at 3, while a1-b2 plus a2-b1 gives 4. Maximum-weight common independent sets of two matroids can still be found in polynomial time with Edmonds' matroid intersection algorithm, which generalises the augmenting paths of bipartite matching. Its correctness rests on a min-max theorem of the kind explained in LP duality. For three or more matroids the problem is NP-hard, since it contains Hamiltonian path, and the plain greedy on k matroids is a 1/k approximation.

The union of matroids is a matroid, which is how you pack k edge-disjoint spanning trees. When the objective is not a sum of weights but a monotone submodular function, such as coverage or diversity, the greedy that adds the best marginal gain among addable elements is a 1/2 approximation under a single matroid. The continuous greedy with rounding reaches 1 - 1/e. A common use in data work is choosing shards that cover the most distinct topics with a per-source cap:

def greedy_submodular(ground, f, oracle, k):
    S = []
    for _ in range(k):
        base, best, gain = f(S), None, 0.0
        for e in ground:
            if e in S or not oracle.can_add(e):
                continue
            g = f(S + [e]) - base          # marginal gain
            if g > gain:
                best, gain = e, g
        if best is None:
            break
        oracle.add(best)
        S.append(best)
    return S

With a partition oracle capping web shards at 2 and code shards at 1, and f counting distinct topics covered, this picks the widest web shard first and then fills each source's quota with whatever adds the most new coverage. Lazy evaluation with a priority queue of stale gains cuts the O(nk) evaluations sharply, because submodular gains only shrink.

Failure modes

• Assuming a matroid that is not there. Knapsack weights, pairwise conflicts and two-sided caps break augmentation. Before trusting a greedy, search small cases by brute force for a pair A and B that cannot augment.
• Negative or zero weights in a max-weight set. Without the early stop the greedy adds harmful elements. With it, a max-weight basis is no longer guaranteed. Decide which one you need.
• Floating-point rank. Linear oracles in floating point declare nearly dependent vectors independent, or the reverse. Use exact arithmetic, a finite field, or a tolerance you have tested against the conditioning of your data.
• Reused oracles. Incremental oracles hold state; reusing one silently contracts the previous run's choices.

Trade-offs

What to do next

1. Write down the feasible sets of your selection problem and test hereditary and augmentation on small cases by brute force.
2. If it is a matroid, name the type from the catalogue above and implement its incremental oracle.
3. Use the generic greedy, and choose explicitly between a maximum-weight independent set and a maximum-weight basis.
4. Model mandatory items as contractions and forbidden items as deletions; reject inputs whose mandatory items are dependent.
5. Add a property test that compares the greedy against brute force on random small instances.
6. If you find two crossing constraints, switch to matroid intersection or an integer program rather than tuning the greedy.
7. For coverage or diversity objectives, use the marginal-gain greedy with lazy evaluation and report the 1/2 bound honestly.