xii. Matroid Intersection

Largest (or heaviest) set independent in two matroids $M_1,M_2$ on the same ground set. Bipartite matching, colourful spanning trees, spanning trees with type quotas, arborescence existence and “basis with at most one vector per group” are all instances. Three matroids are NP-hard. Matroid basics and the greedy theorem: Matroids.

Each matroid is an oracle with clear(), ins(i), indep(i) (“is the current set plus $i$ independent?”). Cost: $O(r)$ augmentations, each an $O(n)$-vertex BFS needing $O(n)$ oracle rebuilds, so about $O(r{n}^2)$ indep calls for rank $r$; fine for $n\le 2000$ with cheap oracles.

Exchange graph and the algorithm

For the current common independent set $S$: edge $x\to y$ ($x\in S$, $y\notin S$) if $S-x+y\in {\mathcal{I}}_1$; edge $y\to x$ if $S-x+y\in {\mathcal{I}}_2$. Sources $X_1=\{y\notin S:S+y\in {\mathcal{I}}_1\}$, sinks $X_2=\{y\notin S:S+y\in {\mathcal{I}}_2\}$. Augment along a shortest source–sink path; stop when none exists.

struct GraphicMatroid {                                       // independent = forest
    vector<pair<int, int>> ed; vector<int> par;
    GraphicMatroid(int n, const vector<pair<int, int>>& edges) : ed(edges), par(n) {}
    int find(int x) { while (par[x] != x) x = par[x] = par[par[x]]; return x; }
    void clear() { iota(all(par), 0); }
    void ins(int i) { par[find(ed[i].first)] = find(ed[i].second); }
    bool indep(int i) { return find(ed[i].first) != find(ed[i].second); }
};
struct ColorfulMatroid {                                      // independent = at most lim[c] elements of colour c
    vector<int> col, lim, used;
    ColorfulMatroid(const vector<int>& color, const vector<int>& limit) : col(color), lim(limit), used(sz(limit)) {}
    void clear() { fill(all(used), 0); }
    void ins(int i) { used[col[i]]++; }
    bool indep(int i) { return used[col[i]] < lim[col[i]]; }
};
struct LinearMatroid {                                        // independent = linearly independent over GF(2)
    vector<ull> vec, basis;
    LinearMatroid(const vector<ull>& v) : vec(v), basis(64) {}
    ull reduce(ull x) const { for (int b = 63; b >= 0; b--) if ((x >> b & 1) && basis[b]) x ^= basis[b]; return x; }
    void clear() { fill(all(basis), 0); }
    void ins(int i) { ull x = reduce(vec[i]); if (x) basis[63 - __builtin_clzll(x)] = x; }
    bool indep(int i) { return reduce(vec[i]) != 0; }
};
template <class M1, class M2> struct MatroidIntersection {   // oracle: clear(), ins(i), indep(i) = "set + i independent?"
    int n; vector<bool> inSet; M1 m1; M2 m2;
    bool augment() {
        vector<int> pre(n + 1, -1); queue<int> q; q.push(n);  // n = virtual source, treated as "in the set"
        while (sz(q)) {
            int x = q.front(); q.pop();
            if (inSet[x]) {                                   // x -> y if S - x + y independent in M1
                m1.clear();
                for (int i = 0; i < n; i++) if (inSet[i] && i != x) m1.ins(i);
                for (int i = 0; i < n; i++) if (!inSet[i] && pre[i] == -1 && m1.indep(i)) pre[i] = x, q.push(i);
            } else {                                          // y -> x if S - x + y independent in M2
                auto backEdge = [&]() {                       // n: x can be added; -1: no more edges; else next vertex
                    m2.clear();
                    for (int c = 0; c < 2; c++) for (int i = 0; i < n; i++) if ((x == i || inSet[i]) && (pre[i] == -1) == (bool)c) {
                        if (!m2.indep(i)) { if (c) { pre[i] = x; q.push(i); return i; } return -1; }
                        m2.ins(i);
                    }
                    return n;
                };
                for (int y; (y = backEdge()) != -1;) if (y == n) { for (; x != n; x = pre[x]) inSet[x] = !inSet[x]; return true; }
            }
        }
        return false;
    }
    MatroidIntersection(int m, M1 a, M2 b) : n(m), inSet(m + 1), m1(a), m2(b) {
        inSet[n] = true; m1.clear(), m2.clear();
        for (int i = n - 1; i >= 0; i--) if (m1.indep(i) && m2.indep(i)) inSet[i] = true, m1.ins(i), m2.ins(i);   // greedy start
        while (augment()) {}
    }
    int size() const { int s = 0; for (int i = 0; i < n; i++) s += inSet[i]; return s; }
};

Usage: MatroidIntersection<GraphicMatroid, ColorfulMatroid> mi(m, GraphicMatroid(n, edges), ColorfulMatroid(color, limit)); then mi.size() and mi.inSet[i]. The backEdge trick finds the next unvisited $x$ with $S-x+y\in {\mathcal{I}}_2$ by inserting already-visited elements first, so each vertex needs $O(n)$ oracle calls instead of $O(n)$ rebuilds.

