The problem is that we attempt to solve the simplest questions cleverly,
thereby rendering them unusually complex.
One should seek the simple solution.
— Anton Pavlovich Chekhov (c. 1890)
I love deadlines. I like the whooshing sound they make as they ﬂy by.
— Douglas Adams, The Salmon of Doubt (2002)

EMatroids[Read Chapter 4 and 7 ﬁrst.]
Status: Needs signiﬁcant revision or deletion
Merge into greedy notes as hardsection?

E.1

Deﬁnitions

Many problems that can be correctly solved by greedy algorithms can be described interms of an abstract combinatorial object called a matroid. Matroids were first describedin 1935 by the mathematician Hassler Whitney as a combinatorial generalization of linear
independence of vectors—“matroid” means “something sort of like a matrix”.
A matroid (S, I) consists of a finite ground set S and a collection I of subsets of X
that satisfies three axioms:• Non-emptiness: The empty set is in I. (Thus, I is not itself empty.)• Heredity: If I contains a subset X ⊆ S, then I contains every subset of X .
• Exchange: If X and Y are two sets in I where |X | > |Y |, then Y ∪ {x} ∈ I for someelement x ∈ X \ Y .
© 2018 Jeff Erickson

http://algorithms.wtf

1E. MATROIDS

The subsets in I are typically called independent sets; for example, we would say thatany subset of an independent set is independent. An independent set is called a basisof the matroid if it is not a proper subset of another independent set. The exchange
property implies that every basis of a matroid has the same cardinality. The rank of asubset X of the ground set is the size of the largest independent subset of X . A subset
of S that is not in I is called dependent (surprise, surprise). Finally, a dependent set iscalled a circuit if every proper subset is independent.
Most of this terminology is justified by Whitney’s original example:• Linear matroid: Let A be any n × m matrix. A subset I ⊆ {1, 2, . . . , n} is independent
if and only if the corresponding subset of columns of A is linearly independent.
The heredity property follows directly from the definition of linear independence; theexchange property is implied by an easy dimensionality argument. A basis in any linear
matroid is also a basis (in the linear-algebra sense) of the vector space spanned by
the columns of A. Similarly, the rank of a set of indices is precisely the rank (in thelinear-algebra sense) of the corresponding set of column vectors.
Here are several other examples of matroids; some of these we will see again later. I
will leave the proofs that these are actually matroids as exercises for the reader.
• Uniform matroid Uk,n : A subset X ⊆ {1, 2, . . . , n} is independent if and only if|X | ≤ k. Any subset of {1, 2, . . . , n} of size k is a basis; any subset of size k + 1 is acircuit.
• Graphic/cycle matroid M(G): Let G = (V, E) be an arbitrary undirected graph. A
subset of E is independent if it defines an acyclic subgraph of G. A basis in the graphic
matroid is a spanning tree of G; a circuit in this matroid is a cycle in G.
• Cographic/cocycle matroid M∗ (G): Let G = (V, E) be an arbitrary undirectedgraph. A subset I ⊆ E is independent if the complementary subgraph (V, E \ I) of G
is connected. A basis in this matroid is the complement of a spanning tree; a circuitin this matroid is a cocycle—a minimal set of edges that disconnects the graph.
• Matching matroid: Let G = (V, E) be an arbitrary undirected graph. A subset I ⊆ Vis independent if there is a matching in G that covers I.
• Disjoint path matroid: Let G = (V, E) be an arbitrary directed graph, and let s be afixed vertex of G. A subset I ⊆ V is independent if and only if there are edge-disjoint
paths from s to each vertex in I.
Now suppose each element of the ground set of a matroid M is given an arbitrary
non-negative weight. The matroid optimization problem is to compute a basis withmaximum total weight. For example, if M is the cycle matroid for a graph G, the matroid
optimization problem asks us to find the maximum spanning tree of G. Similarly, if M isthe cocycle matroid for G, the matroid optimization problem seeks (the complement of)
the minimum spanning tree.
2E.1. Deﬁnitions

The following natural greedy strategy computes a basis for any weighted matroid(S, I), where the ground set S is represented by an array S[1 .. n], and the weights ofground elements are represented by another array w[1 .. n].
GreedyBasis(S[1 .. n], I, w[1 .. n]):sort S in decreasing order of weight w
G←∅for i ← 1 to n
if G ∪ {S[i]} ∈ I
add S[i] to G
return G

