本文将对 STOC2022 的一篇论文: "The shortest even cycle problem is tractable" 进行解读. 虽然这是一篇很新的文章, 但是其核心技术还是相当通俗易懂的.

下文讨论的皆为无权图, 或者说, 环的长度就是经过的点的数目.

我们知道, 最短奇环是容易解决的, 因为最短奇回路 (closed walk) 一定是环 (cycle). 其次, 无向图情况下的最短偶环也在较早的时候规约到了一般图带权匹配, 从而得到了多项式复杂度的解法.

注意: 本文仅梳理了原文的主线脉络, 细节处可能有所不同, 也未涉及

代数刻画

我们从排列观点来看. 对于任何一个排列 \(\sigma \in S_n\), 可将其看做 \(\{1,\dots,n\}\) 的一个环分解, 我们知道, \(\operatorname{sgn} (\sigma) = (-1)^{e(\sigma)}\), 其中 \(e(\sigma)\) 是偶环的数量. 我们知道,

\[\det A = \sum_{\sigma \in S_n} \operatorname{sgn} (\sigma) \prod_{k=1}^n A_{k \sigma(k)}, \quad \operatorname{per} A = \sum_{\sigma \in S_n} \prod_{k=1}^n A_{k \sigma(k)}. \]

现在我们希望统计偶环的信息, 如果记

\[\operatorname{pcc} A = \sum_{\sigma \in S_n} [ 2 \nmid e(\sigma) ] \prod_{k=1}^n A_{k \sigma(k)}, \]

我们立刻就得到等式

\[\operatorname{pcc} A = \frac 12 ( \operatorname{per} A - \det A). \]

与之前对最短奇环的观察相似, pcc (parity cycle cover) 与最短偶环的计算有着重要的联系. 记形式元 \(X\), 记原图的邻接矩阵为 \(A\), 那么 \(\operatorname{pcc} (A + IX)\) 的最高次项就指示出了最短偶环. 也即, 将 \(A\) 中任意非零的一项看做形式变元, 若最高次项为 \(X^{n-k}\), 那么 \(k\) 就是最短偶环的长度.

从 2 到 4

按照 \(\operatorname{pcc}\) 的定义, \(\operatorname{pcc}(A+IX)\) 是一个关于 \(X\) 以及 \(A_{11},\dots,A_{nn}\) 的多项式, 若我们取定有限域 \(F\), 著名的 Schwartz–Zippel 引理保证了, 我们只需要将 \(A\) 中对应的有边的项带入一个 \(F\) 中均匀随机的值, 由于这是一个关于 \(A_{11},\dots,A_{nn}\) 的不超过 \(n\) 次的多项式, 对应的 \(X^{n-k}\) 次项的系数有 \(\geq 1 - \frac{n}{|F|}\) 的概率非零!

域上的多项式通常来说没有域本身简单, 但是我们有一个简单的转化, 只要取足够大的域 \(|F| > n\), 然后选取 \(n+1\) 个点带入进行插值, 就可以转化成域本身的问题了.

但需要小心的是, 虽然 \(\det\) 是好算的, 但 \(\operatorname{per}\) 一般情况下是困难的. 但庆幸的是, 我们在这个问题上有一些已知的重要结果. 显然, 在 \(\bmod 2\) 的情况下, \(\operatorname{per} A = \det A\), 而在 \(\bmod 4\) 的情况下, \(\operatorname{per} A\) 也有多项式复杂度的算法. 我们不妨考虑先让 \(F=\mathbb F_{2^d}\), 然后考虑如何求出 \(\det, \operatorname{per}\) 更多些的信息.

回顾我们是如何在计算上处理 \(\mathbb F_{2^d}\) 的, 我们需要首先找一 \(d\) 次不可约多项式 \(f(X)\), 然后有 \(\mathbb F_2[X] / f(X) \cong \mathbb F_{2^d}\). 为了支持除以 \(2\), 一个自然的想法是将"模 \(2\) 多项式"改成"模 \(4\) 多项式". 这时, 我们记 \(\mathbb E_{2^d} = (\mathbb Z / 4\mathbb Z) [X] /f(X)\), 这时的 \(f(X)\) 系数可以直接取保留原本的 \(\{0, 1\}\) 中对应的值, 这样的话, 由于

\[2\operatorname{pcc} A = \operatorname{per} A - \det A, \]

我们计算出了 \(\operatorname{per} A - \det A\) 取 \(A\in M_{n\times n}(\mathbb E_{2^d})\) 的值之后, 就可以还原出 \(\operatorname{pcc} A\) 在 \(\mathbb F_{2^d}\) 下的信息了.

per 的计算

我们知道, Samuelson–Berkowitz 算法已经能在 \(O(n^4)\) 算任意环上的矩阵 \(\det\) 了 (虽然我们也有办法更快, 但这里不是那么重要), 所以问题的关键在于如何计算 \(\operatorname{per}\).

事实上, Valiant 先前已经提出了一个 \(\tilde O(n^5)\) 的算法计算 \(\operatorname{per}\), 但原文中在此进一步将做法优化到了 \(\tilde O(n^{\omega + 2})\), 而且是比较巧妙的.