Proof: shortest augmenting paths work, and the min-max theorem

Exchange lemma. Let $I$ be independent, $x_1,\dots ,x_k\in I$ and $y_1,\dots ,y_k\notin I$ distinct, with $I-x_i+y_i$ independent for all $i$ and $I-x_i+y_j$ dependent for all $i<j$. Then $I-\{x_i\}+\{y_i\}$ is independent. Induction on $k$: put $J=I-x_1+y_1$. For $j\ge 2$, $I-x_1+y_j$ is dependent, so the unique circuit $C_j$ of $I+y_j$ avoids $x_1$ and stays inside $J+y_j$; it is therefore the unique circuit of $J+y_j$ too. Hence for $i,j\ge 2$, $J-x_i+y_j$ is independent iff $x_i\in C_j$ iff $I-x_i+y_j$ is independent: the hypotheses hold for $J$ and the pairs $\mathrm{2..}k$.

Adding a free element. If moreover $I+y_0$ is independent and every $y_i$ ($i\ge 1$) is spanned by $I$, then $I_0=I+y_0$ satisfies the same hypotheses (the circuit of $I_0+y_i$ is still $C_i$), so $I-\{x_i\}+\{y_0,\dots ,y_k\}$ is independent.

Augmentation. Let $y_0,x_1,y_1,\dots ,x_k,y_k$ be a shortest path from $X_1$ to $X_2$. For $M_1$ use the pairs $(x_i,y_i)$: each is an arc, an arc $x_i\to y_j$ with $j>i$ would shortcut the path, and $y_1,\dots ,y_k$ are not sources (a source later on the path would give a shorter path), so they are spanned by $S$; the lemma gives $S△P\in {\mathcal{I}}_1$. For $M_2$ use the pairs $(x_i,y_{i-1})$ in reverse order with the sink $y_k$ as the free element: arcs $y_a\to x_b$ with $b>a+1$ would shortcut, and $y_0,\dots ,y_{k-1}$ are not sinks. So $S△P\in {\mathcal{I}}_2$ and $|S|$ grows by one.

Optimality. If no path exists, let $U$ be the elements reachable from $X_1$; then $X_1\subseteq U$ and $X_2\cap U=\varnothing$. $r_2(U)=|S\cap U|$: otherwise some $y\in U\setminus S$ has $(S\cap U)+y\in {\mathcal{I}}_2$; $y$ is not a sink, so extending within $S+y$ gives $S-x+y\in {\mathcal{I}}_2$ for some $x\in S\setminus U$, an arc $y\to x$ that makes $x$ reachable, a contradiction. $r_1(E\setminus U)=|S\setminus U|$: otherwise some $y\notin U\cup S$ has $(S\setminus U)+y\in {\mathcal{I}}_1$; $y$ is not a source, so $S-x+y\in {\mathcal{I}}_1$ for some $x\in S\cap U$, an arc $x\to y$ making $y$ reachable, a contradiction. For any common independent $I$: $|I|=|I\cap U|+|I\setminus U|\le r_2(U)+r_1(E\setminus U)=|S|$. This proves maximality and Edmonds’ formula $\max |I|={\min }_U(r_1(E\setminus U)+r_2(U))$.

Matroid union and partition

Put each element into one of $k$ matroids (or $k$ copies of one) so that every part is independent, maximising the number placed: intersect the direct sum (element $e$ copied $k$ times, copy $i$ goes to matroid $i$) with the partition matroid “each element at most once”.

template <class M> struct DirectSumMatroid {                 // element e * k + i = element e placed in part i
    int k; vector<M> parts;
    void clear() { for (auto& p : parts) p.clear(); }
    void ins(int x) { parts[x % k].ins(x / k); }
    bool indep(int x) { return parts[x % k].indep(x / k); }
};
template <class M> vector<int> matroidPartition(int m, const vector<M>& ms) {   // part[e] in [0, k) or -1
    int k = sz(ms); if (!k) return vector<int>(m, -1);
    vector<int> color(m * k); for (int x = 0; x < m * k; x++) color[x] = x / k;
    MatroidIntersection<DirectSumMatroid<M>, ColorfulMatroid> mi(m * k, DirectSumMatroid<M>{k, ms}, ColorfulMatroid(color, vector<int>(m, 1)));
    vector<int> part(m, -1);
    for (int x = 0; x < m * k; x++) if (mi.inSet[x]) part[x / k] = x % k;
    return part;
}

• $k$ edge-disjoint spanning trees (Nash-Williams–Tutte): partition the edges into $k$ forests; all spanning iff each forest has $n-1$ edges.
• Arboricity (fewest forests covering all edges) $={\max }_H\lceil |E(H)|/(|V(H)|-1)\rceil$; find it by trying $k=1,2,\dots$ with matroid partition.
• Covering by independent sets in any matroid: $\min k={\max }_A\lceil |A|/r(A)\rceil$ (Edmonds).
• Union rank: $r_{M_1\vee M_2}(E)={\min }_A(|E\setminus A|+r_1(A)+r_2(A))$.

Proof: union via intersection, and the covering formula