Suppose we can test in F (n) time whether a given subset X ⊂ S is independent. Thenthis algorithm runs in O(n log n + n · F (n)) time.
Theorem E.1. For any matroid M = (S, I) and any weight function w, GreedyBasis(S, I, w)
returns a maximum-weight basis of M.
Proof: We use a standard exchange argument. Let G = {g1 , g2 , . . . , g k } be the independent set returned by GreedyBasis(S, I, w). If any other element of S could be added
to G to obtain a larger independent set, the greedy algorithm would have added it.
Thus, G is a basis.
For purposes of deriving a contradiction, suppose there is an independent set
H = {h1 , h2 , . . . , h` } such thatkXw(g i ) <X̀

i=1w(hi ).

j=1

Without loss of generality, assume that H is a basis. The exchange property now implies
that k = `.
Now suppose the elements of G and H are indexed in order of decreasing weight.
Let i be the smallest index such that w(g i ) < w(hi ), and consider the independent sets
Gi−1 = {g1 , g2 , . . . , g i−1 }andH i = {h1 , h2 , . . . , hi−1 , hi }.

By the exchange property, there is some element h j ∈ H i such that Gi−1 ∪ {h j } is anindependent set. We have w(h j ) ≥ w(hi ) > w(g i ). Thus, the greedy algorithm considers
and rejects the heavier element h j before it considers the lighter element g i . But this isimpossible—the greedy algorithm accepts elements in decreasing order of weight. We now immediately have a correct greedy optimization algorithm for any matroid.
Returning to our examples:• Linear matroid: Given a matrix A, compute a subset of vectors of maximum total
weight that span the column space of A.
3

E. MATROIDS• Uniform matroid: Given a set of weighted objects, compute its k largest elements.
• Cycle matroid: Given a graph with weighted edges, compute its maximum spanning
tree. In this setting, the greedy algorithm is better known as Kruskal’s algorithm.
• Cocycle matroid: Given a graph with weighted edges, compute its minimum spanningtree.
• Matching matroid: Given a graph, determine whether it has a perfect matching.
• Disjoint path matroid: Given a directed graph with a special vertex s, find the largest
set of edge-disjoint paths from s to other vertices.
The exchange condition for matroids turns out to be crucial for the success of thisalgorithm. A subset system is a finite collection S of finite sets that satisfies the heredity
condition—If X ∈ S and Y ⊆ X , then Y ∈ S—but not necessarily the exchange condition.
Theorem E.2. For any subset system S that is not a matroid, there is a weight function
w such that GreedyBasis(S, w) does not return a maximum-weight set in S.
Proof: Let X and Y be two sets in S that violate the exchange property—|X | > |Y |, butfor any element x ∈ X \ Y , the set Y ∪ {x} is not in S. Let m = |Y |. We define a weightfunction as follows:• Every element of Y has weight m + 2.
• Every element of X \ Y has weight m + 1.
• Every other element of the ground set has weight zero.
With these weights, the greedy algorithm will consider and accept every element of Y ,then consider and reject every element of X , and finally consider all the other elements.
The algorithm returns a set with total weight m(m + 2) = m2 + 2m. But the total weightof X is at least (m + 1)2 = m2 + 2m + 1. Thus, the output of the greedy algorithm is not
the maximum-weight set in S.
Recall the Applied Chaos scheduling problem considered in Chapter 4. There is anatural subset system associated with this problem: A set of classes is independent if
and only if no two classes overlap. (This is just the graph-theory notion of “independentset”!) This subset system is not a matroid, because there can be maximal independent
sets of different sizes, which violates the exchange property. If we consider a weighted
version of the class scheduling problem, where each class is worth a different number ofhours, Theorem ?? implies that the greedy algorithm will not always find the optimalschedule. (In fact, there’s an easy counterexample with only two classes!) However,Theorem ?? does not contradict the correctness of the greedy algorithm for the original
unweighted problem; that problem uses a particularly lucky choice of weights (all equal).
4E.2. Scheduling with Deadlines

E.2

Scheduling with Deadlines

Suppose you have n tasks to complete in n days; each task requires your attention fora full day. Each task comes with a deadline, the last day by which the job should becompleted, and a penalty that you must pay if you do not complete each task by its
assigned deadline. What order should you perform your tasks in to minimize the total
penalty you must pay?
More formally, you are given an array D[1 .. n] of deadlines an array P[1 .. n] ofpenalties. Each deadline D[i] is an integer between 1 and n, and each penalty P[i] is a
non-negative real number. A schedule is a permutation of the integers {1, 2, . . . , n}. Thescheduling problem asks you to find a schedule π that minimizes the following cost:
cost(π) :=nX

P[i] · [π(i) > D[i]].

i=1This doesn’t look anything like a matroid optimization problem. For one thing,matroid optimization problems ask us to find an optimal set; this problem asks us to findan optimal permutation. Surprisingly, however, this scheduling problem is actually amatroid optimization in disguise! For any schedule π, call tasks i such that π(i) > D[i]late, and all other tasks on time. The following trivial observation reveals the underlying
matroid structure.
The cost of a schedule is determined by the subset of tasks that are on time.
Call a subset X of the tasks realistic if there is a schedule π in which every task in X
is on time. We can precisely characterize the realistic subsets as follows. Let X (t) denotethe subset of tasks in X whose deadline is on or before t:
X (t) := {i ∈ X | D[i] ≤ t}.
In particular, X (0) = ∅ and X (n) = X .
Lemma E.3. Let X ⊆ {1, 2, . . . , n} be an arbitrary subset of the n tasks. X is realistic if
and only if |X (t)| ≤ t for every integer t.
Proof: Let π be a schedule in which every task in X is on time. Let i t be the tth task
in X to be completed. On the one hand, we have π(i t ) ≥ t, since otherwise, we could
not have completed t − 1 other jobs in X before i t . On the other hand, π(i t ) ≤ D[i],because i t is on time. We conclude that D[i t ] ≥ t, which immediately implies that|X (t)| ≤ t.
Now suppose |X (t)| ≤ t for every integer t. If we perform the tasks in X in increasingorder of deadline, then we complete all tasks in X with deadlines t or less by day t. In
particular, for any i ∈ X , we perform task i on or before its deadline D[i]. Thus, X isrealistic.
5E. MATROIDS

We can now define a canonical schedule for any set X as follows: execute the tasks
in X in increasing deadline order, and then execute the remaining tasks in any order. Theprevious proof implies that a set X is realistic if and only if every task in X is on time inthe canonical schedule for X . Thus, our scheduling problem can be rephrased as follows:
Find a realistic subset X such thatPi∈X P[i] is maximized.

So we’re looking for optimal subsets after all!
Lemma E.4. The collection of realistic sets of jobs forms a matroid.
Proof: The empty set is vacuously realistic, and any subset of a realistic set is clearly
realistic. Thus, to prove the lemma, it suffices to show that the exchange property holds.
Let X and Y be realistic sets of jobs with |X | > |Y |.
Let t ∗ be the largest integer such that |X (t ∗ )| ≤ |Y (t ∗ )|. This integer must exist,
because |X (0)| = 0 ≤ 0 = |Y (0)| and |X (n)| = |X | > |Y | = |Y (n)|. By definition of t ∗ ,there are more tasks with deadline t ∗ + 1 in X than in Y . Thus, we can choose a task jin X \ Y with deadline t ∗ + 1; let Z = Y ∪ { j}.
Let t be an arbitrary integer. If t ≤ t ∗ , then |Z(t)| = |Y (t)| ≤ t, because Y is realistic.
On the other hand, if t > t ∗ , then |Z(t)| = |Y (t)| + 1 ≤ |X (t)| < t by definition of t ∗and because X is realistic. The previous lemma now implies that Z is realistic. This
completes the proof of the exchange property.
This lemma implies that our scheduling problem is actually a matroid optimization
problem, so the greedy algorithm finds the optimal schedule.
GreedySchedule(D[1 .. n], P[1 .. n]):Sort P in increasing order, and permute D to matchj←0for i ← 1 to n
X [ j + 1] ← i
if X [1 .. j + 1] is realisticj ← j+1
return the canonical schedule for X [1 .. j]

To turn this outline into a real algorithm, we need a procedure to test whether agiven subset of jobs is realistic. Lemma 9 immediately suggests the following strategy toanswer this question in O(n) time.
6

Exercises

Realistic?(X [1 .. m], D[1 .. n]):〈〈X is sorted by increasing deadline: i ≤ j =⇒ D[X [i]] ≤ D[X [ j]]〉〉N ←0
j←0for t ← 1 to n
if D[X [ j]] = t
N ← N +1
j ← j+1〈〈Now N = |X (t)|〉〉if N > treturn False
return True

If we use this subroutine, GreedySchedule runs in O(n2 ) time. By using someappropriate data structures, the running time can be reduced to O(n log n); details areleft as an exercise for the reader.

Exercises
1. Prove that for any graph G, the “graphic matroid” M(G) is in fact a matroid. (Thisproblem is really asking you to prove that Kruskal’s algorithm is correct!)
2. Prove that for any graph G, the “cographic matroid” M∗ (G) is in fact a matroid.
©

©

3. Prove that for any graph G, the “matching matroid” of G is in fact a matroid. [Hint:What is the symmetric difference of two matchings?]

4. Prove that for any directed graph G and any vertex s of G, the resulting “disjointpath matroid” of G is in fact a matroid. [Hint: This question is much easier if you’realready familiar with maximum flows.]
5. Let G be an undirected graph. A set of cycles {c1 , c2 , . . . , ck } in G is called redundant
if every edge in G appears in an even number of ci ’s. A set of cycles is independent
if it contains no redundant subset. A maximal independent set of cycles is called acycle basis for G.
(a) Let C be any cycle basis for G. Prove that for any cycle γ in G, there is a subset
A ⊆ C such that A ∩ {γ} is redundant. In other words, γ is the ‘exclusive or’ of thecycles in A.
(b) Prove that the set of independent cycle sets form a matroid.
ª(c) Now suppose each edge of G has a weight. Define the weight of a cycle to be
the total weight of its edges, and the weight of a set of cycles to be the total
weight of all cycles in the set. (Thus, each edge is counted once for every cycle in7

E. MATROIDS

which it appears.) Describe and analyze an efficient algorithm to compute theminimum-weight cycle basis in G.
6. Describe a modification of GreedySchedule that runs in O(n log n) time. [Hint:
Store X in an appropriate data structure that supports the operations “Is X ∪ {i}realistic?” and “Add i to X ” in O(log n) time each.]8© 2018 Jeff Erickson

http://algorithms.wtf