Matroid Intersection Algorithm

Definition

Matroid Intersection Algorithm

Given two finite matroids ${\mathcal{M}}_1=(E,{\mathcal{I}}_1)$ and ${\mathcal{M}}_2=(E,{\mathcal{I}}_2)$ on the same ground set, the matroid intersection algorithm finds a largest set independent in both:

$$S^{\ast }\in \underset{S\in {\mathcal{I}}_1\cap {\mathcal{I}}_2}{\mathrm{argmax}}|S|.$$

Starting with $S=\varnothing$, it repeatedly finds a shortest augmenting path in a directed exchange graph and exchanges the elements along that path. Each augmentation preserves common independence and increases $|S|$ by one. If no augmenting path exists, $S$ has maximum cardinality.

The intersection need not itself be a matroid. This algorithm uses independence tests in ${\mathcal{M}}_1$ and ${\mathcal{M}}_2$ separately.

Build the exchange graph

Fix the current common independent set $S\in {\mathcal{I}}_1\cap {\mathcal{I}}_2$. The directed bipartite graph $H(S)$ has vertex classes $S$ and $E\setminus S$: selected elements on one side, unselected elements on the other.

Arcs represent permitted single exchanges

For each $a\in S$ and $b\in E\setminus S$, test the set obtained by removing $a$ and adding $b$:

$$\begin{array}{rl}a⟶b\text{ in }H(S)& ⟺(S\setminus \{a\})\cup \{b\}\in {\mathcal{I}}_1,\\ b⟶a\text{ in }H(S)& ⟺(S\setminus \{a\})\cup \{b\}\in {\mathcal{I}}_2.\end{array}$$

The diagram shows a pair for which both tests succeed. In general, either arc, both arcs, or neither arc may be present. An arc records an exchange test; its direction does not mean that its starting vertex is always removed.

Mark possible entry and exit elements

Among the unselected elements, mark those that can already be added without removing anything:

$$\begin{array}{rl}{E}_1& =\{b\in E\setminus S:S\cup \{b\}\in {\mathcal{I}}_1\},\\ E_2& =\{b\in E\setminus S:S\cup \{b\}\in {\mathcal{I}}_2\}.\end{array}$$

An augmenting path starts in $E_1$ and ends in $E_2$. Both endpoints lie outside $S$; the sets $E_1$ and $E_2$ may overlap.

Find a shortest augmenting path

Run a multi-source breadth-first search in $H(S)$, starting from every vertex in $E_1$. Stop when a vertex in $E_2$ is reached. Shortest means the fewest arcs, over all choices of starting and ending vertices.

A path alternates between unselected and selected elements

If a path exists, take a shortest one:

$$P=(b_0,a_1,b_1,\dots ,a_t,b_t),b_0\in E_1,b_t\in E_2.$$

Shown for $t=2$: only the path vertices and path arcs are drawn, not the whole graph $H(S)$. Each arc colour identifies the matroid whose exchange test succeeded.

A shortest path has no internal unselected vertex in $E_1$ or $E_2$: such a vertex would allow a later start or an earlier finish. Thus

$$a_1,\dots ,a_t\in S,b_1,\dots ,b_{t-1}\in E\setminus (S\cup E_1\cup E_2).$$

Exchange along the path

Toggle membership simultaneously

Remove the selected path vertices and add the unselected path vertices:

$$S^{\prime }=(S\setminus \{a_1,\dots ,a_t\})\cup \{b_0,b_1,\dots ,b_t\}.$$

Here $1$ means selected and $0$ means unselected. The elements $u,v$ illustrate elements of $S$ outside the path; all elements outside $P$ retain their membership.

In general, the path removes $t$ elements and adds $t+1$:

$$|S^{\prime }|=|S|-\underset{\text{removed}}{\underbrace{t}}+\underset{\text{added}}{\underbrace{(t+1)}}=|S|+1.$$

For a shortest augmenting path, $S^{\prime }\in {\mathcal{I}}_1\cap {\mathcal{I}}_2$. This guarantee concerns the simultaneous update, not a sequence of individually feasible intermediate sets. The correctness proof is omitted here.

Direct addition

If $b_0\in E_1\cap E_2$, the shortest path consists of the single vertex $b_0$ and has zero arcs. Then $t=0$ and $S^{\prime }=S\cup \{b_0\}$: no removal is needed.

Stop or repeat

If breadth-first search reaches no vertex of $E_2$, there is no augmenting path and the current set $S$ has maximum cardinality. Otherwise replace $S$ by $S^{\prime }$ and rebuild the graph and endpoint sets for the new $S$.

MatroidIntersection(M₁, M₂):
    S := ∅
    loop:
        Build H(S), E₁, E₂ using independence tests
        P := a shortest directed path from E₁ to E₂
             (multi-source BFS; allow a zero-arc path)
        if no such P exists:
            return S
        S := (S \ V(P)) ∪ (V(P) \ S)

Here $V(P)$ is the set of path vertices, and the update uses the old value of $S$ on both sides. Each successful iteration increases $|S|$ by one, so there are at most $|E|$ augmentations.

Independence tests and running time

With $n=|E|$ and $k=|S|$, one iteration uses at most

$$\underset{\text{exchange tests}}{\underbrace{2k(n-k)}}+\underset{\text{endpoint tests}}{\underbrace{2(n-k)}}=O(n^2)$$

independence tests. The graph has $n$ vertices and at most $2k(n-k)$ arcs, so breadth-first search takes $O(n^2)$ time. Rebuilding everything each iteration gives $O(n^3)$ independence tests overall, or $O(n^3(T_{\mathrm{ind}}+1))$ time if each independence test costs at most $T_{\mathrm{ind}}$.