A set $T$ of copies is independent in the direct sum iff each part’s elements (copies with index $i$) form an independent set of $M_i$, and it is independent in the partition matroid iff no element is used twice. So common independent sets are exactly partial partitions into independent parts, and maximising the common set maximises the number of placed elements. The union rank formula follows from the intersection min-max applied to these two matroids (a minimising $U$ can be taken as all copies of a set $E\setminus A$, giving $|E\setminus A|$ from the partition side and ${\sum }_i{r}_i(A)$ from the sum side). Covering: $E$ is covered by $k$ independent sets iff the union of $k$ copies has rank $|E|$, iff $|E\setminus A|+kr(A)\ge |E|$ for all $A$, iff $k\ge |A|/r(A)$ for all $A$; for graphic matroids, the worst $A$ can be taken as the edge set of a connected subgraph $H$ with $r(A)=|V(H)|-1$.

Weighted matroid intersection

best[k] is the maximum weight of a common independent set of size $k$, for every $k$ up to the maximum. Each step augments along a source–sink path minimising (cost, number of edges) where entering $y\notin S$ costs $-w_y$ and leaving $x\in S$ costs $+w_x$; Bellman–Ford handles the negative costs (there are no negative cycles). $O(r\cdot n^3)$ plus oracle costs.

template <class M1, class M2>
vector<ll> weightedMatroidIntersection(int n, M1 m1, M2 m2, const vector<ll>& w, vector<char>& inSet) {
    inSet.assign(n, 0); vector<ll> best = {0}; const ll INF = LLONG_MAX / 4;   // best[k]: max weight of size k
    for (;;) {
        vector<int> S; for (int i = 0; i < n; i++) if (inSet[i]) S.push_back(i);
        vector<vector<int>> g(n); vector<char> src(n), snk(n);
        m1.clear(), m2.clear(); for (int x : S) m1.ins(x), m2.ins(x);
        for (int y = 0; y < n; y++) if (!inSet[y]) src[y] = m1.indep(y), snk[y] = m2.indep(y);
        for (int x : S) {
            m1.clear(), m2.clear(); for (int z : S) if (z != x) m1.ins(z), m2.ins(z);
            for (int y = 0; y < n; y++) if (!inSet[y]) { if (m1.indep(y)) g[x].push_back(y); if (m2.indep(y)) g[y].push_back(x); }
        }
        vector<pair<ll, int>> dist(n, {INF, 0}); vector<int> prv(n, -1);   // (cost, #edges), Bellman-Ford
        for (int y = 0; y < n; y++) if (src[y]) dist[y] = {-w[y], 0};
        for (bool ch = true; ch;) {
            ch = false;
            for (int u = 0; u < n; u++) if (dist[u].first != INF) for (int v : g[u]) {
                pair<ll, int> nd = {dist[u].first + (inSet[v] ? w[v] : -w[v]), dist[u].second + 1};
                if (nd < dist[v]) dist[v] = nd, prv[v] = u, ch = true;
            }
        }
        int end = -1;
        for (int y = 0; y < n; y++) if (snk[y] && dist[y].first != INF && (end == -1 || dist[y] < dist[end])) end = y;
        if (end == -1) break;
        best.push_back(best.back() - dist[end].first);
        for (int v = end; v != -1; v = prv[v]) inSet[v] ^= 1;
    }
    return best;
}

Proof sketch: weighted augmentation

Invariant: the current $S$ of size $k$ is a maximum-weight common independent set of size $k$. By a weight-splitting argument (Frank), this holds iff there are $w=w_1+w_2$ such that $S$ is a maximum-$w_1$ basis-like set in $M_1$ and a maximum-$w_2$ one in $M_2$ among sets of its size; under such a splitting the exchange graph with costs $-w_y$ / $+w_x$ has no negative cycle, so shortest paths are well defined. A minimum-cost path changes the weight by exactly $-\text{cost}$, and choosing the fewest edges among minimum-cost paths guarantees the shortcut-free structure of the unique-matching lemma, so $S△P$ is a common independent set; the potentials from Bellman–Ford give a new weight splitting certifying optimality at size $k+1$. The sequence best is concave in $k$ (the step gains are non-increasing).

Patterns

Problem	$M_1$	$M_2$
bipartite matching	partition by left endpoint	partition by right endpoint
spanning tree with at most $c_t$ edges of type $t$ (rainbow tree when all $c_t=1$)	graphic	colourful
arborescence rooted at $r$ exists / max branching	graphic (undirected)	partition by head, $r$ excluded
basis of vectors, at most $c$ from each group	linear	colourful
largest set of vectors independent over GF(2) whose edges also form a forest	linear	graphic
tasks with deadlines, each taken by a compatible worker	transversal (via matching)	uniform / scheduling

• Matroid parity (pick pairs of elements so that the union is independent) generalises both general matching and matroid intersection; it is polynomial for linear matroids (Lovász; Gabow–Stallmann) and needs exponentially many oracle calls in general. In contests it appears only through general matching.
• With three constraints (e.g. Hamiltonian path = graphic ∩ in-degree ≤ 1 ∩ out-degree ≤ 1) the problem is NP-hard: look for structure instead.