Matroid cogirth and quotient path

Posted on August 15, 2026 by Yu Cong, translated by GLM 5.3
Tags: ,

一个拟阵的 cogirth 是它最小（带非负权重或者元素数量最少）的 cocircuit 的大小。找一个拟阵的 cogirth 因此是图上最小割问题的推广。 假设拟阵用一个 rank oracle 给出，即使在 binary matroid 上计算 cogirth 都是 NP-hard。 所以如果能找到些计算 cogirth 简单的 matroid class 会有意思。

关于这个问题，几个月前我有个失败的想法，现在把他写下来。

1 想法

拟阵和图有很多联系。除了 graphic matroid，图上的TT-join 和TT-cut 也可以被表示成拟阵上的东西。考虑图的 incidence matrix，TT-join 要选择一个偶数大小的顶点集合TT， 所以给 incidence matrix 加上一列tt, 表示某行对应的顶点在不在TT里面。接下来要考虑这新矩阵上的 binary matroid MM。 众所周知，linear matroid 的 cocycle 就是它矩阵表示的 row space 里向量的 support，那么图的 minimum TT-cut 恰好就是新加入一列为 1 的、在 row space 里的行向量的最小 support。 而TT-join 是恰好让子图里TT中的顶点度数是奇数的边集合，考虑在 incidence matrix 把TT-join 对应的列向量选出加起来，再加上tt就会是零向量了。因此TT-join 刚好就是拟阵MM中包含tt的那些 circuit 去掉tt的部分。这个东西叫作 matroid port。

接下来我们即将观察到一个重要结论！仍然先考虑图，取任何一个 cut δ(S)\delta(S)，|S∩T||S\cap T|不是奇数就是偶数😂！因此图的 min-cut 大小是这两者中较小的：|S∩T||S\cap T|是偶数情况下最小的 cut δ(S)\delta(S)（也就是M/tM/t的 cocircuit），|S∩T||S\cap T|是奇数情况下的最小 cut（也就是TT-cut，同时也是MM的最小tt-port transversal）实际上这对任何拟阵都成立。

对拟阵 NN，记 λ(N)=min⁡{|D|:D∈𝒞*(N)} \lambda(N)=\min\{|D|:D\in \mathcal{C}^*(N)\} 为它的 cogirth，若这个最小化不可行则取值为 +∞+\infty。如果 MM 是带有一个指定元素 ff 的拟阵，它的 ff-port 是如下 clutter 𝒫f(M)={C\{f}:C∈𝒞(M),f∈C}. \mathcal{P}_f(M)= \{C\setminus\{f\}:C\in \mathcal{C}(M),\ f\in C\}. 对一个 clutter 𝒫\mathcal{P}，令 τ(𝒫)\tau(\mathcal{P}) 为 transversal（即与 𝒫\mathcal{P} 中每个成员都相交的集合）的最小大小。
Lemma1

MM 是 groundset 为 E∪{f}E\cup\{f\} 的拟阵，其中 ff 既不是 loop 也不是 coloop。则 λ(M\f)=min⁡{λ(M/f),τ(𝒫f(M))}. \lambda(M\setminus f) = \min\{\lambda(M/f),\tau(\mathcal{P}_f(M))\}.
Proof

固定 X⊆EX\subseteq E。XX 是 𝒫f(M)\mathcal{P}_f(M) 的 transversal，当且仅当不存在包含 ff 的 circuit 整个落在 (E\X)∪{f}(E\setminus X)\cup\{f\} 里。也就是说，XX 与 𝒫f(M)\mathcal{P}_f(M) 的每个成员都相交，当且仅当 f∉cl⁡M(E\X)f\notin \operatorname{cl}_M(E\setminus X)。

