顶点覆盖数据规约规则的边际效力：以逐规则消融实验测定各规则对核大小的独立贡献及其结构预测因子

1 · 研究问题

在最小顶点覆盖（minimum vertex cover）的参数化预处理中，六条经典数据规约规则（度-1 规则、度-2 折叠、支配规则、线性规划/Nemhauser–Trotter 约简、皇冠约简 crown reduction、unconfined 规则）各自对最终核（kernel）大小的边际贡献是多少——即在保留其他全部规则的前提下单独移除某一条，核的顶点数与边数增加多少？这些边际贡献能否由可先验计算的图结构量（度分布、局部聚类系数、二部性程度）预测，从而给出"对某类图该先跑哪几条规则"的可操作判据？

2 · 研究背景与空白

技术背景。 核化（kernelization）是参数化算法的核心技术：在多项式时间内把实例 (G, k) 化简为等价实例 (G′, k′)，其中 G′ 的规模仅由 k′ 有界，且 G 有大小 ≤ k 的顶点覆盖当且仅当 G′ 有大小 ≤ k′ 的顶点覆盖。顶点覆盖是核化在实践中效果最好的少数问题之一。各条规则的机制不同：度-1 规则直接把度为 1 的顶点的邻居放进覆盖；LP/Nemhauser–Trotter 约简解一个可用二部图最大匹配求解的线性松弛，把取值为 1 和 0 的顶点分别确定下来；皇冠约简寻找一种特殊的二部结构（"皇冠"）并整体消去。关键的资源特性是：全部规约规则都是多项式时间的，且本课题完全不需要求解 NP 难的顶点覆盖本身——交付物是核的大小，不是最优解。这使课题彻底绕开了算力墙，也绕开了"让学生去挑战已知难题"的陷阱：我们测量的是预处理的效力，而不是试图打败 PACE 冠军求解器。

已有工作到哪一步。 Abu-Khzam 等的《Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments》系统实验了多条规则，给出的具体建议是：皇冠约简在实践中比线性规划快得多，有时化简效果同样好（尽管其最坏情况核大小界更差），最佳流程似乎是先做预处理与高度数方法，再做皇冠约简。PACE 2019 顶点覆盖赛道的冠军求解器 WeGotYouCovered 采用了组合策略：激进的核化 + 局部搜索 + 分支约简 + 最先进的分支定界求解器，并公布了完整实现与实例集。另有针对偏好连接模型的核大小分析、顶点覆盖结构参数化的理论工作，以及基于快速证据验证的紧凑整数规划设计（arXiv:2509.25445）等新近方向。

空白在于：现有实验工作报告的是"规则组合的总效果"与"先跑哪个更快"的经验流程，而没有做过逐规则的消融实验——因此没人知道在现代规则集里，哪几条规则实际上是冗余的（它们的效果已被其他规则完全覆盖），也没人给出"边际贡献取决于图的什么性质"的预测。这个空白属于"评价维度转换 + 问题方向转换"，可靠性高：实例与实现全部公开、算力门槛极低、正负结论都成立（若某条规则边际贡献接近零，那是一条对求解器工程有直接价值的简化建议；若每条都不可或缺，则现有规则集被证明是精简的）。

3 · 可检验假设

• H1：在同时保留 LP/Nemhauser–Trotter 约简的规则集中，移除皇冠约简后核顶点数的中位增幅 ≤ 5%；而移除 LP 约简后的中位增幅 ≥ 30%。即"皇冠约简的化简效力在有 LP 约简时基本被覆盖，其价值主要在速度而非效力"。若移除皇冠后增幅 > 15%，H1 被否证，说明两条规则捕获的是不同结构。
• H2：各规则的边际贡献可由图结构量预测：度-1/度-2 规则的贡献与"度 ≤ 2 顶点的比例"的 Spearman ρ ≥ 0.7；皇冠约简的贡献与图的局部二部性度量（例如最大二部子图的边占比估计或三角形密度的倒数）ρ ≥ 0.5。若两者都不成立，说明边际贡献由更全局的结构决定，这本身是对"规则可按图类型选择"这一直觉的否证。

4 · 量化验收标准

