拟阵交算法

Oracle 模型与目标 ​

给定同一有限底集 $E$ 上的两个拟阵

$$M_1=(E,{\mathcal{I}}_1),M_2=(E,{\mathcal{I}}_2),$$

以及独立性 oracle：输入 $X\subseteq E$，返回 $X\in {\mathcal{I}}_j$ 与否。无权拟阵交要找

$$max\{|I|:I\in {\mathcal{I}}_1\cap {\mathcal{I}}_2\}.$$

算法从 $I=\varnothing$ 开始，每轮构造交换图并增广一次；至多增广 $r\le |E|$ 次，其中 $r$ 是最优公共独立集大小。若当前 $|I|=k$，朴素实现枚举 $I\times (E\setminus I)$ 中的交换对，以 $O(k|E|)$ 次 oracle 调用建图。对 $k=0,1,\dots ,r-1$ 求和，总计

$$O(r^2|E|)$$

次独立性查询和同阶的附加图搜索工作；若一次 oracle 成本为 $T_{\mathrm{ind}}$，oracle 时间相应乘上它。基本回路、rank oracle 与 Cunningham 型算法能改善此界，本页固定的是可直接核验的朴素 oracle 实现。

交换有向图的方向 ​

固定当前公共独立集 $I$。交换图 $D_I$ 的顶点是底集 $E$，并在 $I$ 与 $E\setminus I$ 之间加两类方向相反的弧。对 $a\in I,b\notin I$：

$$a\to b⟺I-a+b\in {\mathcal{I}}_1,$$$$b\to a⟺I-a+b\in {\mathcal{I}}_2.$$

源集合与汇集合为

$$S_I=\{b\notin I:I+b\in {\mathcal{I}}_1\},T_I=\{b\notin I:I+b\in {\mathcal{I}}_2\}.$$

因此一条 $S_I$ 到 $T_I$ 的路从外部元素开始，先沿 $M_2$ 弧进入 $I$，再沿 $M_1$ 弧离开，如此交替。交换图弧方向只是约定，但 sources、sinks 和后续证明必须与约定一致；交换其中一类方向却不交换端点集合会破坏增广语义。

最短增广路与对称差 ​

若 $b\in S_I\cap T_I$，长度零的路径直接把 $b$ 加入 $I$。否则在 $D_I$ 中找一条最短的 $S_I$–$T_I$ 路

$$P=(b_0,a_1,b_1,\dots ,a_k,b_k),$$

其中 $b_j\notin I,a_j\in I$。令

$$I^{\prime }=I\mathrm{△}V(P)=(I\setminus \{a_1,\dots ,a_k\})\cup \{b_0,\dots ,b_k\}.$$

外部顶点比内部顶点多一个，所以 $|I^{\prime }|=|I|+1$。真正需要证明的是 $I^{\prime }$ 同时属于 ${\mathcal{I}}_1,{\mathcal{I}}_2$。

每条弧只保证一次单元素交换保持某个拟阵独立，不能把这些局部保证无条件串联。最短性排除了能由基本回路消去产生的“捷径”：若最终 $I^{\prime }$ 在 $M_1$ 中含回路，沿路径取该回路最早出现的新增元素，拟阵回路消去会找到一个更早可交换的旧元素，从而生成跳过一段路径的 $M_1$ 弧；这与 $P$ 最短矛盾。对 $M_2$ 从路径另一端作对称论证。故最短路径的对称差确为公共独立集。

无增广路时的最优性证书 ​

若从 $S_I$ 无法到达 $T_I$，令 $R$ 为交换图中从 $S_I$ 可达的全部元素。交换闭包性质推出

$$r_1(E\setminus R)=|I\setminus R|,r_2(R)=|I\cap R|.$$

直观上，若 $E\setminus R$ 在 $M_1$ 中还能增加秩，就会存在新的源或从可达内部元素通向不可达外部元素的 $M_1$ 交换弧；若 $R$ 在 $M_2$ 中还能增加秩，则会出现可达汇或相应 $M_2$ 弧。两者都与可达集定义矛盾。

取 $U=E\setminus R$，得到

$$r_1(U)+r_2(E\setminus U)=|I\setminus R|+|I\cap R|=|I|.$$

另一方面，任意公共独立集 $J$ 都满足

$$|J|\le r_1(U)+r_2(E\setminus U).$$

所以当前 $I$ 已最优，$U$ 同时给出 拟阵交 min–max 定理公理库拟阵交定理Matroid intersection theorem · Edmonds matroid intersection theorem两个有限拟阵的最大共同独立集大小，等于一次底集切分上的两侧秩之和的最小值。的等值证书。算法不是在“找不到路”时凭经验停止，而是产出可验证上界。

具体例子：二分匹配 ​

给二分图 $G=(L\bigsqcup R,E)$，在边集上定义两个 partition matroids：

• $M_1$ 要求每个左端点至多关联一条已选边；
• $M_2$ 要求每个右端点至多关联一条已选边。

公共独立集恰是匹配。交换图中的外部边若能替换一条冲突的已匹配边，就对应沿交替路翻转端点占用；从两端都可直接加入的外部边之间找到增广路，正恢复普通 匹配增广路公理库增广路Augmenting path相对于当前匹配，边在未匹配与已匹配之间交替且两个端点均未匹配的路径。。拟阵交算法把“端点冲突”推广成任意两套拟阵独立性 oracle。

失败边界与近邻算法 ​

单拟阵最大权基由贪心解决；两个拟阵的无权公共独立集需要交换图增广。加权拟阵交还必须给弧赋 reduced cost、维护势并找最短路径，不能把本页 BFS 中的“最短”简单改成按元素权排序。

三个 partition matroid 的交已经能表达三维匹配，一般为 NP-hard；“两个”是该多项式算法的结构边界。共同独立集族自身通常不是拟阵，因此不能对 ${\mathcal{I}}_1\cap {\mathcal{I}}_2$ 再运行普通拟阵贪心。

参考资料

• Jack Edmonds, “Matroid Intersection,” Annals of Discrete Mathematics 4, 1979, 39–49.
• William H. Cunningham, “Improved Bounds for Matroid Partition and Intersection Algorithms,” SIAM Journal on Computing 15(4), 1986.
• Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, chapters 39–41.