由标准的 closure–cocircuit 对偶，f∉cl⁡M(S)f\notin \operatorname{cl}_M(S) 当且仅当存在 MM 的一个 cocircuit DD 使得 f∈Df\in D 且 D∩S=∅D\cap S=\emptyset。取 S=E\XS=E\setminus X，这就等价于存在 cocircuit DD 满足 f∈Df\in D 且 D\{f}⊆XD\setminus\{f\}\subseteq X。于是 τ(𝒫f(M))=min⁡{|D|−1:D∈𝒞*(M),f∈D}. \tau(\mathcal{P}_f(M)) = \min\{|D|-1:D\in \mathcal{C}^*(M),\ f\in D\}.

另一方面，M/fM/f 的 cocircuit 恰好是 MM 中不含 ff 的那些 cocircuit，所以 λ(M/f)=min⁡{|D|:D∈𝒞*(M),f∉D}. \lambda(M/f) = \min\{|D|:D\in \mathcal{C}^*(M),\ f\notin D\}.

最后，M\fM\setminus f 的 cocircuit 是形如 D\{f}D\setminus\{f\}（D∈𝒞*(M)D\in \mathcal{C}^*(M)）的集合中的非空极小者。因此 M\fM\setminus f 的最小 cocircuit 要么来自 MM 中不含 ff 的 cocircuit，给出 λ(M/f)\lambda(M/f)；要么来自含 ff 的 cocircuit，给出 τ(𝒫f(M))\tau(\mathcal{P}_f(M))。

这就是图上 TT-cut/TT-join 关系的拟阵形式。在 binary graphic 的特例中，用偶大小的 terminal set TT 的 incidence vector 给图 GG 的 cycle matroid 添加一个元素 ff。port 𝒫f(M)\mathcal{P}_f(M) 就是由极小 TT-join 组成的 clutter，而穿过 ff 的 cocircuit 删去 ff 之后就是 TT-cut。于是上面的恒等式说的正是：最小割是“最小偶割”和“最小 TT-cut”中较小的那个，而后者等于 TT-join 的最小 transversal 大小。

2 Matroid port transversal

由 Lemma 1 的证明，计算 τ(𝒫f(M))\tau(\mathcal{P}_f(M)) 等价于找 MM 中包含 ff 的最小 cocircuit： τ(𝒫f(M))=min⁡{|D|−1:D∈𝒞*(M),f∈D}. \tau(\mathcal{P}_f(M)) = \min\{|D|-1:D\in \mathcal{C}^*(M),\ f\in D\}.

一些 tractable 的情形：

所以看起来（几乎）所有存在多项式时间 cogirth 算法的 matroid class，也都存在多项式时间的 port transversal 算法，不过对一般的拟阵，似乎没有办法把 port transversal 归约到 cogirth。

3 同一ground set上所有拟阵的有向图

GGW 在拟阵上定义了一个度量。 给定 ground set 同为 EE 的两个拟阵 M1,M2M_1,M_2。如果存在 ground set 为 E∪{e}E\cup \left\{ e \right\} 的拟阵 NN，使得 M1=N/eM_1=N/ e 且 M2=N\eM_2=N\setminus e，就说 M2M_2 可以由 M1M_1 经过一次初等变换得到。 他们把 M1M_1 和 M2M_2 之间的距离定义为把一个变成另一个所需初等变换的最少次数。

Lemma 1 给出了初等变换在 cogirth 问题上的算法版本。如果 NN 上的 ee-port transversal 可以被高效计算，那么 N\eN\setminus e 的 cogirth 就可以归约到 N/eN/e 上。

现在考虑一个有向图，顶点集是固定 ground set EE 上的所有拟阵。如果存在从 QQ 到 LL 的初等变换，就从 QQ 向 LL 引一条弧。每条弧 aa 都关联一个 ground set 为 E∪{e}E\cup \left\{ e \right\} 的中间拟阵 MaM_a。如果 MaM_a 上的 ee-port transversal 可以被高效求解，就称弧 aa 是 certified 的。 一条简单路径如果每条弧都是 certified 的，就称它是 certified 的。 于是 Lemma 1 说明：若给定了从某个我们能计算 cogirth 的拟阵 QQ 到 LL 的多项式长度的 certified path，就可以在多项式时间内计算拟阵 LL 的 cogirth。