1. 方法学校验（硬门槛）：用自建核化管线，在文献与 PACE 使用过的公共实例上重现已发表的核大小数字，相对偏差 ≤ 5%（核大小是确定性量，不存在硬件差异，因此判据可以严格；若某规则实现有多种变体导致差异，须逐一列出变体并说明所选版本）。同时要求：在至少 3 个已发表实例上，本管线得到的规则应用顺序建议与 Abu-Khzam 等的结论方向一致。这一步不过关，后续全部结论无效。
2. 正确性门槛（第二道硬门槛）：核化必须保持解等价。判据：对 ≥ 200 个顶点数 ≤ 30 的随机小图，用暴力枚举求出精确最小顶点覆盖，验证 VC(G) = VC(G′) + （规约过程中确定进入覆盖的顶点数），要求 100% 通过，任何一例失败即视为实现有误。这是消融实验唯一能排除"核变小是因为规约写错了"的证据，必须写进正文。
3. 消融设计写死：采用"留一移除"（leave-one-out）与"逐一加入"（greedy add-one）双向消融，两套结果都报。规约过程必须迭代至不动点（fixpoint），且规则应用顺序在同一实验内固定并公开；额外做一次顺序随机化实验（≥ 10 个随机顺序）量化顺序对核大小的影响幅度——若顺序效应大于规则效应，全部消融结论无效，必须在正文明确报告这一检查。
4. 统计口径：核缩减比例是有界比值，报中位数与 IQR，不报均值；跨实例比较用配对 Wilcoxon 符号秩检验（配对单位为实例）；相关性给自助法（≥ 2000 次重采样）95% 置信区间与散点图，不报单一 R²。
5. 样本量：实例 ≥ 60 个，覆盖至少 4 类（PACE 2019 顶点覆盖赛道公开实例、DIMACS 团/独立集基准的补图、SNAP 真实网络、随机与幂律合成图）；顶点数跨 3 个数量级；每类下限 10 个。
6. 运行成本单列：报告每条规则的单次应用耗时与在整个不动点迭代中的累计耗时（中位数与 IQR，≥ 5 次重复，固定频率），因为文献中"皇冠约简比 LP 快得多"这一结论正是速度侧的，必须在同一口径下独立复核。
7. 可复现性：全部规约规则实现、实例清单与下载脚本、原始核大小与计时 CSV、统计脚本开源；一键重跑脚本；随机种子写死。

5 · 数据与工具

用途	来源 / 工具
实例集	PACE 2019 挑战赛顶点覆盖赛道公开实例（pacechallenge.org 归档，含公开与隐藏测试集的公开部分）；DIMACS 团问题基准（可取补图转为顶点覆盖实例）；SNAP 真实网络；自建随机图与幂律图生成器。外部实例仅用于校验与对比，不计入本项目的数据贡献
参考求解器/核化器	WeGotYouCovered（PACE 2019 冠军，开源）或 KaMIS 的规约模块，作为核大小的独立交叉校验参照。仅用于校验与对比，不计入本项目贡献
规则实现	自行实现六条规则（Python + NumPy 原型 → C++ 或 Numba 加速版本；每条 50–150 行）。LP/Nemhauser–Trotter 约简可归约为二部图最大匹配，用 NetworkX 的 hopcroft_karp_matching 或 SciPy 的 maximum_bipartite_matching 实现（须核实 SciPy 版本的接口与复杂度）；皇冠约简同样依赖最大匹配
精确求解（仅用于正确性门槛的小图）	自行实现的暴力枚举（n ≤ 30）；可选用 PuLP + CBC 或 Google OR-Tools 的整数规划做二次确认（仅在 n ≤ 200 的小图上使用，不用于主分析）
结构量计算	NetworkX / igraph（度分布、聚类系数、三角形计数、k-core）
统计与作图	Python + SciPy + Matplotlib
算力	纯 CPU。全部规约规则为多项式时间：最大匹配 O(m√n)，n = 10⁶ / m = 10⁷ 的实例在数分钟内可完成（须实测标定）。内存以邻接表为主，16 GB 可覆盖 PACE 公开实例的绝大部分。超出范围：求解最小顶点覆盖的最优解（NP 难）不在本课题范围内，正文必须明确声明本项目不求解、不与求解器竞速

6 · 方法路径

1. 装环境，下载 PACE 与 DIMACS 实例，跑通参考核化器（WeGotYouCovered 或 KaMIS）在几个实例上的输出，作为后续对照的锚点；实测规约的运行成本标度。
2. 逐条实现六条规约规则，每条实现后立刻通过 n ≤ 30 的暴力等价性检验（验收第 2 条），不通过不进入下一条。
3. 核实工具能力边界：SciPy/NetworkX 的最大匹配实现在百万边规模上是否可用（若不可用，须自行实现 Hopcroft–Karp，若需自行实现，须用制造样例与 NetworkX 小图结果双重验证，这本身可作为方法学贡献写入）；确认参考核化器公布的核大小定义与本项目一致（是否把已确定顶点计入）。
4. 完成方法学校验（验收第 1 条），归档差异分析。
5. 组建实例样本（≥ 60 个、4 类），计算全部结构量协变量。
6. 执行双向消融扫描（留一移除 + 逐一加入）与顺序随机化检查，记录核顶点数、核边数、每规则耗时；输出边际贡献分布。
7. 分析与独立交叉校验：（a）出边际贡献表、配对 Wilcoxon 检验、结构量相关性与置信区间；（b）用参考核化器对同一批实例产出核大小，验证本管线的全规则核与之在同一量级（差异须能由规则集差异解释并逐条说明）；（c）在合成图上做受控实验——固定顶点数与边数、只扫描"度 ≤ 2 顶点比例"，检验 H2 的预测关系是否在受控条件下成立。

