Matroid Intersection

Given two matroids $M_1, M_2$ over common ground set $E$, the matroid intersection algorithm finds a set $X \subseteq E$ of maximum size such that $X \in \mathcal{I}(M_1) \cap \mathcal{I}(M_2)$. The algorithm works by starting with the set $S = \emptyset$, and repeatedly augmenting $S$ using the corresponding exchange graph $\mathcal{G}_{M_1, M_2}(S)$. The vertices of $\mathcal{G}_{M_1, M_2}(S)$ are the elements of $E$, and for $y \in S$ and $x \in E \setminus S$:

1. There is a directed edge $(y, x)$ if $S - y + x \in \mathcal{I}(M_1)$.
2. There is a directed edge $(x, y)$ if $S - y + x \in \mathcal{I}(M_2)$.

Note that $\mathcal{G}_{M_1, M_2}(S)$ is bipartite. We also label certain vertices $x \in E \setminus S$:

1. $x$ is a source if $S + x \in \mathcal{I}(M_1)$.
2. $x$ is a sink if $S + x \in \mathcal{I}(M_2)$.

To augment $S$, the algorithm finds the shortest path $x_0, y_1, x_1, \dots, y_n, x_n$ from a source to a sink. Then, it redefines $S$ to

There are two facts that together explain the correctness of this algorithm:

1. Augmenting by the shortest source-sink path preserves $S$'s independence in both matroids.
2. If there are no augmenting paths, then $S$ has maximum size among all $X \subseteq E$ such that $X$ is independent in both matroids.

Example - SERVERS

Explanation

Let $E$ be the set of all provided edges. The problem asks us to find the size of a largest subset $S \subseteq E$ where:

1. $S$ is acyclic.
2. For each frequency $f$, there are at most $c(f)$ edges in $S$ with frequency $f$.

We can directly apply matroid intersection. Let $E$ be the ground set. Then, condition 1 is asking for $S$ to be independent in the graphic matroid, and condition 2 is asking for $S$ to be independent in the partition matroid where the categories are frequencies and $c(f)$ is the capacity of category $f$.

Implementing the Matroid Intersection Algorithm

We'll implement the algorithm with a general interface so that it can be used for any matroids $M_1, M_2$ we want. Then, in the next section, we'll give the specific operations needed for our matroids.

Let $N=|E|$ be the size of the ground set and $R$ be the size of a maximum common independent set. Then, our algorithm does $R$ iterations of the following:

1. Construct the exchange graph between $S$ and $E \setminus S$.
2. Update $S$ using a shortest augmenting path from a source to a sink.

Step 2 can be done in $\mathcal O(RN)$ time using BFS. The hard part is step 1, where we need to maintain a matroid structure that allows us to efficiently check when a set is independent.

It turns out that supporting the following operations (for both matroids) is enough:

• clear(): set $S := \emptyset$.
• check(x): return true if $S + x$ is independent and false otherwise.
• add(x): set $S := S + x$, assuming $S + x$ is independent.
• precomp(): (optional) precomputation to speed up a batch of check(x) queries.

Recall that we need to know for each $y \in S$ and $x \in E \setminus S$ if $S - y + x \in \mathcal I(M_1)$ and $S - y + x \in \mathcal I(M_2)$. The trick is to batch queries by $y$. For a fixed $y$, we use clear() and add(x) to obtain $S - y$, then use check(x) to find all $x$ where $S - y + x$ is independent. Before making the check(x) calls, we also make a call to precomp() to potentially speed up the batch of $\mathcal O(N)$ check(x) calls. In case precomputation is unnecessary, precomp() can be defined as an empty function.

This builds the graph with $\mathcal O(R)$ calls to clear() and precomp(), $\mathcal O(R^2)$ calls to add(x), and $\mathcal O(RN)$ calls to add(x). Observe that we sidestepped the need to efficiently remove arbitrary elements from $S$, which would have been a big problem for matroids like the graphic matroid.

Also see KACTL's implementation, which only checks edges as needed rather than building the entire graph upfront.

