在 BRANCHING 中, 给出的分析时间复杂度的方法只能得到较为粗略的上界, 而 MEASURE AND CONQUER (简称为 M&C) 能够求出更紧的界.

设问题 的 instance 为 , 的 measure 为 .

M&C 更注重于 measure 的选择, 而不是创造 branching 和 reduction rules. 一个 measure 需要满足下面的条件:

• 设 是 通过 reduction 得到的子问题, 则 .
• 对任意instance , .
• input 的 measure 以 为上界.

更复杂的 measure 可以给时间复杂度提供更好的上界.

Maximum Independent Set

将以下面的算法为例来分析其复杂度. 基于 BRANCHING 中的各个引理, 下面的算法正确性显然, 其中 甚至 为树时多项式地求 的最大独立集是已知的事实.

上述算法中唯一的分支在 (3), 此时 branching vector 为 至少为 , 则 , 得到了 的时间复杂度, 但这只是一个最坏情况的上界.

求解树的最大独立集的多项式时间算法: 由于树的叶子结点度数总为 , 因此设 的叶子集合为 , 那么 , 可以 地求出树的最大独立集 (最坏情况是 为链的情形).

重新设计问题实例并使用M&C分析

首先已经知道 branching 的运行时间以多项式搜索树的叶子结点数为界, 而叶子节点完全由分支规则 (3) 产生, 因此 branch 是(在运行时间上) “costly” 的, reduction 是“cheap” 的也就是说度数大于等于3的点是 “costly” 的, 度数不超过2的的点是 “cheap” 的, 为其分别定义权重 和 .

因此定义图 (的 instance) 的 measure 为 表示 中度数至少为 3 的点的个数.

事实上是所有结点的权重和. 前述 instance 为 的情况相当于每个点的权重都为 .

分析和 有关的 branching vectors, 在下面也会把 称为 weight of instance.

"和 有关"的含义: 在前面以 的结点数 为问题的 instance, 分支后得到的子问题的 instance 为 , 在这里将 作为问题的 instance, 那么得到的子问题的 instance 为 , branching vector 的写法并不改变.

首先需要分析的是, branching rule (3) 是如何具体改变 的:

• 当丢弃 时, 对于 , 的权也会从 变为 , 因此 instance 的 measure 减少 , 至少为 .

• 当选择 时, 中的点的权重可能会改变. 很不幸的是如果 的存在度数为 2 的邻接点或者全部的邻接点度数都为 2, 那么选择 造成的删点有可能不会影响 的大小(只删去了权重为 的点), 这就意味着 branching vector 为 , , 并没有达到目的.

显然 并不是一个好的 measure, 需要重新设计.

问题在于度数为 2 的结点. 度数为 0 或 1 的结点可以被立刻由 reduction 移除掉, 度数至少为 3 的结点会进行 branch, 只有度数为 2 的结点留在图中, 因此应该有三种权重. 这很好修改, 令 表示结点度数为 2 的权重, 那么设计 measure 我们不关心 取何值时可以得到最好的结果 (通过更细致的分析和算力可以做到), 只需要知道改变 measure 可以得到一个更好的界即可, 这就是 M&C 的基本思想.

定理 1 当 时, 以 为 measure 进行 M&C 可以得到算法 mis3 的运行时间为 .

PROOF

M&C 的一般策略

就像上述例子一样, 在用 M&C 时设计问题实例的方法就是给问题中不同性质的成分赋不同的权, 后文中几乎所有的复杂度分析都是用这种方法.

Feedback Vertex Set

Feedback Vertex Set 简称为 FVS.

给定图 , 若 满足 不含有 cycle ( 为森林), 则称 为 FVS. FVS 问题目的是找到最小的 FVS, 即删去最少数目的点使原图成为树/森林.

FVS 的一个算法

前置定义与引理

称点集 是无环的如果 是森林, 那么最大无环集 与最小 FVS 是 的一个划分, 所以求最小 FVS 等价于求最大无环集.

朴素的 branching 思想

在算法的某个过程中, 假如得到了一个无环集 , 那么很自然地就会考虑 中的点能否添加到 中, 这便是一个分支规则, 对于 , 设 与 中的 相邻:

• 直接删去
• 选择 , 并删去 中的所有满足下面条件的 : 对于 , .

对于这种分支规则, 一个很好的 measure 是 , 在这个 maesure 下, ?

A more complicated one

现在定义对 的非平凡连通分量 的收缩(contract)操作 (非平凡的含义是树 的结点数至少为 2):

• 表示将 收缩为结点 , 保留与 相连的所有的边, 并删去缩点后与 有重边相连的结点.

