Matroids are pretty cool objects. They generalize the notion of independence, and they can extend Kruskal’s algorithm. This is mostly the basic properties about them, up to how they can extend Kruskal’s algorithm. There are some other more involved, but related, properties about them, like rank, duality, circuits, minors, and span, but this is already getting long (or should I say long long).
Matroid Definition
A matroid is a set E, often called the ground set, with a corresponding collection of independent subsets of E, denoted \mathcal{I}. The independent subsets are subject to the following constraints:
(I1) \emptyset \in \mathcal{I}.
(I2) If I_1 \subseteq I_2 and I_2 \in \mathcal{I}, then I_1 \in \mathcal{I} as well. That is, any subset of an independent set is similarly independent.
(I3) If I_1, I_2 \in \mathcal{I} with |I_1| < |I_2|, then there is an e \in I_2 \setminus I_1 such that I_1 \cup \{ e \} \in \mathcal{I}.
(I1) is more of a technicality. The only difference between keeping and excluding (I1) is whether or not we consider \mathcal{I} = \emptyset to be valid. (I2) comes naturally; it would not make sense for a subset of an independent set to be dependent. (I3) is also fairly intuitive: it implies that we can add an element in I_2 \setminus I_1 while still maintaining I_1's independence.
There are many examples of matroids.
Example: Perhaps the most elementary example of a matroid is the \textit{free matroid}, in which we consider all subsets of E to be independent. We can verify the free matroid is acually a matroid; (I1) is true, as \emptyset \in \mathcal{I}; (I2) is valid, as any set is independent and thus any subset of an independent set is similarly independent; a stronger version of (I3) holds, as given I_1, I_2 \in \mathcal{I} with |I_1| < |I_2|, for all e \in I_2 \setminus I_1, I_1 \cup \{ e \} \in \mathcal{I}.
Example: Another elementary example of a matroid is the \textit{uniform matroid}, denoted U_n^k, which is described by the ground set |E| = n and \mathcal{I} = \{ I \subseteq E: |I| \le k \}. We can verify that the uniform matroid is indeed a matroid; (I1) is valid, since k \le n; (I2) is valid since a subset cannot have greater cardinality than the original set; a stronger version of (I3) holds, since given I_1, I_2 \in \mathcal{I} with |I_1| < |I_2|, for all e \in I_2 \setminus I_1, I_1 \cup \{ e \} \in \mathcal{I}.
Notice that free matroid is a special case of the uniform matroid in which k = 0.
Example: A very important exmaple of a matroid, called a \textit{graphic matroid}, is derived from a graph G and denoted M(G). The ground set E is the set of edges in G and the set \mathcal{I} is the set of acyclic subgraphs (or alternatively, forests) of G. Unlike the previous examples, it is not immediately clear why M(G) is a matroid. It is not hard to see that (I1) and (I2) hold, but proving (I3) takes some more care. Assume, by sake of contradiction, that (I3) does not hold for some I_1, I_2 \in \mathcal{I} with |I_1| < |I_2|. We can assume I_1 and I_2 to be disjoint. If that is not the case, then consider I_1 \setminus I_2 and I_2 \setminus I_1 instead. Notice that if there is a node u in I_2 but not in I_1, then there is clearly such an edge e \in I_2 \setminus I_1: just consider the edge e that contains u. Thus, we are free to assume that all nodes in I_2 are also in I_1. That is, |V_2| < |V_1|, where V_1 is the set of vertices in I_1 and V_2 the set of vertices in I_2. Notice that since I_1, I_2 both constitute spanning forests, |V_1| = |I_1| + C_1 and |V_2| = |I_2| + C_2, where C_1, C_2 are the number of connected components in I_1 and I_2 respectively. Since |V_2| < |V_1|, we have:
\begin{equation}
|I_2| + C_2 < |I_1| + C_1 \Longrightarrow C_1 > C_2.
\end{equation}
That is, I_1 has more connected components than I_2. Naturally, since I_1 has more connected components, there is an edge in only I_2 that connects two of the connected components of I_1. Such an edge is guaranteed not to form a cycle. And thus, as desired (I3) holds, so M(G) is a matroid.
Example: Another common example of a matroid is formed when considering a vector space V. Let E be the set of vectors in V and \mathcal{I} the collection of linearly independent sets of vectors. It is not hard to see that (I1) and (I2) both hold. Assume, by sake of contradiction, that (I3) does not hold. In other words, given some I_1, I_2 \in \mathcal{I} with |I_1| < |I_2|, for all e \in I_2 \setminus I_1, I_1 \cup \{ e \} \notin \mathcal{I}. This implies that I_2 \setminus I_1 \subseteq \text{span} (I1) \Longrightarrow I_2 \in \text{span} (I_1) \Longrightarrow \text{span} (I_2) \subseteq \text{span} (I_1). However, this means that |I_2 | \le |I_1|, a contradiction. Thus, we have reached a contradiction, and, as desired, (I3).
There are many operations one can do on a matroid. For example,
Definition: If M_1 = (E_1, \mathcal{I}_1) and M_2 = (E_2, \mathcal{I}_2) with E_1 \cap E_2 = \emptyset, then we define the \textit{direct sum} M_1 \oplus M_2 = \left( E_1 \cup E_2, I_1 \cup I_2: I_1 \in \mathcal{I}_1 , I_2 \in \mathcal{I}_2 \right).
Lemma: The direct sum of M_1 = (E_1, \mathcal{I}_1) and M_2 = (E_2, \mathcal{I}_2) always forms a matroid.
Proof: Showing that (I1) and (I2) hold is not hard, so we devote our attention to showing that (I3) holds as well. Suppose that we chose an arbitrary independent set I = I_1 \cup I_2, where I_1 \in \mathcal{I}_1 and I_2 \in \mathcal{I}_2. We chose another independent set I' = I_1' \cup I_2', where I_1' \in \mathcal{I}_1, I_2' \in \mathcal{I}_2, and |I'| < |I|. By the independence axioms on M_1 and M_2, we know that (I_1 \setminus I_1') \cup (I_2 \setminus I_2') \ne \emptyset. Therefore, we can chose an e \in (I_1 \setminus I_1') \cup (I_2 \setminus I_2') = (I_1 \cup I_2) \setminus (I_1' \cup I_2'), from which the desired follows.
Bases
We may be curious about the maximal independent set of a matroid i.e. an independent set with strictly dependent supersets. Such a set is called a \textit{basis}.
Definition: An element I \in \mathcal{I} is a basis if for all I \subset I', I' is dependent.
To take some examples, the basis of the free matroid is the ground set, the bases of U_{n, k} are the subsets of E of cardinality k, the bases of G are the spanning trees, and the bases of a vector space V are the collection of linearly independent vectors which span V.
One may notice that all bases seem to be of the same cardinality, at least, in all of our examples, they are. This leads us to the following:
Proposition: If B_1, B_2 are bases of some matroid M, then |B_1| = |B_2|.
Proof: Assume by sake of contradiction and without loss of generality (WLOG) that |B_1| < |B_2|. Then, by (I3), there is an element e \in B_2 \setminus B_1 such that B_1 \cup \{ e \} \in \mathcal{I}. However, this contradicts the assumption that B_1 is a maximal independent set. And thus, we reach a contradiction and the desired holds true.
Lemma: The set of bases \mathcal{B} satisfies the following:
(B1) \mathcal{B} is not empty.
(B2) If B_1, B_2 \in \mathcal{B} with some arbitrary x \in B_1 \setminus B_2, then there exists a y \in \setminus B_1 such that (B_1 \setminus \{ x \} ) \cup \{ y \} \in \mathcal{B}.
Proof: Clearly, (B1) holds, since we are talking about finite matroids, so let us devote our attention to (B2). Suppose that we have chosen an x \in B_1 \setminus B_2. Consider B_1 \setminus \{ x \}, which is independent, and B_2, which is also independent. By (I3), we know that there exists a y \in B_2 \setminus (B_1 \setminus \{ x \} ) = B_2 \setminus B_1 such that (B_1 \setminus \{ x \}) \cup \{ y \} \in \mathcal{I}. Thus, as desired, (B2) holds.
Arguably more interesting is that (B1) and (B2) \enquote{define} the set of bases. That is,
Lemma: Suppose we have a ground set E and an arbitrary set \mathcal{B} obeying (B1) and (B2). Denote the collection of subsets of \mathcal{B} as \mathcal{I}. Then, (E, \mathcal{I}) forms a matroid with \mathcal{B} the set of bases.
Proof: We first show that (E, \mathcal{I}) is indeed a matroid by verifying that (I1), (I2), and (I3) all hold. Indeed, by (B1), (I1) holds and naturally, by our construction, (I2) holds too. Thus, we devote our attention to showing that (I3) holds. Suppose, by sake of contradiction, that (I3) does not hold for some sets I_1, I_2 with |I_1| < |I_2|. We know that I_1 and I_2 can both be extended to some, possibly many, bases B_1, B_2. Leveraging the fact that we have multiple options for B_1, B_2, we can chose the B_1, B_2 that minimizes |B_2 \setminus (I_2 \cup B_1).| Notice that (I_2 \cap B_1) \setminus I_1 = \emptyset. If it were not empty, then we could chose an x \in (I_2 \cap B_1) \setminus I_1 such that I_1 \cup \{ x \} \in \mathcal{I}. Therefore, we have that:
\begin{equation}\label{e1}
I_2 \setminus I_1 = B_1 \setminus I_2.
\end{equation}
Now, naturally, since |B_2 \setminus (I_2 \cup B_1)| is minimized, we may wonder if we can always achieve a cardinality of 0. Indeed, it is possible. Suppose that B_2 \setminus (I_2 \cup B_1) \ne \emptyset. Then, chose an arbitrary x \in B_2 \setminus (I_2 \cup B_1); we know by (B2) that we can always find a y \in B_1 \setminus B_2 such that (B_2 \setminus \{ x \}) \cup \{ y \} \in \mathcal{B}. However, in such a case
|((B_2 \setminus \{ x \}) \cup \{ y \} ) \setminus (I_2 \cup B_1)| < |B_2 \setminus (I_2 \cup B_1)|,
which is a contradiction. Thus, we conclude that B_2 \setminus (I_2 \cup B_1) = \emptyset or alternatively, that:
\begin{equation}
B_2 \setminus B_1 = I_2 \setminus I_1.
\end{equation}
We may wonder if, by symmetry, B_1 \setminus (I_1 \cup B_2) is similarly empty. It turns out it is. Suppose, by sake of contradiction, that we can chose an x \in B_1 \setminus (I_1 \cup B_2). Then, there must be a y \in B_2 \setminus B_1 = I_2 \setminus I_1 such that (B_1 \setminus \{ x \} ) \cup \{ y \} \in \mathcal{B}. For such a y, we know that I_1 \cup \{ y \} \in \mathcal{I}. However, this contradicts the assumption that (I3) fails. And thus, indeed B_1 \setminus (I_1 \cup B_2) = \emptyset. As a consequence, we know that:
\begin{equation}
B_1 \setminus B_2 \subseteq I_1 \setminus I_2.
\end{equation}
Notice that:
\begin{equation}
|B_2 \setminus B_1| = |B_1 \setminus B_2| = |I_2 \setminus I_1| \le |I_1 \setminus I_2|
\end{equation}
Since |I_2 \setminus I_1| < |I_1 \setminus I_2|, we know that |I_2| \le |I_1|, but this contradicts the assumption that |I_1 | < |I_2|. Therefore, our original assumption that (E, \mathcal{I}) does not satisfy (I3) is fallacious. Indeed, (E, \mathcal{I}) forms a matroid. It is not hard to verify that the corresponding set of bases is \mathcal{B}.
There is a very simple greeedy algorithm to find the basis of a matroid with maximal weight. Before we introduce this algorithm, we establish Kruskal’s algorithm.
Kruskal’s algorithm finds the maximal weight spanning forest as follows:
- Initialize a set S = \emptyset. At the end of the algorithm, S will describe the maximal weight spanning forest.
- Iterate over elements in our edges in decreasing order of weights and add e \in E to S if S \cup \{ e \} is acyclic.
We can generalize this into the language of matroids as follows:
- Initialize a set S = \emptyset. At the end of the algorithm, S will describe the basis of maximal weight.
- Iterate over elements in E = \{ e_1, e_2, \dots , e_n \} in decreasing order of weights and add e \in E to S if S \cup \{ e \} \in \mathcal{I}.
Lemma: The aforementioned algorithm always produces a basis of maximal weight.
Proof: Let the set S at the $i$th iteration be S_i. We claim that S_i can always be extended to a basis of maximal weight B_i, and we will show so via induction. The base case, when i = 0, is obvious: \emptyset can be extended to an optimal basis. Now, suppose our current set is S_i, and we are considering appending e_{i + 1} to S_i to form S_{i + 1}. If S_i \cup \{ e_{i + 1} \} \notin \mathcal{I}, then we can let S_{i + 1} = S_i. Similarly, if S_{i} \cup \{ e_{i + 1} \} \subseteq B_i, then we can let S_{i + 1} = S_i \cup \{ e_{i + 1} \}. Hence, we can assume that S_i \cup \{ e_{i + 1} \} \notin B_i and S_i \cup \{ e \} \in \mathcal{I}. In such a case, we can extend S_i \cup \{ e_{i + 1} \} to form some basis B' such that B_i \setminus B' = \{ e_{i + 1} \}. In other words, it can be extended to some basis B' = (B_i \cup \{ e _{i + 1} \} ) \setminus e_j for some j > i + 1. We know that:
$$w(B’) = w(B_i) + w(e_{i + 1}) - w(j) \le w(B).$$
And thus, as desired, B' is also a basis of maximal weight. It follows that our algorithm always produces a basis of maximal weight.
Corollary: Kruskal’s algorithm works.
Lemma: Suppose we have a ground set E and a set of nonempty independent subsets of E, denoted \mathcal{I}. If for all weight functions, the aforementioned algorithm produces an independent set of maximal weight, then (E, \mathcal{I}) forms a matroid.
Proof: We instead prove the contrapositive, namely that if (E, \mathcal{I}) does not form a matroid, then there exist some weight functions for which the aforementioned algorithm does not produce an independent set of maximal weight.
There are two reasons why (E, \mathcal{I}) may not form a matroid, either (I2), or (I3) fails. If (I2) fails, then there exist an I_1, I_2 such that I_1 \subseteq I_2, I_2 \in \mathcal{I}, I_1 \notin \mathcal{I}. We want to construct a weight function to ensure that our algorithm fails. Naturally, it may fail if we consider elements in I_1 before elements in I_2 \setminus I_1. And as such, we construct the following weight function:
$$w(e_i) = \begin{cases} 2 & e_i \in I_1 \ 1 & e_i \in I_2 \setminus I_1 \ 0 & e_i \notin I_2 \end{cases}.$$
Notice that in this case, our optimal basis has weight 2|I_1| + |I_2 \setminus I_1|
since we can always let our basis be some superset of I_2. However, if we were to follow the steps our algorithm, we will chose some proper subset of I_1, some subset of I_2 \setminus I_1, and some subset of I_2. This will clearly yield a suboptimal basis.
Now, suppose that (I2) holds, but (I3) does not hold. That is, for some I_1, I_2 with |I_1| < |I_2|, there does not exist an e \in I_2 \setminus I_1 with I_2 \cup \{ e \} \in \mathcal{I}. We can construct the following weight function:
$$w(e_i) = \begin{cases} 1 + \frac{1}{2|I_1|} & e_i \in I_1 \ 1 & e_i \in I_2 \setminus I_1 \ 0 & e_i \notin (I_2 \cup I_1) \end{cases}$$
Now, in accord with this weight function, we can achieve a basis of weight greater than or equal to |I_2|: just let the basis be some superset of I_2. On the other hand, our algorithm will give a basis of weight |I_1| \cdot \left( 1 + \frac{1}{2|I_1|} \right) = |I_1| + \frac{1}{2}, which is suboptimal. And thus, as desired, our algorithm fails.
Question: Suppose we have a list of tasks that need to be completed. Each task has a corresponding due date and takes one day to complete. For each task, if you complete it, you gain a reward, which varies per task and is a positive integer. In which order should you attempt the tasks so as to maximize the reward incurred?
We want to translate this into the language of matroids. Let a set of tasks be independent if they can all be completed before their deadlines. We speculate that (E, \mathcal{I}) forms a matroid. Clearly, (I1) and (I2) hold, but showing that (I3) holds is slightly more involved. Chose two independent sets X, Y with |X| < |Y|; let t_0 be the first time where more tasks in X have deadline before or at t_0 than in Y. Alternatively, if we N_t(A) be the number of tasks in A whose deadline is t or earlier, then we let t = t_0 be the first time at which N_t(X) \ge N_t(Y).
The aforementioned definition is particularly telling because if N_t(A) \le t for all t, then A is independent. Consequently, if we can find an e \in Y \setminus X such that N_t(X \cup \{ e \} ) \le t for all t, then we are done. In attempt to find such an e, chose some y \in Y \setminus X such that its deadline is t_0 + 1. Such a y is guaranteed to exist by the definition of t_0. Then,
\begin{equation}
N_t(X \cup { y } ) = N_t(X) + 1 \le N_t(Y) \le t
\end{equation}
whenever t > t_0. Whenever t \le t_0, N_t(X \cup \{ y \} ) = N_t(X). That is, for all t, N_t(X \cup \{ y \} ) \le t. And so, indeed, (E, \mathcal{I}) forms a matroid.
Now, we return to our original question at hand, we construct the following algorithm:
- Initialize a set S = \emptyset.
- Sort R, the set of rewards, in increasing order. Permute the set of deadlines accordingly.
- Iterate over all tasks in the order which they appear in R, and add a task t iff we can complete all tasks in S \cup \{ t \} before the deadline.
Works Cited:
-
Matroid Theory by James Oxley
-
Lecture Notes of Jeff Erickson
-
Lecture Notes of Federico Ardila