Skip to main content

Math 428/529: Discrete Optimization

Jonathan A. Noel

Section 8.3 Matroid Intersection

In Section 8.1, we saw how, for non-negative weight functions, the maximum weight of an independent set in a matroid can be found via a standard greedy algorithm. So, for example, by considering graphic matroids, the minimum weight spanning tree problem in graphs can be transformed into a maximum weight independent set problem in a matroid, which can be solved by a greedy algorithm (which, in the context of minimum weight spanning trees, is known as Kruskal’s Algorithm).
Of course, it is somewhat rare that a problem can be phrased in terms of a matroid. As we will see in this section, the maximum weight independent set in the intersection of two matroids can also be found in polynomial time. Moreover, there are natural optimization problems that cannot be phrased in terms of a matroid, but can be phrased in terms of the intersection of two matroids. For example, matching problems in bipartite graphs is an example.

Example 8.3.1. Matchings and Matroids.

Let \(G\) be a bipartite graph with bipartition \((A,B)\text{.}\) For each vertex \(v\in V(G)\text{,}\) let \(E_v\) be the set of edges incident with \(V\text{.}\) Let \(M_A = (E(G),\mathcal{I}_A)\) and \(M_B = (E(G),\mathcal{I}_A)\) be the partition matroids corresponding to the sets \(\{E_v: v\in A\}\) and \(\{E_v: v\in B\}\) respectively. Then \(Y\in\mathcal{I}_A\cap \mathcal{I}_B\) if and only if no two edges in \(Y\) contain a common vertex; i.e. \(Y\) is a matching. However, it is not hard to see that the set of all matchings in a bipartite graph is not necessarily a matroid; in particular, the third property in Definition 8.1.1 may be violated.
In the exercises at the end of this chapter, there are many additional interesting problems that can be expressed in terms of the intersection of two matroids. The following theorem provides a beautiful duality statement for the maximum cardinality of a common independent set of two matroids.
In Section 8.4, we will also show that it is possible to find the maximum weight common independent set of two matroids in polynomial time.
Like so many of the other of the statements that we have seen in this course, Theorem 8.3.2 can be seen through the lense of duality. That is, the “dual” of the problem of finding the maximum cardinality of a common independent set of two matroids is the problem of partitioning the ground set \(X\) into two sets in a way that minimizes the \(M_1\)-rank of the first set and the \(M_2\)-rank of the second. Note that the weak duality statement (i.e. if we replace the \(=\) with a \(\leq\)) is easy to see. That is, if \(Y\in\mathcal{I}_1\cap \mathcal{I}_2\text{,}\) then \(Y\cap A\) must be independent in \(M_1\) and \(Y\cap B\) must be independent in \(\mathcal{I}_2\text{,}\) and so
\begin{equation*} |Y|=|Y\cap A|+|Y\cap B| \leq r_{M_1}(A)+r_{M_2}(B). \end{equation*}
Thus, the \(\leq\) direction holds. The interesting part is proving the \(\geq\) direction.
Let us now describe the algorithm alluded to in Theorem 8.3.2, after which we will work on proving that it is correct and that it implies the statement in the theorem. Starting with \(Y=\emptyset\text{,}\) which is independent in both matroids, the algorithm repeatedly attempts to replace \(Y\) with a common independent set in the two matroids of cardinality one larger than before (i.e. to augment it). So, it suffices to describe the algorithm for augmenting a common independent set.
For a common independent set \(Y\) of \(M_1\) and \(M_2\text{,}\) define \(H(M_1,M_2,Y)\) to be the digraph with vertex set \(X\) where \(uv\) is an arc if either
  • \(u\in Y\text{,}\) \(v\in X\setminus Y\) and \((Y\setminus\{u\})\cup\{v\}\in\mathcal{I}_1\) or
  • \(u\in X\setminus Y\text{,}\) \(v\in Y\) and \((Y\setminus\{v\})\cup\{u\}\in\mathcal{I}_2\text{.}\)
