Matroids, briefly

August 14th, 2020 in Math

Over the summer, I casually got back into competitive programming. I was really surprised to see that Matroid Intersection is now a topic that shows up in contest problems. In Waterloo, I learned about Matroids in CO450: Combinatorial Optimization, and how problems such as maximum bipartite matching can be modeled with a matroid intersection problem. But, it’s been over 2 years since that course, so I thought I’d review. I will be stating theorems without proof, so it would be nice to look into the references for proofs of the results.

Matroids

Matroids are sets that carry some concept of independence which can be applied to its subsets.

1. In the analogue of vector spaces, the ground set is the set of vectors, and the concept of independence is linear independence: a subset of vectors is independent if no vector in the set is the linear combination of the other vectors.
2. In the analogue of graph theory, considering the set of edges, one notion of independence is if the edges form a forest: a subset of edges is independent if the edges do not form a cycle.

We call the universe of the matroid the be ground set, and we call the subsets of the ground set which are independent to be independent sets. The ground set is denoted with \(\mathcal{E}\) and the independent sets are denoted by the family of subsets, \(\mathcal{I}\), ie. \(\mathcal{I} \subseteq \mathcal{P}(\mathcal{E})\).

Note that in the two examples above, both concepts of independence share common traits:

• If you have a independent set, all of its subsets are independent.
• All maximum independent sets are the same size.

These two properties, give us the bulk of our generalized characterization for a matroid.

Formally, a matroid is a pair \(\mathcal{M} = (\mathcal{E}, \mathcal{I})\), where \(\mathcal{I} \subseteq \mathcal{P}(\mathcal{E})\), such the following 3 properties are satisfied ¹:

1. (M0) \(\emptyset \in \mathcal{I}\).
2. (M1) If \(I \in \mathcal{I}\) and \(J \subseteq I\), then \(J \in \mathcal{I}\).
3. (M2) For any \(X \subseteq \mathcal{E}\), the all maximal independent sets in \(X\) are the same size.

Using familiar notation from vector spaces:

1. For any \(X \subseteq \mathcal{E}\), any maximal independent set of \(X\) is a basis.
2. The rank of \(X\), \(r(X)\), is the cardinality of its basis. \(r: \mathcal{P}(\mathcal{E}) \to \mathbb{N}\) is the rank function.
3. We say rank of the matroid $M$ to be \(r(E)\).
4. Minimal dependent sets are called circuits. This comes from the forest example: all circuits in the Graphic Matroid are cycles. Note that there is no guarantee that all circuits are the same cardinality.
5. The elements of \(E\) are called edges. This also comes from the forest example.

Some examples of Matroids:

1. The Vector Matroid, the first example above.
2. The Graphic Matroid, the second example above.
3. The Uniform Matroid, \(U_{k, n} = \left(\{1, 2, \dots, n\}, \text{All subsets of size up to } k \right)\). This is a super simple matroid where all 3 properties are easy to verify.
4. The Partition Matroid, where \(\mathcal(E)\) is partitioned into \(E_1, E_2, \dots, E_r\), and \(I \subseteq \mathcal{E}\) is independent it has at most 1 edge in each \(E_i\).

Another really important property is that the rank function is submodular:

• For all \(X, Y \subseteq E\), \(r(X) + r(Y) \geq r(X \cup Y) + r(X \cap Y)\)
• In fact, if \(r: \mathcal{P}(\mathcal{E}) \to \mathbb{N}\) is submodular and \(r(X) \leq r(Y)\) if \(X \subseteq Y\) and \(r(X) \leq \|X\|\), then \(r\) must be the rank function.

Another important property is the strong basis exchange:

• For any two bases \(B_1, B_2\) of \(M\), we can find \(x \in B_1 \setminus B_2, y \in B_2 \setminus B_1\) such that \(B_1 - x + y\) and \(B_2 - y + x\) are bases as well.

Greedy Algorithms characterize Matroids

Let’s assign a weight to each \(e \in \mathcal{E}\), ie. \(w: \mathcal{E} \to \mathbb{R}\). Can we find the maximal weight basis? You might intuitively consider a greedy algorithm, which begins with an empty set, and repeatedly picks the largest remaining edge that makes the new set independent, until a basis is reached.

Rado-Edmonds theorem: One of the most important results in Matroid theory, which essential states that picking edges greedily will always produce a maximal weight basis.

In the example of the Graphic Matroid, the greedy algorithm is Kruskal’s algorithm, which finds the minimum weight spanning tree (or maximal forest, if the graph is disconnected).

Boruvka’s theorem: The converse is true as well! Any pair \((\mathcal{E}, \mathcal{I})\) that satisfies the non-empty and subset properties (M0), (M1), for which the greedy algorithm always produces a maximal weight basis (for any weight function) is a Matroid.

Astounding! The fact that an independence system has a rank is characteristic of the fact that a greedy algorithm is correct on its structure.

Matroid Intersection