注意这个有向图是有限的，因为 ground set 是固定的。它还是弱连通的，并且是一个 DAG：当 port 元素 ee 既不是 loop 也不是 coloop 时，沿一条弧走会让 rank 增加 1；否则这条弧是自环。

容易看出，如果存在从 QQ 到 LL 的路径，那么 QQ 必是 LL 的 quotient。

4 quotient对之间的路径

Oxley 定义了一类有趣的集合族，叫作 modular cut。 modular cut 在 certified path 和 matroid port transversal 之间建立了联系。 参考文献见 GGW 第 6 节。

设 MM 是 ground set 为 EE 的拟阵，A,B⊂EA,B\subset E。 若 rank function 在它们身上是 modular 的，就称 (A,B)(A,B) 是一个 modular pair： r(A)+r(B)=r(A∪B)+r(A∩B) r(A)+r(B)=r(A\cup B)+r(A\cap B)

EE 的子集族 ℱ\mathcal F 是一个 modular cut，如果：
  • 向上封闭。若 X⊂Y⊂EX\subset Y\subset E 且 X∈ℱX\in \mathcal F，则 Y∈ℱY\in \mathcal F
  • 若 (X,Y)(X,Y) 是modular pair，则 X∩Y∈ℱX\cap Y\in \mathcal F
  • 若 Y∈ℱY\in \mathcal F 且 X⊂YX\subset Y 满足 r(X)=r(Y)r(X)=r(Y)，则 X∈ℱX\in \mathcal F。

注意我们这里 modular cut 的定义遵循 GGW，与 Oxley 的定义不同。
Theorem2Oxley

设 ℱ\mathcal F 是拟阵 MM 的一个 modular cut，则存在 ground set 为 E(M)∪{e}E(M)\cup \left\{ e \right\} 的拟阵 NN，使得 N\e=MN\setminus e=M，且对每个 X⊂E(M)X\subset E(M)，rN(X∪{e})=rM(X)r_N(X\cup \left\{ e \right\})=r_M(X) 当且仅当 X∈ℱX\in \mathcal F。

Theorem 2 给出了 modular cut 和初等变换之间的联系。 给定 LL 的一个 modular cut ℱ\mathcal F，可以构造中间拟阵 NN 和“弧尾”拟阵 Q=N/eQ=N/e，使得
  • Q→LQ \to L 是一次初等变换
  • rQ(X)=rL(X)−𝟏X∈ℱr_Q(X)=r_L(X)-\bm{1}_{X\in \mathcal F}
  • NN 的 ee-port恰好是 ℱ\mathcal F 中inclusionwise极小的集合。
Corollary3

XX 是 NN 的 ee-port transversal 当且仅当 E−X∉ℱE-X\notin \mathcal F。

4.1 Higgs lifts

设 Q,LQ,L 是 ground set 同为 EE 的两个拟阵。如果 QQ 的每个 flat 都是 LL 的 flat，就称 QQ 是 LL 的 quotient。

令 k=r(L)−r(Q)k=r(L)-r(Q)，并对 i∈[k]i\in [k] 定义 ri(X)=min⁡{rL(X),rQ(X)+i}r_i(X)=\min \left\{ r_L(X),r_Q(X)+i \right\} 每个 rir_i 都是 EE 上某个拟阵的 rank function。

这个操作叫作 Higgs lifts。背景见 https://www.sciencedirect.com/science/article/pii/S0196885819300752 及其参考文献。 令 MiM_i 为 rank function 是 rir_i 的拟阵，则 L=MkL=M_k，Q=M0Q=M_0。 MiM_i 的基是大小为 r(Q)+ir(Q)+i、张成 QQ 且在 LL 中独立的集合。
Lemma4

