Matroid Structure and the Exact Boundary of Greedy Optimality

Sort the elements by weight, scan them, and add each one whose addition preserves feasibility. On some problems this returns a maximum-weight feasible set and on others it does not, and the dividing line is not a matter of degree. There is a set of axioms on the family of feasible sets under which the scan is provably optimal, and any family violating them admits an instance on which the scan is wrong. The axioms define a matroid, introduced by Whitney in 1935 to abstract linear dependence, and they are the reason a single piece of code solves maximum-weight spanning trees, maximum-weight bases of a partition matroid, and maximum-weight independent sets in a transversal matroid on one side, while failing on knapsack and set cover on the other.

The axioms

A matroid $M = (E, \mathcal{I})$ consists of a finite ground set $E$ and a family $\mathcal{I}$ of subsets of $E$ called independent sets, satisfying:

1. Empty set. $\emptyset \in \mathcal{I}$.
2. Heredity. If $I \in \mathcal{I}$ and $J \subseteq I$, then $J \in \mathcal{I}$.
3. Exchange. If $I, J \in \mathcal{I}$ and $|I| < |J|$, there exists $x \in J \setminus I$ such that $I \cup {x} \in \mathcal{I}$.

The third axiom is the substantive one. It says that a smaller independent set can always be enlarged by an element of a larger one, which rules out the situation where a maximal independent set is trapped below the maximum size. Heredity alone permits such traps: take $E = {a, b, c}$ and let the independent sets be $\emptyset$, ${a}$, ${b}$, ${c}$ and ${a,b}$, with every other subset dependent. Heredity holds, yet both ${a,b}$ and ${c}$ are maximal, at sizes 2 and 1, and no element of ${a,b}$ can be added to ${c}$. The exchange axiom is what forbids this shape.

Two consequences follow immediately from the axioms, and both are used in the correctness proof. First, all maximal independent sets have the same cardinality, called the rank of the matroid; if $I$ and $J$ are maximal with $|I| < |J|$, the exchange axiom produces an element of $J$ that enlarges $I$, contradicting maximality. Second, the basis exchange property holds: for any two bases $B_1, B_2$ and any $x \in B_1 \setminus B_2$, there is $y \in B_2 \setminus B_1$ such that $B_1 - x + y$ is a basis.

The greedy algorithm on a matroid

With weights $w: E \to \mathbb{R}$, the algorithm sorts $E$ in decreasing weight and adds each element that keeps the current set independent. Its output is a maximum-weight basis, and when every weight is non-negative that basis is also a maximum-weight independent set.

def matroid_greedy(elements, weight, independent):
    # independent(S) tests membership in the matroid's family
    chosen = []
    for x in sorted(elements, key=weight, reverse=True):
        if independent(chosen + [x]):
            chosen.append(x)
    return chosen

Correctness has a clean induction, and the whole argument turns on two facts: heredity limits which element can be heaviest, and contraction preserves the matroid structure.

The first choice is safe. Let $x$ be the heaviest element of $E$ such that ${x}$ is independent; such an element is called a non-loop, and if none exists then every element is a loop, the only independent set is $\emptyset$, and the algorithm is trivially optimal. Let $B$ be a maximum-weight independent set containing as many elements as possible, so $B$ is a basis. If $x \in B$ there is nothing to prove. Otherwise $B \cup {x}$ is dependent, because $B$ is a maximal independent set, so it contains a circuit $C$ with $x \in C$. Write $C = {x} \cup C’$ with $C’ \subseteq B$ and $C’ \neq \emptyset$. For any $z \in C’$, the set ${z}$ is independent by heredity, and therefore $w(z) \le w(x)$ because $x$ was chosen heaviest among elements whose singleton set is independent. Minimality of the circuit gives that $B - {z} + {x}$ is a basis for every $z \in C’$: it is independent, since $C$ is the only circuit in $B \cup {x}$ and $z$ was removed from it, and it has $|B|$ elements. Its weight is $w(B) - w(z) + w(x) \ge w(B)$. So a maximum-weight basis containing $x$ exists. Heredity is what makes the weight comparison go the right way, and this is the step that fails for knapsack, where $B - {z} + {x}$ need not be feasible at all.

The subproblem is the same problem. Let $M/x$ denote the contraction of $M$ by $x$: its ground set is $E \setminus {x}$, and $S$ is independent in $M/x$ exactly when $S \cup {x}$ is independent in $M$. Contraction of a matroid is a matroid, so the contraction satisfies the three axioms, and greedy run on $M/x$ behaves exactly as greedy run on $M$ after the first step, because the independence test chosen + [x] in the code above is precisely the contraction test when chosen already contains $x$. An independent set containing $x$ has the form ${x} \cup S$ with $S$ independent in $M/x$, and its weight is $w(x) + w(S)$, so a maximum-weight independent set containing $x$ consists of $x$ plus a maximum-weight independent set of the contraction. Induction on $|E|$ then gives optimality of the full run.

The algorithm returns a maximum-weight basis. When all weights are non-negative, a maximum-weight basis is also a maximum-weight independent set, since any independent set extends to a basis without losing weight. With negative weights the two objectives diverge: greedy still returns a maximum-weight basis, but a maximum-weight independent set may be smaller, and the unmodified loop above will add negative-weight elements that a set-based objective would exclude.