The Matroid Intersection problem is about finding the largest independent set in two matroids \((\mathcal{E}, \mathcal{I}_1)\), \((\mathcal{E}, \mathcal{I}_2\) which share the same ground set. This problem can be solved in polynomial time. Note that the intersection of two independent sets may not satisfy (M2), and thus the intersection of two matroids is not always a matroid.

We can solve the maximum bipartite matching problem as a matroid intersection problem. Given a bipartite graph \((U, V, E)\), let \(E\) be the base set. Then consider \(M_U = (E, I_U)\), where each independent set in \(I_U\) covers each node in \(U\) at most once. Similarly, consider \(M_V = (E, I_V)\), with the same property defined on \(V\). Then, it should be clear that the largest \(I \in I_U \cap I_V\) is a set of edges which never covers any node twice, thus a maximal bipartite matching. It should also be clear that \((E, I_U \cap I_V)\) is not a matroid: bipartite matchings which cannot be added to are not necessarily maximal.

Note: finding the maximum intersection of 3 matroids is NP-hard. There is a clever way to solve the Hamiltonian path problem by finding the intersection of 3 matroids.

As it turns out, there is an polynomial time algorithm to solve the matroid intersection problem, assuming a polynomial time oracle exists for both independence sets. An important result that arises in this algorithm is Edmond’s Matroid Intersection Theorem (or the Min-Max Theorem):

\[\text{max} \{ |I| : I \in \mathcal{I}_1, \mathcal{I}_2 \} = \text{min} \{ r(X) + r(\mathcal{E} \setminus X) : X \subseteq \mathcal{E} \}\]

For any matroid \(M\) and independent set \(I\), we can define the exchange graph \(D_M(I)\) to be a bipartite graph, where the nodes are \((I, \mathcal{E} \setminus I)\). An edge will exist between \(x \in I, y \in \mathcal{E} \setminus I\) if \(I\) will still be independent when exchanging \(x\) for \(y\).

Aside: can you see how the strong basis exchange property interacts with this graph?

Let’s extend this exchange graph concept to two matroids at once, by making it directed. For two matroids and some independent set \(M_1, M_2, I\), we can define the directed exchange graph \(D_{M_1, M_2}(I)\) to have directed edge \((x, y)\) if \(I + x - y \in \mathcal{I}_1\) and directed edge \((y, x)\) if \(I + x - y \in \mathcal{I}_2\).

Then, we let \(X_1 := \{ x \notin I : I + x \in \mathcal{I}_1 \}\), the elements that we can add to \(I\) and keep it in the first matroid, and \(X_2 := \{ x \notin I : I + x \in \mathcal{I}_2 \}\), the elements we can add to \(I\) and keep it in the second matroid.

We try to find an augmenting path from any node in \(X_1\) to any node in \(X_2\). If no node exists, we stop, and claim that our current \(I\) is the maximum intersection possible. Otherwise, we let \(P\) be all the nodes on the augmenting path, and let \(I := I \bigtriangleup P\) (this basically means to remove elements of \(P\) already in \(I\), and to add new elements of \(P\) into \(I\)). Note that, since \(X_1\) and \(X_2\) are both in \(\mathcal{E} \setminus I\), the augmenting path starts and ends in \(\mathcal{E} \setminus I\), meaning there is 1 more edge so the cardinality of \(I\) increases by 1. The MIT link does a good job of explaining this.²

In summary. the algorithm will do the following:

I = empty set
while (true):
	Repeatedly add elements to I such that I is in I_1 and I_2.
	Create exchange graph D_M1_M2(I).
	X1 = All elements not in I such that I + x is still in I_1.
	X2 = All elements not in I such that I + x is still in I_2.
	Try to find augmenting path from X1 to X2 in D_M1_M2(I).
	If found:
		Augment I with P, nodes in the new path.
	Else:
		return I

Voila! In practice, verifying if \(I\) is independent or not can have various degrees of complexity, but is generally polynomial. The codeforces link does a great job of looking at various time complexities for different matroid cases, and possible improvements. ³

Matroids in Competitive Programming

I am not sure how many contest problems exist that need to be solved with Matroid Intersection, but I bet that a lot of problems can be cheesed with matroid intersection.

Here are some problems that can be solved with matroid intersection.

1. Pick Your Own Nim (Yandex Cup 2019)
2. Demonstration of Honesty!

I got these off of Codeforces comments, so maybe a more informed person can provide more examples.

Further Topics in Matroid Theory

I won’t talk about them, mostly because I don’t remember them well enough. Maybe I will revisit them in the future.

1. Matroid Duals
2. Maximum Weight Matroid Intersection as Linear Programming

References

1. CO 450 (Bill Cook, 2014) ⤴

2. MIT 18.438 Notes (Goemans, Steinhardt, 2009) ⤴

3. Codeforces: Matroid Intersection in Simple Words, by ATSTNG ⤴

#Combinatorics   #Matroids