设 QQ 是 LL 的 quotient，Q=M0→⋯→Mk=LQ=M_0 \to \cdots \to M_k=L 是从 QQ 到 LL 的一列 Higgs lifts， 则边 Mi−1→MiM_{i-1}\to M_i 是由 modular cut ℱi={X⊂E:rL(X)−rQ(X)≥i}\mathcal F_i=\left\{ X\subset E: r_L(X)-r_Q(X)\geq i \right\} 诱导的初等变换。
Proofsketch

前半部分是 Oxley 书中的 Proposition 7.3.5，只是那里用的名字是 “elementary quotient” 而不是初等变换。

modular cut 的部分本质上就是 https://www.sciencedirect.com/science/article/pii/0012365X78901218 的 Theorem 3.4，不过他们对我们的 modular cut 用的名字是 modular filter，而他们的 modular cut 指的是 modular filter 中的 flat（这也是 Oxley 的定义）。
Theorem5

设 QQ 是 LL 的 quotient。则 λ(L)=min⁡{λ(Q),hk}, \lambda(L)=\min \left\{ \lambda(Q),h_k \right\}, 其中 hk=min⁡{|T|:T⊆E,[rL−rL(E−T)]−[rQ−rQ(E−T)]>0}h_k=\min \left\{ |T|:T\subseteq E, [r_L-r_L(E-T)]-[r_Q-r_Q(E-T)]>0 \right\}。
Proof

由 Lemma 1，LL 的 cogirth 是 QQ 的 cogirth 与 Higgs lifts 上各中间拟阵的最小 port transversal 之中的最小值。

把 Lemma 4 和 Corollary 3 结合起来可知，每个最小 port transversal 就是 hi=min⁡{|T|:T⊆E,rL(E−T)−rQ(E−T)<i}h_i=\min \left\{ |T|:T\subseteq E, r_L(E-T)-r_Q(E-T)<i \right\}。

注意 {hi}i∈[k]\left\{ h_i \right\}_{i\in [k]} 是不增的，因此只需要计算 hk=min⁡{|T|:T⊆E,[rL−rL(E−T)]−[rQ−rQ(E−T)]>0}h_k=\min \left\{ |T|:T\subseteq E, [r_L-r_L(E-T)]-[r_Q-r_Q(E-T)]>0 \right\}。

然而，当 QQ 是 LL 的 quotient 时这并没有什么用。 事实上，当 λ(L)≠λ(Q)\lambda(L)\neq \lambda(Q) 时，LL 的最小 cocircuit 总是 hkh_k 的可行解，计算 hkh_k 和求 λ(L)\lambda(L) 一样难。

4.2 Separation path

Theorem 2 说明拟阵 MM 的每个 modular cut 都给出一个初等变换 N/e→MN/e\to M。

GGW 还给出了一种基于 separation 寻找 modular cut 的方法。
Lemma6

设 λM(X)=rM(X)+rM(E−X)−rM(E)\lambda_M(X)=r_M(X)+r_M(E-X)-r_M(E) 是 ground set 为 EE 的拟阵 MM 的 connectivity function，(A,B)(A,B) 是 EE 的一个二部划分。 则所有满足 λM/X(A−X)=0\lambda_{M/X}(A-X)=0 的集合 X⊆EX\subseteq E 构成的集合族是 MM 的一个 modular cut。
Lemma7Lemma 5.4 in GGW

设 LL 是一个拟阵，(A,B)(A,B) 是 E(L)E(L) 的一个划分。则存在一条初等变换的路径 L=Mk←⋯←M0=Q, L= M_k \leftarrow \cdots \leftarrow M_0=Q, 其中 Mi−1M_{i-1} 是由 MiM_i 通过 Lemma 6 和 Theorem 2 得到的，并且 λMi(A)=i\lambda_{M_i}(A)=i。