Time Complexity: $\mathcal O(R^2)$ calls to clear() and precomp(), $\mathcal O(R^3)$ to add(x), and $\mathcal O(R^2N)$ calls to check(x). Note that in our implementation, the complexity is always dominated by these oracle calls. In KACTL's implementation, backE loops over all $N$ elements instead of just those in $S$, which adds an extra $O(RN^2)$ (though the number of oracle calls stays the same).

Copy
template <class M1, class M2> vector<bool> MatroidIsect(M1 m1, M2 m2, int n) {
	vector<bool> in_S(n);
	auto augment = [&] {
		vector<int> S, E_S;  // E_S has indices of all edges not in S
		for (int i = 0; i < n; i++) {
			if (in_S[i]) S.push_back(i);
			else E_S.push_back(i);
		}
		// build exchange graph
		vector<vector<int>> adj(n);

Implementing the Matroid Structure

We implement the graphic matroid with union-find and the partition matroid by maintaining a count of the number of used elements of each frequency.

In our case, the maximum size of a common independent set is $n-1$ and the size of the ground set is $m$. We get an extra $\mathcal O(\alpha(n))$ factor from union-find, but this is still well within the time limit.

Time complexity: $\mathcal O(n^2m \cdot \alpha(n))$

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: Union-find Data Structure (Click to expand)

struct GraphicMatroid {
	int n;  // nodes of the graph must be in [0..n-1]
	DSU dsu;
	vector<pair<int, int>> edges;
	GraphicMatroid(int n, const vector<pair<int, int>> &edges)

Modifying Existing Matroids

We now consider some ways of making new matroids from existing ones. This expands the kinds of conditions we can handle.

Matroid Dual

In many problems, it is useful to consider the dual of some well-known matroid. The dual $M^\star$ of a matroid $M$ is defined on the same ground set $E(M)$ with the independent sets defined as follows:

As an example, consider the graphic matroid $M$ corresponding to a connected graph $G = (V, E)$. Then, the bases of $M$ are spanning trees, and a set of edges $X \subseteq E$ is independent in $M^\star$ if and only if $G$ remains connected after removing all of the edges in $X$.

Claim: The dual $M^\star$ of a matroid $M$ is itself a matroid.

Proof: Clearly, the non-emptiness and heredity axioms hold, so it remains to show that the exchange axiom also holds. Let $X, Y \in I(M^\star)$ such that $|X| < |Y|$. For convenience, we will reframe the exchange axiom in terms of $X^c = E \setminus X$ and $Y^c = E \setminus Y$. Our goal is to show that there exists $e \in X^c$ such that $e \notin Y^c$ and $X^c - e$ contains a basis of $M$.

Partition $X^c$ into $\mathcal{C}$ and $\mathcal{A}$ where

and $\mathcal{A} = X^c \setminus \mathcal{C}$. If there exists $e \in \mathcal{C}$ such that $e \notin Y^c$, then we are immediately done. Suppose that $\mathcal{C} \subseteq Y^c$. It follows that

so we get

Furthermore, it can be shown that

by taking any maximum independent set $S \subseteq \mathcal{C}$ and noting that $S \cup \mathcal{A}$ is independent by choice of $\mathcal{A}$. Therefore, $r(X^c) \neq r(Y^c)$, which is a contradiction because $X^c$ and $Y^c$ both contain bases of $M$.

Contraction of a Matroid

Suppose we have an existing matroid $M=\langle E, \mathcal I\rangle$, but there are some elements $A \subseteq E$ we are forced to include. If $A \in \mathcal I$, we can effectively mod out by $A$ with matroid contraction: the contraction of $M$ by $A$, written $M / A$, is the matroid on the ground set $E \setminus A$ where $B$ is independent in $M / A$ if $A \cup B \in \mathcal I$.

Problems

Additional Problems

• Honesty

  • Max Size Graphic + Colorful
• Ambiguous Forest

  • Max Size Graphic + Graphic
• Rainbow Graph

  • Min Weight Graphic + Colorful
  • NAIPC 2018 Sols
  • Arup Guha Sol
• TST

  • Partition into 3 MST's
• Almost Rainbow Tree (Easy)

  • Can be solved exactly using Matroid Intersection, or via a $1/2$-approximation using greedy.
• Almost Rainbow Tree (Hard):

  • Can be solved exactly using Matroid Intersection, or via a $2/3$-approximation using local search.