Measure and Conquer

从参数计数到加权测度 ​

有界搜索树公理库有界搜索树Bounded search tree对局部障碍作完备分支，并让参数预算在每条分支严格下降。常用剩余顶点数或参数 $k$ 作为递归变量。Measure and Conquer 改用状态相关的非负测度

$$\mu (I)=\sum _{q\in Q}{w}_q{n}_q(I),$$

其中 $n_q(I)$ 是实例 $I$ 中类型 $q$ 的对象数，$w_q$ 是待选权重。类型可以是顶点度数、约束长度或局部剩余容量；测度不必为整数，也不必等于输入规模。

必须先证明三个条件：基例在有界测度内可多项式求解；每条安全约简不增加 $\mu$；每个递归分支都让 $\mu$ 严格下降。只把经验上“困难”的对象赋较大权重，不足以形成终止或时间证明。

分支向量与指数底 ​

若某规则产生 $b$ 个子实例，测度下降分别为 ${\mathrm{\Delta }}_1,\dots ,{\mathrm{\Delta }}_b>0$，递推为

$$T(\mu )\le \sum _{i=1}^{b}T(\mu -{\mathrm{\Delta }}_i)+\mathrm{poly}(n).$$

该规则的 branching number $\rho >1$ 是方程

$$\sum _{i=1}^b{\rho }^{-{\mathrm{\Delta }}_i}=1$$

的唯一正根，因而贡献 $O({\rho }^{\mu })$。完整算法的底数由所有可达规则中最大的 $\rho$ 决定，而不是挑一个好看的分支单独计算。

若最终能证明初始测度 $\mu (I_0)\le \gamma n$，总时间才可改写为 $O(({\rho }^{\gamma }{)}^n\mathrm{poly}(n))$。遗漏这一步会把按测度的界误当成按输入大小的界。

三次顶点分支的局部账本 ​

考虑最大独立集一类分支：对三次顶点 $v$，一支排除 $v$，另一支选入 $v$ 并删除闭邻域 $N[v]$。设三次顶点权重为 1、二次顶点权重为 $a\in [0,1]$，并先看三个邻居也都是三次且互不重合的局部状态。

排除 $v$ 会删除权重 1，并使三个邻居从三次降为二次，测度下降

$${\mathrm{\Delta }}_{out}=1+3(1-a).$$

选入 $v$ 删除 $v$ 及三个邻居，下降至少 ${\mathrm{\Delta }}_{in}=4$。于是这个局部规则给出

$$T(\mu )\le T(\mu -{\mathrm{\Delta }}_{out})+T(\mu -4).$$

这不是完整算法的最终界：邻居相邻、共享外部邻居或后续约简都会改变降幅；度 0、1、2 与其他分支也产生约束。例子的作用是展示“删除对象”和“对象改类型”都必须进入同一账本，不能只数被删顶点。

权重优化 ​

每条约简给出形如“新测度不大于旧测度”的线性不等式，每条分支给出依赖权重的降幅。固定候选底数 $r$ 后，条件

$$\sum _i{r}^{-{\mathrm{\Delta }}_i(w)}\le 1$$

通常是凸约束或可经变换数值求解；也可二分 $r$ 并检查权重可行性。线性规划公理库线性规划Linear programming · LP在线性等式和不等式约束下优化线性目标函数的问题。能处理部分线性化账本，但指数约束本身不应冒充普通 LP。

数值优化给出的权重只是猜想证书。发布证明时要给足够精度的有理权重或严格区间，并逐规则验证不等式；浮点求解器打印六位小数不构成严格上界。

Reduction rule 的证明责任 ​

若一个约简把三次顶点变为两个二次顶点，测度变化是 $2a-1$；要保证不增加，必须加入 $a\le 1/2$，或把约简产生的其他删除一并计算。权重非负可保证 $\mu$ 不会因生成对象而无界下降，但仍要证明终止状态与 $\mu$ 的关系。

某些局部状态在算法不变量下永远不可达，可以不纳入最大规则；这必须由结构引理证明。反过来，把可达坏状态漏掉会得到虚假的较小指数底。Measure 正确只证明搜索树大小，单节点约简、复制与解恢复的多项式工作仍需相乘。

与其他分析的边界 ​

递归树法公理库递归树法Recursion-tree method把递归式各层代价展开成树并对层和叶子求和的渐近分析方法。展开已知递推；Measure and Conquer 先设计递推所用的势尺，再展开。它与摊还势函数都使用权重，但这里衡量尚未解决实例并控制递归叶数，不是在操作序列间搬移成本。

若测度含参数 $k$ 与结构项，例如 $\mu =k+\alpha n_2$，最终可得到 $c^k\mathrm{poly}(n)$ 的参数化界；若只知 $\mu =O(n)$，得到的是精确指数算法。两者不能仅因都用非整数权重而混称 FPT。

参考资料

• Fedor Fomin, Fabrizio Grandoni, Dieter Kratsch, A Measure & Conquer Approach for the Analysis of Exact Algorithms, Journal of the ACM, 2009.
• Fedor Fomin, Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015.