沿用与 Higgs lifts 相同的论证，我们有 λ(L)=min⁡{λ(L\A),λ(L\B),min⁡i∈[k]hi}\lambda(L)=\min\left\{ \lambda(L\setminus A),\lambda(L\setminus B),\min_{i\in [k]} h_i \right\}，其中 hih_i 是满足 λM/(E−X)(A−(E−X))>0\lambda_{M/(E-X)}(A-(E-X))>0 的 X⊆EX\subseteq E 的最小大小。 设 XX 是 LL 的一个 cocircuit，可以看出 XX 是 hkh_k 的可行解当且仅当 X−AX-A 和 X−BX-B 都非空。 于是 λ(L)\lambda(L) 的这个刻画简单地退化成一个显然的事实：LL 的最小 cocircuit 要么含于 AA、要么含于 BB、要么同时跨越 AA 和 BB……

5 为什么这些路径对计算cogirth没帮助 「by chatgpt」

上面的两种路径构造对组织证明有帮助，但它们本身并没有创造出新的算法。原因在于：从 quotient QQ 到 LL 的任何一条有向路径，都只是把一个属于该 quotient 对的不变量分解开而已。

设 QQ 是 LL 在公共 ground set EE 上的 quotient。定义 LL 相对于 QQ 的 relative cogirth 为 ρ(Q,L)=min⁡{|T|:T⊆E,[rL(E)−rL(E−T)]−[rQ(E)−rQ(E−T)]>0}. \rho(Q,L)= \min\left\{ |T|:T\subseteq E, [r_L(E)-r_L(E-T)]-[r_Q(E)-r_Q(E-T)]>0 \right\}. 于是 TT 是 ρ(Q,L)\rho(Q,L) 的可行解，当且仅当删除 TT 在 LL 中造成的秩损失严格大于在 QQ 中造成的秩损失。也就是说，TT 杀掉了某些在 LL 中出现而在 QQ 中不出现的秩增量。
Theorem8

设 QQ 是 LL 的 quotient。则 λ(L)=min⁡{λ(Q),ρ(Q,L)}. \lambda(L)=\min\left\{ \lambda(Q),\rho(Q,L) \right\}. 此外，若 Q=M0→M1→⋯→Mk=L Q=M_0\to M_1\to\cdots\to M_k=L 是任意一条非平凡的初等变换路径，则 ρ(Q,L)=mini∈[k]ρ(Mi−1,Mi). \rho(Q,L)=\min_{i\in[k]} \rho(M_{i-1},M_i). 对单独一条弧 Mi−1→MiM_{i-1}\to M_i，数 ρ(Mi−1,Mi)\rho(M_{i-1},M_i) 恰好是中间那个 ground set 多出一个元素的拟阵的最小 ee-port transversal。
Proof

一个集合 TT 会降低拟阵 MM 的秩，当且仅当 TT 包含 MM 的某个 cocircuit。 因为 QQ 是 LL 的 quotient，QQ 中的任何秩损失也是 LL 中的秩损失。 因此 QQ 的每个 cocircuit 都包含 LL 的某个 cocircuit，于是 λ(L)≤λ(Q)\lambda(L)\leq \lambda(Q)。另外，若 TT 是 ρ(Q,L)\rho(Q,L) 的可行解，则它降低了 LL 的秩，从而包含 LL 的某个 cocircuit；因此 λ(L)≤|T|\lambda(L)\leq |T|。这就证明了 λ(L)≤min⁡{λ(Q),ρ(Q,L)}. \lambda(L)\leq \min\left\{ \lambda(Q),\rho(Q,L) \right\}.

