结果族 120：Almost-linear-time exact matching and prescribed-degree factors in general graphs · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
舞会上想给同学们配舞伴，每人只能牵一个人，怎样配出最多对？这个”最大匹配”问题自 1965 年起就有了多项式算法，但速度长期停在”边数 × 根号顶点数”的台阶上。这篇论文一步跨到近乎线性——几乎和把图读进电脑一样快。
关键词卡片
@@M@@f@@-因子（@@M@@f@@-factor）：给每个顶点规定度数的生成子图问题。@@M@@(n+m)^{1+o(1)}@@，几乎与输入规模同阶。看个具体例子
数一数：粗边 @@M@@\{1\text{-}2,\ 3\text{-}4,\ 5\text{-}6\}@@ 共 3 条且互不碰头，已是最大匹配。定理保证：对任何 @@M@@n@@ 点 @@M@@m@@ 边的简单图，单一随机算法在每条计算路径上都于 @@M@@(n+m)^{1+o(1)}@@ 时间停机，至少以 @@M@@2/3@@ 的概率输出显式最大匹配；答案输出前必被验证，绝不谎报。同一框架还近乎线性地解决 @@M@@f@@-因子的判定与构造。
为什么值得关心
此前最快的组合方法是 Micali–Vazirani 算法；前几年借近乎线性流算法，二部图率先突破到近乎线性，一般图却因”花”结构迟迟未动。本文把它扛过奇集合约束这道最难的门槛，推广到任意简单图，刷新了五十年的老纪录。
暂无形式化证明（AI 结果待核验）
第一级台阶
入门导读用舞会配对作比：每人只能牵一个舞伴，怎样配出最多对？这个”最大匹配”问题自 1965 年起就有多项式算法，速度却长期停在”边数乘根号顶点数”的台阶上。翻译一下：对象是图中一批互不碰头的边；操作是不断调整配对使总数增多；论文断言：存在一个随机算法，跑得几乎和把图读进电脑一样快，还能以高概率给出确凿的最大配对——并顺带把”给每个顶点规定度数”的生成子图问题做到同样快。
第二级台阶
用本科术语说：匹配是两两端点不交的边集，最大基数匹配求其最大者；@@M@@f@@-因子是满足 @@M@@\deg_F(v)=f(v)@@ 的生成子图。计算模型是字长 @@M@@\Theta(\log n)@@ 的随机 word-RAM，一切读写、有限精度与输出都计费。时间界 @@M@@(n+m)^{1+o(1)}@@ 写成 @@M@@Cp^{1+\eta(p)}@@（@@M@@p=n+m@@，@@M@@\eta@@ 非增趋于 @@M@@0@@）。一般图特有的障碍是奇集合约束——Edmonds 匹配多面体的顶点度不等式放行三角形上各边取 @@M@@1/2@@，纯流方法管不住它。
第三级台阶
定理（thm:main）在此陈述：单一均匀随机算法对任何 @@M@@n@@ 点 @@M@@m@@ 边简单图，在每条计算路径上至多 @@M@@Cp^{1+\eta(p)}@@ 条指令内停机，且以至少 @@M@@2/3@@ 概率输出显式最大匹配。假设”简单无权无向图、邻接表输入”界定了计费口径，”每条路径”意味着连失败的随机尝试也计入时间。结论经见证保真归约（Beneš 型重排网络加路径替换）落到次三次图的完美匹配核心，再均匀化成单一程序；推论给出 @@M@@f@@-因子判定与构造的同样保证，扩展仅对数级。
证明任一无权简单图的最大匹配（maximum-cardinality matching）可用单一随机算法在 @@M@@(n+m)^{1+o(1)}@@ 时间内精确求出，成功概率至少 @@M@@2/3@@，且时间界在每条计算路径上成立；同一方法把 @@M@@f@@-因子判定与构造也做到近乎线性，将一般图精确匹配从 @@M@@O(m\sqrt n)@@ 推进到近乎线性。
匹配（matching）是组合优化的基石：Edmonds 1965 年用花（blossom）收缩给出多项式算法后，一般图上最快的构造性组合算法长期是 Micali–Vazirani 的 @@M@@O(m\sqrt n)@@；代数方法（Mucha–Sankowski、Harvey）达到 @@M@@O(n^\omega)@@，但只在稠密图上占优。近十余年，基于内点法的几乎线性精确流算法（Chen 等与 van den Brand 等）使二部图匹配获得 @@M@@(n+m)^{1+o(1)}@@ 解法。然而一般图的花结构对应奇集合约束（odd-set constraints），纯流与内点技术无法直接控制——这正是本文要跨越的最后一道障碍：把几乎线性精确求解从二部图推广到任意简单图。
定理（主定理）：存在单一均匀随机 word-RAM 算法，对任何 @@M@@n@@ 顶点、@@M@@m@@ 边的简单图（记 @@M@@p=n+m@@），在每条计算路径上于 @@M@@Cp^{1+\eta(p)}@@ 条指令内停机（@@M@@\eta@@ 非增且随 @@M@@p@@ 趋于 0），并以至少 @@M@@2/3@@ 的概率输出显式最大匹配。稀疏端 @@M@@m\le\kappa n@@ 给出 @@M@@n^{1+o(1)}@@，稠密端 @@M@@m=\Theta(n^2)@@ 给出 @@M@@n^{2+o(1)}@@。算法不承诺完美匹配；否定答案只可能来自带上限的随机搜索，且绝无假阳性——每个候选解在输出前都被显式验证。
推论（@@M@@f@@-因子）：给定每个顶点的度指令 @@M@@0\le f(v)\le\deg_G(v)@@，在相同的时间与概率保证下，可判定 @@M@@f@@-因子（@@M@@f@@-factor，即满足 @@M@@\deg_F(v)=f(v)@@ 的生成子图）是否存在并构造之；不存在时恒答 NO。
全文骨架是”归约—核心算法—均匀化”三段。先把基数问题二分：对阈值 @@M@@k@@，用 Beneš 型重排网络（rearrangeable network）把”大小为 @@M@@k@@ 的匹配”化成规模 @@M@@O(m+n\log n)@@ 的完美匹配实例——朴素地添加 @@M@@n-2k@@ 个万能顶点会引入二次多条边，网络把它压到近乎线性；再用 Dahlhaus–Karpinski 路径替换把最大度降到 3。于是核心化为次三次图（subcubic）上的完美匹配。核心状态把顶点分成”箱”（bins，带构造性 factor-critical 见证的奇块）与”行”（rows，沿原边指派到箱的单点），其余顶点显式配对；难点是结构改变后如何不全局扫描地修复这一表示。作者引入 @@M@@a+1@@ 层账本（ledger）：每行向邻箱共分 @@M@@L@@ 配额，箱 @@M@@d@@ 有残差底线 @@M@@c_jw_d@@（@@M@@w_d@@ 为箱权重），允许非负债务（debt）暂时违约。先看两端：最底层账本在稳态无债，直接给出每个非空箱集的严格 Hall 盈余（@@M@@Lh(X)\ge y^a(X)\ge w(X)>0@@），保证行—箱指派总可重排；最顶层账本带对数势 @@M@@\Phi=\sum\log x_e+\sum\log s_d@@，只要完美匹配存在且无结构动作可用，Berge 增广路径论证便给出改进环流方向，故不会假性停滞。再修中间：修复被实现为行—箱关联图上的精确流问题，只从债务相对其规模显著的箱出发探索；未探索的边界箱暂获乐观容量，吸收量足额即”锁定”与其规模成比例的份额，总流量受初始债务约束，物理扫描量随之受限；若请求底线不可行，则剥除箱集 @@M@@R@@（@@M@@Lh(R)<c_jw(R)@@），相邻两层底线恰差 1 的间隙使每个更粗账本债务净降至少 @@M@@w(R)@@——债务同时为局部探索与剥块买单。匹配目标与流测试共用”定价步”（priced-step）接口：寻找目标增益相对加权长度充分大的环流方向并走小的精确二进步，方向以森林中未展开的路径表示，免去逐步展开；该接口由冻结森林分解与预建路径副本构成的后端实现，承袭 Chen 等的几乎线性流框架与 Khandekar–Rao–Vazirani 的 cut-matching 技术。费用上，相位参数满足 @@M@@Lg_*=O(N)@@，几何重置周期 @@M@@b_j=B^{a-j}@@ 把各级投影费用加总为 @@M@@S^{1+O(1/a)+o_a(1)}@@。最后，每个固定参数分支满足此界；随机耗尽只产生可能错误的否定答案（分支 @@M@@t@@ 总错误 @@M@@\le 2^{-(t+20)}@@），确定性前提失败只挂起分支；Levin 式加权 dovetailing 把所有分支与一个确定的多项式回退分支编进一个程序，错误率求和 @@M@@<1/3@@，再以全输入上的上确界定义包络 @@M@@\eta@@，得到单一程序在每条路径上的时间界。
本文主结果暂无 Lean 形式化证明，请以社区核验为准；OpenAI 官方声明”未经形式化的结果可能有问题”。证明链长达十节、技术密度很高，但设计上处处保守：候选解一律显式验证（无假阳性），确定性 guard 只挂起分支而不出错，多项式回退分支保证停机。结果族 120 内的姊妹结果（@@M@@f@@-因子等）均由本文主定理经见证保真的显式归约推出，彼此支撑为一个整体；其中个别构件（如路由助手）的技术细节该文未在解读层面展开，此处从略。
问 1：证明里最关键、最脆弱的机制是什么？
答：@@M@@a+1@@ 层账本（ledger）与债务（debt）系统。匹配状态把顶点分成带 factor-critical 见证的奇块”箱”与指派到箱的单点”行”；两端各有一张底牌——最底层账本在稳态无债，给出每个非空箱集的严格 Hall 盈余（保证行—箱指派总可重排）；最顶层带对数势，只要完美匹配存在且无结构动作可用，Berge 增广论证就给出改进方向。中间层的修复全靠”债务同时为局部探索与剥块买单”：相邻账本底线恰差 1 的间隙，使剥除箱集后每个更粗账本的债务净降至少与剥除规模成比例。这条势能论证一旦有漏，整个近线性账就收不拢。
问 2：为什么二部图的近乎线性流方法不能直接搬过来？
答：一般图的花结构对应奇集合约束，纯流与内点法技术无法控制——这正是引言点名的”最后一道障碍”。本文的答案是用匹配状态与局部投影提供奇块控制：箱内构造性 factor-critical 见证允许”改变暴露点而不立即展开嵌套块”，把奇结构装进可局部修复的表示里。
问 3：与已有工作相比真正的新意是什么？
答：组合算法最快是 Micali–Vazirani 的 @@M@@O(m\sqrt n)@@；代数方法 @@M@@O(n^\omega)@@ 只在稠密端占优；近乎线性精确流（Chen 等、van den Brand 等）只拿下二部图。本文首次在一切密度范围内给出输入规模的近乎线性精确界（稠密端 @@M@@n^{2+o(1)}@@），并把 @@M@@f@@-因子一并做到近乎线性；此外”每条路径时间界 + 单一均匀程序”的表述比惯常的期望时间更严格。
问 4：为什么强调”单一均匀算法”与”每条路径”？这需要额外做什么？
答：对每个固定指数松弛分别给算法并不够——论文在均匀化一节用指令级 Levin 式 dovetailing 把所有固定参数分支与一个确定性多项式回退分支编进一个程序：分支 @@M@@t@@ 的总错误预算 @@M@@2^{-(t+20)}@@ 求和小于 @@M@@1/3@@，确定性前提失败只挂起分支，随机耗尽只产生可能错误的否定答案，再以全输入上确界定义包络 @@M@@\eta@@。每个候选解输出前显式验证，杜绝假阳性。
问 5：这种巨型工程最可能在哪里出错？
答：后端数据结构链最危险：静态路由稀疏器（cut-matching 加集中不等式）、冻结森林分解、路由快照层级与预建路径副本的”身份保持”——论文自陈替换受影响副本前要转移其保存的历史，这类实现级不变量是典型出错点；其次是从基数二分经 Beneš 网络与路径替换到次三次完美匹配的归约常数。本文未形式化，十节长链每一环都需复算。
问 6：谁会用到它？
答：需要大规模稀疏图上精确匹配与 @@M@@f@@-因子的人：组合优化库与图算法工程可直接受益；它也检验了几乎线性流框架（最小比率环流方向）在非流结构上的延展能力，为一般图上更多精确问题的近乎线性化提供模板。加权匹配是否也能近乎线性，论文未讨论。
总评
这是把一般图精确匹配从 @@M@@O(m\sqrt n)@@ 一举推进到近乎线性的里程碑式工程，设计上处处保守（显式验证、无假阳性、确定性回退）；最大风险是未经形式化的超长实现链——账本势能与后端不变量任何一处失守，定理即不成立。