对于无环集 定义 是 的所有以 为子集的最大无环集 (对于 , 且 是最大无环集). 置 , 那么 FVS 问题转化为求 的一个元素, 一个更一般的问题是对任意 找到 的一个元素.

收缩操作的目的是对图进行简化而不影响最大无环集, 且收缩操作必然可以将 变为独立集, 那么收缩之后问题就转化为给定独立集 求 包含 的最大无环集, 这会降低问题的求解难度.

现在需要论证最大无环集 收缩得到的独立集 是收缩后的图的最大无环集(如果给收缩定义一个逆操作“展开”, 也要论述 展开后得到的 是原图的最大无环集, 当然, 不关注展开之后的图是什么样子的, 毕竟收缩是丢失信息的), 表述为下面的引理:

Lemma 1 设 是无环集且 是 的非平凡连通分量, 令 是 做 操作后得到的图, 那么 PROOF 这个证明全部依托于反证法, 且证了一个方向之后另一个方向就是相似的方法.

当 时, 需要证明的是: 是 的最大无环集, 且 , 后面是显然的, 因为 .

首先若收缩后 与 有重边相连, 则 就含有环, 这意味着 , 于是收缩删除的点不会包括 中的点, 于是 是 的顶点集的子集.

证明 是无环的. 令 , 假设 有环 , 由于 是无环的, 那么 在环 中, 可以将 写成 的形式, 其中 与 相邻且 是 中的一条路径. 现在再展开 , 那么 中有 使得 与 相邻, 与 相邻, 且 之间有路径 , 这意味着在 中 是一个环, 这个环是 的子图, 显然与 的无环性相悖.

通过假设有环, 构造出一个环为 的子图以得到矛盾.

证明 是最大的. 假设 存在 使得 , 那么在 中 就是一个比 更大的无环集, 这与 的最大性质相悖.

因此当我们在求 的包含 的最大无环集时, 总可以假定 是独立集, 如若不然, 收缩即可.

下面的引理是后续分支算法的 branching rules 的主要依据.

Lemma 2 设 是 的一个独立集, 且 恰与 中的一个顶点 相邻, 则存在 使得 或者 中的两个顶点在 中.

PROOF 分类讨论一下即可, 首先假设 中没有点在 中(它们也不在 中), 则 , 且 中 , 那么 也是无环的同时是 的最大无环集, 这与 的最大性矛盾, 因此 中至少有一个点在 中, 有两种情况:

• 当 中有两个点在 中时, 引理成立;
• 当仅有一个 满足 时, 首先 , 那么 有环, 且 中 , 则 中所有的环都包括 , 这就意味着 是无环的, 它的大小等于 , 命题得证.

下面再给三个新定义.

• active vertex: 算法执行过程中的一个顶点 .

令 , 为 active vertex, 再令 , 由于 是独立集, 则 , 那么 中可能存在非平凡连通分量, 令 为 执行 之后得到的图.

• generalized neighbor: 如果在 中 则称 中的 为 的 generalized neighbor, 的含义如上.
• generalized degree: 在 中, 的 generalized neighbor 的个数称作 generalized degree, 记作 .

对于 generalized neighbor, 只有两种情况:

1: 若 不与 中除 外的任何点相邻, 则 仍然是独立集, 那么无需执行收缩操作(或者说执行收缩操作不改变 ), 的 generalized neighbor 就是它的 neighbor.

2: 若 与 相邻, 则 中存在非平凡连通分量 , 将 收缩为 之后, , 也就是说 为 的 generalized neighbor 的集合.

这里 也可以是多个点, 也就是 中的非平凡连通分量是形如 的图.

详细算法流程

设 , 给出下面的 branch 算法, 分为 preprocessing 和 main procedure.

Preprocessing

若 不连通, 设其连通分量分别为 则 若 不是独立集, 则对其非平凡连通分量 做 操作得到 , 满足 如果 中存在 active vertex 则 将为 active vertex.

Main Procedure

预处理部分保证了下面的 是连通的且 是 的独立集.

若 , 显然 , .

若 :

• . 则 中不存在环, 于是 .

• , 选择 满足 , 在 上做分支, 要么选 , 要么不选 , 则

如果 中没有 active vertex, 则任意选定 active vertex , 后文中的 都指本步骤选择的 active vertex.

对于 , 若

• , 则直接把 加到 中即 ;

• , 要么选 要么丢掉 ,

• , 设 的 generalized neighbor 为 , 由 Lemma 2 可得 如果选择 导致了环的存在, 直接忽略掉该分支即可.

最 trivial 的分支规则 的正确性显然, 上面算法中的4的第一三条的正确性需要再说明一下:

执行 操作后, 在 中 将恰与 中的一个顶点 相邻, 此时在 中, 对于 , 要么 , 要么 中的两个点在 中, 而 本身是由 中的一些点和 收缩而来, 的 neighbor 是 的generalize neighbor, 那么在 中以及 , 一定有 或者 , 这分别对应了 和 的情形.

Theorem 1 FVS 问题可以在 的时间内解决.

PROOF 设计 measure 为 其中 为 active vertex. 这实际上是 中的点权为 , 中的点的点权为 , 剩余的点的点权为 , 且 , 若在 measure 为 的条件下得到了复杂度上界为 , 那么可以得到最终的运行时间为 . 接下来考虑三个分支规则的 branching vector.

对于 2 的第 2条, , 那么所有的点的权重为 , 若直接丢弃 , 总权重减少 , 若选择 , 将成为 active vertex, 那么 的权重将变为 , 中的两个顶点的权重将减为 , 总权减少了 , 因此 branching vector 为 .

对于 4 的第 2 条,

对于 4 的第 3 条, , 其中 表示 的 generalized

neighbor 中的权重为 的点的个数.

通过搜索得到 , 则 .

In undirected graphs of maximum degree three, the feedback vertex set problem can be solved in polynomial time, by transforming it into an instance of the matroid parity problem for linear matroids.

Dominating Set & Set Cover

对于 MSC 的 set cover , 会说 是 的集合覆盖. 令 , 将求解 MDS 转化为求解 MSC, 即 是 的支配集当且仅当 是 的集合覆盖.

定义 的频率为 , 即 中含有 的集合 的个数.

两个比较显然的用来 reduction 的引理.

Lemma 1 若 满足 , 则存在一个不包含 的 MSC.

Lemma 2 若某个 满足仅有唯一的 使得 , 那么所有的 set cover 都包含 .

定义 , 即将 中的每个集合 删去 中的元素.

Algorithm

1: 若 则

2: 若存在 , 则

3: 若某个 满足 且 , 则 .

4: 选择 中基数最大的集合 , 若 , 则在多项式时间内求解 ; 若 , 则 要么在 MSC 中, 要么不在, 有分支 定义 , 对于 MSC 的实例 , 定义其 measure 为 , 那么分支规则的 branching factor 为 , 因为选择 之后 中的元素至少减少 3 个, 于是用该算法求解 MDS 的复杂度为 .

事实上, 设计一个好的 measure 后, 对于同一个算法, 可以得到更好的复杂度上界为 .

借助 M&C 分析

注意到前述的分支规则是不断删掉 中的集合, 并且每次是选择基数最大的集合, 这样的选择是合理的, 因为这样可以将 中尽可能多的元素的频率减少 , 当频率减少到 时便可以使用 reduction 而无需再分支.

除此之外移除 中频率较高的元素可以让 中更多的元素的基数减少 , 当 的基数减少到 的时候, 很容易就能判断是否要选择 而无需再分支.

当选择一个集合 时, 中所有的元素的频率都会减少至 .

因此显然可以赋予不同频率的元素 和不同基数的集合 不同的权重, 且偏好出现频率高的元素和基数大的集合, 于是令 , ,

设计 measure 其中 表示权重, 且 都是递增的(这符合前面分析的直觉), 且 .

为了便于分析具体的复杂度上界, 对权重做如下的赋值:

• , 这是因为对于频率为 1 的元素或者是基数为 1 的子集无需再做分支
• .

并假定 , 其中 为 的差分, 这个不等式衡量了序列 的增长速度, 是逐渐减缓的, 这个假定是基于经验得到的, 同时它也确实能简化分析.

求两个分支的 .

删去 的分支:

分别考虑频率和基数的减少量. 删去 使基数为 的集合数目减少了 1, 对 measure 的减少为 ; 删去 使 中每个元素 的频率都从 减少到了 , 那么 measure 总共减少了 注意假定中 , 因此 , 于是令 , 表示 中频率为 的元素的个数, 那么有 个元素的频率将从 降为 , 于是 然而仅仅考虑这两部分还不够, 删去 之后会导致出现频率为 的元素, 那么可以直接进行 reduction, 问题的 size 还会继续缩小, 于是还要再考虑 的值.

设 表示不等于 且至少含有一个 中的频率为 2 的元素的集合, 删去 之后, 就必然要选 , 设 , 表示 中的 中的频率为 2 的元素的个数, 选择 将问题的 size 减少了 , 同时

Lower Bound Analysis

分析下界的一般方法是构造一个实例, 该实例的复杂度作为整个问题最坏情况复杂度的下界.

最大独立集: 构造 .

.

MDS: 构造 , 是若干三角形的并, 如下所示

.

总结: 使用 M&C 分析时间复杂度上界的一般步骤

Exercise