7 · 新颖性边界

本课题不声称：不提出新的规约规则，不改进任何核大小的理论上界，不求解最小顶点覆盖，不与 PACE 求解器比赛求解速度或解质量，不声称任何新的参数化复杂度结果。PACE 实例、DIMACS 基准、WeGotYouCovered/KaMIS 与全部六条规则均为他人工作，标注为对照基准，不计入本项目贡献。

已有工作完成了什么：Abu-Khzam 等给出了多条规则的实验比较与流程建议（皇冠约简比线性规划快得多、有时化简同样好、建议先预处理与高度数方法再做皇冠约简）；PACE 2019 冠军 WeGotYouCovered 展示了激进核化 + 局部搜索 + 分支约简 + 分支定界的组合在竞赛实例上的效力；理论侧有偏好连接模型下的核大小分析与结构参数化结果。这些结论本项目引用而不重复声称。

本项目的贡献：首次以逐规则消融的方式给出各规约规则的边际核缩减贡献分布，并检验该贡献能否由可先验计算的图结构量预测。主结论是这份"边际贡献表 + 冗余规则清单 + 结构预测判据"，不是任何新规则或新求解器。

为什么有价值：核化的实现成本主要花在规则数量上，而现有建议只告诉工程师"都跑一遍、按某个顺序"。若某条规则在现代规则集中边际贡献接近零，实现者可以直接省掉它；若边际贡献可由图性质预测，则可以做成自适应的规则选择。两者都能直接落到求解器工程里。

风险提示：规则之间存在强交互（A 的贡献取决于 B 是否在场），因此"留一移除"的边际贡献不是可加分解。正文必须明确这一点，并用"逐一加入"的第二套结果作为交互强度的度量；若两套结果差异巨大，"规则贡献高度依赖组合、不存在稳定的边际排序"同样是有效且重要的结论。

8 · 决策门槛（go / no-go）

• 第 6 周：正确性门槛。若任何一条规则无法通过 n ≤ 30 的暴力等价性检验，降级路径 A：把该规则移出规则集并在正文声明，规则数下限为 4 条（度-1、度-2 折叠、LP 约简、支配规则——这四条实现最简单、正确性最易验证）。消融框架完全保留。
• 第 10 周：最大匹配的规模可行性必须核实完毕——这是需要提前确认而非边做边发现的事项。若 SciPy/NetworKit 的实现无法处理百万边实例且自行实现超时，降级路径 B：把实例规模上界下调至 m ≤ 10⁶，并把实例数量从 60 补到 80 以维持统计功效。主结论不变（边际贡献是相对量，不依赖绝对规模）。
• 第 14 周：方法学校验硬门槛。若核大小与文献偏差 > 5%，先排查规则变体定义、不动点迭代是否跑满、核大小是否把已确定顶点计入三项；第 17 周仍不过关则降级路径 C：放弃与外部文献的绝对核大小对照，改用参考核化器（WeGotYouCovered/KaMIS）在本机上的实际输出作为对照锚点，硬门槛替换为"本管线全规则核与参考核化器核的顶点数比值落在 [0.9, 1.3] 且差异可逐规则解释"。
• 第 22 周：顺序随机化检查必须完成。若顺序效应的幅度超过规则效应（即换个顺序核大小的变化比移除一条规则还大），降级路径 D：把课题重心正式转为"规约规则应用顺序对核大小与耗时的影响"这一主题——这依然是本领域缺少系统数据的方向，消融框架、实例集、统计口径全部复用，主结论框架保留。
• 第 32 周：消融扫描完成且 H1 有明确判定。若进度不足，降级路径 E：实例类别从 4 类减为 3 类（保留 PACE + SNAP + 合成），每类实例数不低于 15。
• 预算裁剪顺序：结构量种类 → 实例类别数（下限 3）→ 规则数（下限 4）→ （绝不裁剪）正确性门槛与顺序随机化检查。
• 选择前提：适合喜欢图论证明与算法细节、能耐心把六条规则各自的边界情形写对的学生。本路线的最大隐患是规则实现的正确性，正确性门槛必须严格执行，不可为赶进度跳过。

---