Note that the underlying graph of \(H(M_1,M_2,Y)\) is bipartite with bipartition \((Y,X\setminus Y)\text{.}\) Here is the (surprisingly simple) algorithm.
It is evident that this algorithm runs in polynomial time (assuming that one can check the conditions \(S\in\mathcal{I}_1\) and \(S\in\mathcal{I}_2\) in polynomial time). The rest of this section is devoted to proving that Algorithm 8.3.3 is correct and that it implies Theorem 8.3.2. That is, that it always either outputs a common independent set or it (correctly) determines that \(Y\) is a largest such set and outputs a partition \(A\sqcup B\) as in the theorem.
Suppose first that we are in the case that a directed path from \(Z_1\) to \(Z_2\) exists in \(H(M_1,M_2,Y)\text{.}\) In this case, what we want to show is that \(Y'\in\mathcal{I}_1\cap\mathcal{I}_2\text{.}\) First, let us prove the following.

Proof.

For \(0\leq i\leq m\text{,}\) define
\begin{equation*} Y_i:=\{y_1,\dots,y_{m-i}\}\cup\{z_{m+1-i},\dots,z_m\}\cup\{y_{m+1},\dots,y_n\}. \end{equation*}
We prove that \(Y_i\in\mathcal{I}_1\) for each \(i\) by induction on \(i\text{.}\) Note that this suffices to prove the lemma because \(Y_m=Y'\setminus\{z_0\}\text{.}\) In the case \(i=0\text{,}\) we have \(Y_0=Y\) and so it is true by our assumption that \(Y\in\mathcal{I}_1\cap\mathcal{I}_2\text{.}\)
Suppose \(i\geq 1\text{.}\) Then
\begin{equation*} W_1:=\{y_1,\dots,y_{m-i}\}\cup\{z_{m+1-i}\}\cup\{y_{m+2-i},\dots,y_m\}\cup\{y_{m+1},\dots,y_n\}\in \mathcal{I}_1 \end{equation*}
by the fact that the arc \(y_{m+1-i}z_{m+1-i}\) is in \(H(M_1,M_2,Y)\text{.}\) Also, \(Y_{i-1}\in \mathcal{I}_1\) by induction. Consequently,
\begin{equation*} W_2:=Y_{i-1}\setminus\{y_{m+1-i}\} = \{y_1,\dots,y_{m-i}\}\cup\{z_{m+2-i},\dots,z_m\}\cup\{y_{m+1},\dots,y_n\}\in\mathcal{I}_1. \end{equation*}
So, \(W_1\) and \(W_2\) are independent sets with \(|W_2|< |W_1|\text{.}\) Thus, there exists an element of \(W_1\setminus W_2\) that can be added to \(W_2\) while maintaining independence. If \(W_2\cup\{z_{m+1-i}\}\) is independent, then we are done because this set is simply \(Y_i\text{.}\) The only other alternative is that there must exist \(j\) with \(m+2-i\leq j\leq m\) such that \(W_2\cup \{y_j\}\) is independent.
Now, the set \(Y\setminus\{y_{m+1-i}\}\) is independent and has cardinality less than that of \(W_2\cup\{y_j\}\text{.}\) So, there is an element of \((W_2\cup\{y_j\})\setminus(Y\setminus\{y_{m+1-i}\})\) that can be added to \(Y\setminus\{y_{m+1-i}\}\) while maintaining independence. Thus, there exists some \(m+2-i\leq k\leq m\) such that \((Y\setminus\{y_{m+1-i}\})\cup\{z_k\}\in\mathcal{I}_1\text{.}\) However, this implies that \(y_{m+1-i}z_k\) is an arc of \(H(M_1,M_2,Y)\) which contradicts the fact that \(z_0,y_1,z_1,\dots,y_m,z_m\) is a shortest path and completes the proof.
Now, let us show that the set \(Y'\) is, itself, in \(\mathcal{I}_1\text{.}\)

Proof.

By Lemma 8.3.4, we know that \(Y'\setminus\{z_0\}\in\mathcal{I}_1\text{.}\) Since \(z_0\in Z_1\text{,}\) we have that \(Y\cup\{z_0\}\in\mathcal{I}_1\text{.}\) So, there must exist an element of \(Y\cup\{z_0\}\) that is not in \(Y'\setminus\{z_0\}\) that can be added to \(Y'\setminus\{z_0\}\) while maintaining independence. If this element is \(z_0\text{,}\) then we win. We claim that this must be the case. Indeed, by our choice of a shortest path and the fact that \(Z_1\cap Y=\emptyset\) by definition, we know that \(z_0\) is the only element of \(Z_1\) in \(Y'\text{.}\) So, if we start with \(Y\) and we add each element of \((Y'\setminus\{z_0\})\setminus Y\) to \(Y\text{,}\) one by one, the \(M_1\)-rank never increases. So, \(r_{M_1}((Y\cup Y')\setminus\{z_0\})=|Y|\text{.}\) Thus, the only element of \(Y\cup\{z_0\}\) that can be added to \(Y'\setminus\{z_0\}\) and increase the rank is \(z_0\text{.}\) This completes the proof.
The previous lemma shows that \(Y'\in \mathcal{I}_1\text{.}\) A symmetric argument using \(z_m\) in the place of \(z_0\) proves that \(Y'\in \mathcal{I}_2\) as well. So, in the case that there’s a path from \(Z_1\) to \(Z_2\text{,}\) we have that \(Y'\) is a common independent set of \(M_1\) and \(M_2\) that is larger than \(Y\text{.}\)
To complete the analysis of the algorithm and proof of the theorem, we need to consider the case that no path from \(Z_1\) to \(Z_2\) exists. We prove the following.

Proof.

By definition of \(A\) and \(B\text{,}\) we have \(Z_2\subseteq A\text{,}\) \(Z_1\subseteq B\text{,}\) \(A\sqcup B=X\) and there are no arcs in \(H(M_1,M_2,Y)\) from \(B\) to \(A\text{.}\) Since \(Y\in\mathcal{I}_1\text{,}\) we have \(r_{M_1}(A)\geq |Y\cap A|\text{.}\) If equality does not hold, then there exists \(x\in A\setminus Y\) such that \((Y\cap A)\cup\{x\}\in\mathcal{I}_1\text{.}\) Let \(S\) be a maximal set such that
  • \((Y\cap A)\cup\{x\}\subseteq S\text{,}\)
  • \(S\subseteq Y\cup \{x\}\text{,}\)
  • \(S\in \mathcal{I}_1\text{.}\)
Since we know that \(Y\in\mathcal{I}_1\text{,}\) we must have \(|S|\geq |Y|\text{;}\) otherwise, we would keep adding elements of \(Y\) to \(S\) until it holds. So, either \(S=Y\cup\{x\}\) or \(S=(Y\setminus\{y\})\cup\{x\}\) for some \(y\in Y\setminus A\text{.}\)
In the first case, we have that \(Y\cup\{x\}\in\mathcal{I}_1\) which implies that \(x\in Z_1\text{.}\) However, since \(x\in A\text{,}\) this contradicts the fact that \(Z_1\subseteq B\) and \(A\cap B=\emptyset\text{.}\) In the second case, we have that \(yx\) is an arc of \(H(M_1,M_2,Y)\text{.}\) However, since \(y\in Y\setminus A\subseteq B\text{,}\) this is again a contradiction. Therefore, \(r_{M_1}(A)=|A\cap Y|\text{.}\) The proof that \(r_{M_1}(B)=|B\cap Y|\) is symmetric.
Now, for any \(Z\in \mathcal{I}_1\cap\mathcal{I}_2\text{,}\) we have
\begin{equation*} |Z|= |Z\cap A|+|Z\cap B| \leq r_{M_1}(Z\cap A)+r_{M_2}(Z\cap B)=|Y\cap A|+|Y\cap B|=|Y| \end{equation*}
which completes the proof.
Here are two YouTube videos related to this section:
PrevTopNext