Huffman coding, described in the merge argument, is the same exchange pattern without being a matroid problem: the feasible objects are trees rather than sets, so the axioms do not apply, yet the merge is safe because the two rarest symbols can always be exchanged into maximum depth at no cost. The pattern generalizes past matroids, and what it loses is the guarantee that the greedy rule is optimal for every weight function, not just the one the problem supplies.

The sort costs $O(n \log n)$ and the independence tests dominate the rest. For graphic matroids, independence testing is a connectivity query, and with a union-find structure the total is $O(n \log n)$ plus near-linear work.

Three matroids that carry the standard algorithms

Graphic matroid. $E$ is the edge set of a graph, and a set is independent if it contains no cycle. Heredity is immediate. The exchange axiom is the statement that a forest with fewer edges than another forest can be extended by an edge from the larger one, which follows from counting components: a forest on $n$ vertices with $k$ edges has $n - k$ components, so a smaller forest has more components, and some edge of the larger forest must connect two components of the smaller one. Kruskal’s algorithm is the greedy algorithm on this matroid with weights negated.

Partition matroid. $E$ is partitioned into classes $E_1, \dots, E_m$ with capacities $c_1, \dots, c_m$, and a set is independent if it takes at most $c_i$ elements from each class. This models scheduling with per-category limits and multiple-choice constraints. Sorting all elements by weight and filling each class from the top up to its capacity is optimal, which is why that rule is safe here even though the analogous rule fails for knapsack.

Transversal matroid. $E$ is a set of elements each adjacent to some vertices of a bipartite graph, and a set is independent if it can be matched into distinct vertices. This is the matroid underlying maximum bipartite matching, and the greedy algorithm on it computes a maximum-weight matching when the weights are on the left-hand elements. The independence test is an augmenting-path search, so the “greedy” algorithm is only as fast as that test; the matroid structure guarantees optimality, not speed.

Interval scheduling from the earliest-finish rule sits outside the theorem rather than inside it. The family of pairwise non-overlapping intervals is not a matroid: with intervals ${[0,10], [1,2], [3,4]}$ the set ${[0,10]}$ and the set ${[1,2],[3,4]}$ are both maximal, at sizes 1 and 2, so the exchange axiom fails. The matroid theorem is therefore sufficient for greedy optimality under the weight-ordering rule, not necessary for greedy optimality in general; interval scheduling is optimal by a different exchange, ordered by finish time rather than by weight, and that difference is what keeps it out of the matroid framework.

What fails, and how the failure is detectable

0/1 knapsack. $E$ is the item set, and a set is independent if its total weight is at most the capacity. Heredity holds: a subset of a feasible set is feasible. The exchange axiom fails. Take capacity 10, item $a$ with weight 6 and value 6.6, and items $b$ and $c$ with weight 5 and value 5 each. The set ${b, c}$ has size 2 and is independent; the set ${a}$ has size 1 and is independent. Exchange demands an element of ${b,c}$ that can be added to ${a}$, and neither can, since $6 + 5 > 10$. Both sets are maximal, with different cardinalities, which is exactly the shape the axiom forbids. The densities make the failure visible: greedy by value density takes $a$ first, at density $1.1$ against the others’ $1$, and then cannot fit either half, for a total value of 6.6 against an optimum of 10.

Set cover. Feasible sets are covers of the universe, which is an upward-closed family, not a downward-closed one. Heredity fails outright: a subset of a cover need not cover. The greedy algorithm still gives a logarithmic approximation, and that analysis lives in the harmonic bound for set cover.

The failure of the exchange axiom is not merely a proof inconvenience. It is a certificate: whenever two maximal independent sets of different sizes exist, an instance can be constructed on which weight-greedy is suboptimal, by giving the elements of the smaller maximal set slightly higher weight than the elements it blocks. So a family that fails the axiom admits no ordering of its elements for which the weight-greedy scan is optimal for every weight function.

Recognizing a matroid in a new problem

The practical question is usually whether a newly encountered constraint family is a matroid, and the fastest test is to look for two maximal independent sets of different sizes. If one exists, the family is not a matroid and greedy by weight is unsafe. If none exists, the family may still fail the exchange axiom, since the axiom is stronger than equal-rank maximal sets, but equal rank across all maximal sets plus heredity is the necessary condition and is usually enough to settle a design question.

A second test is closure under the operations that generate matroids. Direct sums, truncations, duals, and restrictions of matroids are matroids, so a constraint that decomposes into a partition matroid and a graphic matroid on disjoint ground sets is a matroid. Intersections of matroids are generally not matroids, and the intersection of two matroids is the setting for matroid intersection, a polynomial problem that is strictly harder than greedy and is solved by augmenting paths rather than by a single sort. Weighted matroid intersection is the natural home of problems that “almost” fit the greedy pattern, and the algorithmic cost rises from $O(n \log n)$ to a polynomial in $n$ and the rank.

The boundary is therefore sharp in a way that is unusual in algorithm design. On one side, one sort and one independence test. On the other, augmenting-path machinery with a substantially larger constant. Knowing which side a problem is on determines the algorithm before any code is written.