反过来，设 DD 是 LL 的最小 cocircuit。若删除 DD 会降低 QQ 的秩，则 DD 包含 QQ 的某个 cocircuit，于是 λ(Q)≤|D|=λ(L)\lambda(Q)\leq |D|=\lambda(L)。若删除 DD 不会降低 QQ 的秩，则 DD 是 ρ(Q,L)\rho(Q,L) 的可行解，于是 ρ(Q,L)≤|D|=λ(L)\rho(Q,L)\leq |D|=\lambda(L)。因此 min⁡{λ(Q),ρ(Q,L)}≤λ(L), \min\left\{ \lambda(Q),\rho(Q,L) \right\}\leq \lambda(L), 这就证明了第一个结论。

对于路径的结论，令 S=E−TS=E-T 并令 δi(S)=rMi(S)−rMi−1(S). \delta_i(S)=r_{M_i}(S)-r_{M_{i-1}}(S). 由于每条非平凡的弧都让 rank 增加 1，所以 δi(E)=1\delta_i(E)=1 且 δi(S)∈{0,1}\delta_i(S)\in\left\{ 0,1 \right\}。同时 rL(S)−rQ(S)=∑i=1kδi(S). r_L(S)-r_Q(S)=\sum_{i=1}^k \delta_i(S). 因此 [rL(E)−rL(S)]−[rQ(E)−rQ(S)]>0⇔∑i=1k(1−δi(S))>0⇔δi(S)=0 for some i. \begin{aligned} &[r_L(E)-r_L(S)]-[r_Q(E)-r_Q(S)]>0 \\ &\qquad\Longleftrightarrow \sum_{i=1}^k (1-\delta_i(S))>0 \\ &\qquad\Longleftrightarrow \delta_i(S)=0 \text{ for some }i. \end{aligned} 对 T=E−ST=E-S 取最小值即得 ρ(Q,L)=mini∈[k]ρ(Mi−1,Mi). \rho(Q,L)=\min_{i\in[k]}\rho(M_{i-1},M_i). 对于单独一条弧，其 modular cut ℱ\mathcal F 满足 rMi−1(S)=rMi(S)−𝟏S∈ℱr_{M_{i-1}}(S)=r_{M_i}(S)-\bm 1_{S\in\mathcal F}，所以 δi(S)=0\delta_i(S)=0 当且仅当 S∉ℱS\notin\mathcal F。由 Corollary 3，这恰好就是 T=E−ST=E-S 是 ee-port transversal 的条件。

这个定理说明 certified path 并没有改变底下的优化问题：它只是把 relative cogirth ρ(Q,L)\rho(Q,L) 写成沿路径各个 port-transversal 值的最小值。因此，只有当所选的每条弧的 label 都各自比原来的相对问题更容易时，路径才有用。

5.1 Higgs lifts

对 Higgs 路径 Q=M0→⋯→Mk=LQ=M_0\to\cdots\to M_k=L，第 ii 条弧由 ℱi={X⊆E:rL(X)−rQ(X)≥i} \mathcal F_i=\left\{ X\subseteq E:r_L(X)-r_Q(X)\geq i \right\} 诱导，因此它的 port-transversal 值是 hi=min⁡{|T|:T⊆E,rL(E−T)−rQ(E−T)<i}. h_i=\min\left\{ |T|:T\subseteq E, r_L(E-T)-r_Q(E-T)<i \right\}. 序列 hih_i 是不增的，所以 Higgs 路径上最小的 label 是 hkh_k。但是 hk=min⁡{|T|:rL(E−T)−rQ(E−T)<rL(E)−rQ(E)}=min⁡{|T|:[rL(E)−rL(E−T)]−[rQ(E)−rQ(E−T)]>0}=ρ(Q,L). \begin{aligned} h_k &=\min\left\{ |T|: r_L(E-T)-r_Q(E-T)<r_L(E)-r_Q(E) \right\}\\ &=\min\left\{ |T|: [r_L(E)-r_L(E-T)]-[r_Q(E)-r_Q(E-T)]>0 \right\}\\ &=\rho(Q,L). \end{aligned} 于是对 quotient 对 Q≤LQ\leq L 来说，Theorem 5 恰好就是 Theorem 8。特别地，当 λ(L)≠λ(Q)\lambda(L)\neq \lambda(Q) 时，LL 的最小 cocircuit 是 hkh_k 的可行解，所以计算最后一个 Higgs label 本身就已经是在计算 λ(L)\lambda(L) 中最难的那部分了。