我们可以对于 Gauss 消元进行观察. Gauss 消元基于的关键性质在于, 将矩阵的一行乘以一个数加到另一行上去, 不影响 \(\det\) 的值, 但是对于 \(\operatorname{per}\) 呢? 我们注意, \(\operatorname{per}\) 依然满足线性性, 也即, 将一行乘以一个数 \(\tau\), 那么 \(\operatorname{per}\) 的值相应的乘以 \(\tau\), 以及对应的有某行上的可加性. 因此, 对于矩阵 \(M\), 设 \(M'\) 是将第 \(j\) 行减去第 \(i\) 行的 \(\tau\) 倍, \(M''\) 是将第 \(j\) 行替换成第 \(i\) 行, 那么我们有

\[\operatorname{per} M = \operatorname{per} M' + \tau \operatorname{per} M''. \]

我们知道 \(\det M'' = 0\), 但是 \(\operatorname{per} M'' \neq 0\), 这有什么用呢? 为此, 本文最为精彩的一步来了: 我们将给 \(\operatorname{per} M''\) 与某个矩阵的 \(\det\) 再次建立联系! 由于 \(M''\) 有两行是相同的, 不妨设 \(i=1\), \(j=2\), \(M''_{1k} = a_k\), 我们可以将 \(\operatorname{per} M''\) 写作:

\[\begin{align*} \operatorname{per} M'' &= \sum_{\sigma \in S_n} ([\sigma(1) < \sigma(2)] + [\sigma(1) > \sigma(2)]) \prod_{k=1}^n M''_{k\sigma(k)}\\ &= 2 \sum_{\sigma \in S_n} [\sigma(1) < \sigma(2)] \prod_{k=1}^n M''_{k\sigma(k)}\\ &= 2 \left(\sum_{k=0}^{n-2} [x^k]\right) \det \begin{pmatrix} a_1 & a_2 x & \cdots & a_n x^{n-1}\\ a_1x^{n-1} & a_2 x^{n-2} & \cdots & a_n\\ M''_{31} & M''_{32} & \cdots & M''_{3n} \\ \vdots & \vdots & \ddots & \vdots\\ M''_{n1} & M_{n2} & \cdots & M_{nn} \end{pmatrix}. \end{align*} \]

等等, 最后一步是什么? 让我们冷静一下. 看看一个置换 \(\sigma\) 取到的 \(x\) 的次数是什么, 是 \(x^{n-1 + \sigma(1) - \sigma(2)}\), 所以提取 \(0\sim n-2\) 次项刚好就只取了 \(\sigma(1) < \sigma(2)\) 的贡献. 由于前面乘以了 \(2\), 所以 \(\det\) 的符号也不重要了. 而且, 对于非奇异的多项式矩阵, 存在一个确定性算法在 \(\tilde O(n^{\omega} \mu)\) 的时间内计算出其行列式. [Labahn–Neiger–Zhou, 2017] (我还不会这个的具体做法, 之后看有没有时间研究一下) 我们可以随机选取 \(\rho \in \mathbb F_{2^d}\) 检验 \(\det M''(\rho)\) 是否是 \(0\), 如果不是, 则调用该算法. 我们这个矩阵的平均度数满足 \(\mu \leq 2\), 也就是说可以在复杂度 \(\tilde O(n^{\omega})\) 的时间内算出结果.

我们还未完全论述这个类似 Gauss 消元过程的完整流程. 记 \(\overline{\upsilon}\) 将 \(\upsilon\in \mathbb E_{2^d}\) 按照自然的方法映射到 \(\mathbb F_{2^d}\). 我们首先要指出的是, \(\upsilon\) 可逆当且仅当 \(\overline{\upsilon}\) 可逆. 当 \(\overline{\upsilon}\) 可逆, 我们记 \(\overline{\upsilon} \cdot \overline{\tau} = 1\), 那么就有 \(\upsilon \cdot \tau \in 1 + 2\mathbb E_{2^d}\). 这里我们用类似 Newton 迭代的方法, 可以将 \(\tau\) 提升到

\[\tau_* = \tau ( 2 - \upsilon \tau ), \]

易见 \(\upsilon \cdot \tau_* = 1\). 因此, 我们先从小到大处理 \(M\) 的每一列, 如果第 \(i\) 列的 \(j\in [i, n]\) 部分存在一个 \(\overline{M_{ji}} \neq 0\) 非零的, 将其换到第 \(i\) 行, 并用来消去其他行. 否则如果有一个非零的, 依然可以用来消去剩下的, 如果全 \(0\), 则答案为 \(0\).

清算

在这一过程中, 我们消元了 \(O(n^2)\) 次, 所以产生了 \(O(n^2)\) 个 \(M''\) 需要计算, 复杂度是 \(\tilde O(n^{\omega+2})\), 支配了 \(\det\) 中的 \(\tilde O(n^4)\) 一项. 因此通共复杂度是 \(\tilde O(n^{\omega+2})\).

此外, 我们需要分析错误率. 我们总共进行了 \(O(n)\) 次 \(\operatorname{per}\) 的调用, 也就是总共进行了 \(O(n^3)\) 次由 Schwartz–Zippel 引理保证正确性的操作. 总共正确的概率被 union bound 控制到 \(1 - O(n^4/2^d)\). 当 \(d = 5\lg n\) 时, 我们有正确率 \(1 - O(n^{-1})\).