5.2 Separation path

现在取 Lemma 7 给出的分离路径。设 (A,B)(A,B) 是 E(L)E(L) 的一个划分，令 k=λL(A)k=\lambda_L(A)。端点 Q=M0Q=M_0 满足 λQ(A)=0\lambda_Q(A)=0，并且与 LL 有相同的两个 side minor，即 Q/A=L/A,Q/B=L/B. Q/A=L/A, \qquad Q/B=L/B. 也就是说，QQ 是把 AA 与 BB 之间的全部连通性杀掉之后从 LL 得到的拟阵。由于 λQ(A)=0\lambda_Q(A)=0，QQ 的每个 cocircuit 都落在某一侧。因此 Theorem 8 中的 λ(Q)\lambda(Q) 项只是答案中“含于 AA 或含于 BB”的那部分。

相对的那一项则是跨越的部分。为了从代数上看清这一点，设 T⊆ET\subseteq E，令 S=E−TS=E-T。由于 QQ 关于 (A,B)(A,B) 是分离的，且它的 side minor 与 LL 的一致，故 rQ(S)=rL/B(S∩A)+rL/A(S∩B). r_Q(S)=r_{L/B}(S\cap A)+r_{L/A}(S\cap B). 把两个收缩的秩展开，得 rQ(S)=rL(B∪(S∩A))−rL(B)+rL(A∪(S∩B))−rL(A). \begin{aligned} r_Q(S) &= r_L(B\cup (S\cap A))-r_L(B) + r_L(A\cup (S\cap B))-r_L(A). \end{aligned} 再利用 k=λL(A)=rL(A)+rL(B)−rL(E)k=\lambda_L(A)=r_L(A)+r_L(B)-r_L(E)，得到 rL(S)−rQ(S)=k−λL/S(A−S). r_L(S)-r_Q(S)=k-\lambda_{L/S}(A-S). 于是 [rL(E)−rL(S)]−[rQ(E)−rQ(S)]=k−[rL(S)−rQ(S)]=λL/S(A−S). \begin{aligned} &[r_L(E)-r_L(S)]-[r_Q(E)-r_Q(S)] \\ &\qquad = k-[r_L(S)-r_Q(S)]\\ &\qquad = \lambda_{L/S}(A-S). \end{aligned} 把 S=E−TS=E-T 代入，就有 ρ(Q,L)=min⁡{|T|:T⊆E,λL/(E−T)(A∩T)>0}. \rho(Q,L)= \min\left\{ |T|:T\subseteq E, \lambda_{L/(E-T)}(A\cap T)>0 \right\}. 这恰好就是分离路径计算里最后那个 hkh_k。

若 TT 是 LL 的一个 cocircuit，则 L/(E−T)L/(E-T) 是 ground set 为 TT、rank 为 1 的拟阵，且在这个收缩里 TT 中没有元素是 loop。因此 λL/(E−T)(A∩T)>0 \lambda_{L/(E-T)}(A\cap T)>0 当且仅当 A∩TA\cap T 和 B∩TB\cap T 都非空。所以分离路径的公式说的只是：LL 的最小 cocircuit 必属于三种类型之一——含于 AA、含于 BB、或跨越分离 (A,B)(A,B)。

因此分离路径并不是 cogirth 的一种新归约。它只是对“杀掉 AA–BB 连通性所得到的特殊 quotient QQ”套用 relative cogirth 公式，其最后一个 port-transversal 项恰好就是最小跨越 cocircuit 那一项。