demonstrate 的 blog

这里我们讨论如何使用 layering 的想法获得 feedback vertex set 的 2 近似。

feedback vertex set 给定一个无向图，每个顶点具有非负权值，求出最小权值的顶点子集使得去掉它们后剩余图恰好是无环图。

一个重要的概念是所谓图的 cyclomatic number，如果每条边给出一个 dimension，那么组成一个 cycle 的边均设为 1，其他设为 0，这样的向量张成 里面的子空间的维数称为 cyclomatic number，一般记为 ，可以证明 ，最后一项为联通分量的个数，我们可以对一个联通分量的情况容易给出证明。

我们可以发现，通过移掉某些顶点让图变成无环，这时对应的 cyclomatic number 会减少到 0，那么在依次去掉顶点的过程中，我们可以得到每个顶点对这个 cyclomatic number 的影响，记为 ，于是我们容易发现 。

事实上，对一个 minimal feedback vertex set 来说，，这意味着如果 weight function 是 cyclomatic weighted，那么对应的是 2-opt 解。为了说明前者，我们可利用之前的关系转换到证明关于度的不等式上来。这个 bound 可以用两方面的因素来分析，假定去掉 得到了 个联通无环分支，则这 部分含有边数为 。另外在 这个 cut 上的边数可以获得个 lower bound：，其中 是仅与 中一个顶点相连的联通分支数。利用 （即每个顶点产生的贡献的和正好是这种点个数和单与之相连联通分支的和）就可以证明了。

利用这个想法可以将 weight function 分解成为几个部分，每次都是选择 ，然后从每点权值去掉这个部分（），这样就会从图上得到一些权值为 0 的顶点，这样逐步下去就能获得 acyclic 的 graph，这些点对应的就是我们的近似解。类似前面的证明过程，可以得到这样是近似度为 2 的算法。

——————
And he divided himself against them, he and his servants, by night, and smote them, and pursued them to Hobah, which is on the left hand of Damascus.

这里我们讨论 k-center 与 parametric tuning 方法。k-center problem 简而言之就是找一个图的 k 个中心，所谓中心，自然要求其他点到其距离的最大值最小，那 k 个中心的话自然是其中最近的那个点的距离。这个问题是 NP-hard 的，且如果该 graph 不满足三角不等式，则不存在任意近似。为此，我们将此问题严格的限定在 metric graph 上。

k-center problem 给定一个完全 metric 无向图 ，每条边非负，求一个含有 k 个顶点的子集 ，定义 ，要求 能被最小化。

所谓 parameter tuning 是指为一个问题寻找到某个参数 ，给定一个参数 可以构造对应的问题实例 的简化版本 ，这个问题去掉了当 cost 时的部分。利用这个简化过的问题系列，可以估计最优值以及利用某个特定的参数获得近似解。

利用这个想法求解 k-center 的问题的观察在于，给定所有顶点，然后将所有的边按照权值从小到大排序，每加一条边就得到一个图，记这个序列为 ，随着边的增加顶点之间开始互相连接。这个时候对应的 dominating set 在不断缩小：所谓 dominating set 是指这样一个顶点集合的子集，任意一个非 dominating set 中的顶点都存在一条边连接到 dominating set 中的顶点；另外一个相关的概念是 independent set，也是一个顶点集的子集，其中任意两个顶点都没有边相连。最小的 dominating set 就是最大的 independent set。由于边增多导致某个时候最小 dominating set 正好含有 k 个顶点，这意味着此时加入的边（所有边 weight 最大的）正好是最优解，对应的 minimal dominating set 正好是要求的 k-center（根据三角不等式可以证明）。

实际操作的时候注意到 minimal dominating set 或者 maximal independent set 都是 NP-hard 问题，我们会转而利用下面的观察：对于图 ，令 是 的 independent set，则 。其中上标 2 表示原 graph 上如果两点存在一点将两者连接则也将其连接获得的新 graph。利用这个 graph 可以容易获得的一个 independent set：在每个 clique 中仅取一个顶点。

这样一个近似算法可以是：

• 先计算 ；
• 利用以上观察估计在哪个位置的 independent set 正好变成不大于 k；
• 将对应的 maximal independent set 作为 k-center 返回；

这个算法的近似度为 2：这是因为如果最优解对应 边，而 上对应的 k-center 必然是 dominating set，这样每条边的长度不会超过 2 倍最优值。

更强的结论是，对于任意 ，我们都不可能找到近似度为 的多项式时间的近似算法了。

该问题有一个推广是为每个顶点增加权值，要求选择的 k-center 的权值和小于给定 ，这只需要比较简单的修改原算法，另外增加选择 k-center 权值约束的部分就能获得近似度为 3 的算法。

——————
And there went out the king of Sodom, and the king of Gomorrah, and the king of Admah, and the king of Zeboiim, and the king of Bela (the same is Zoar;) and they joined battle with them in the vale of Siddim;

我们知道一个有向图上给定 source 和 sink 将两者分离对应的是所谓 (s,t)-cut 问题，其对偶问题是 max flow，两者存在多项式时间求解算法（见 BGL 的算法），这里讨论的是这个问题的推广，所谓 multiway cut 与 k-cut 问题。

multiway cut 给定顶点集的子集 ，称为 terminal set，要求给出一个边集的子集 ，使得去掉了该边集的图 terminal set 里面的顶点互不联通（不存在连接任两点的 path），这称为一个 multiway cut。并且在每条边上有所谓的 cost，要求选择的 cut 的边权值之和最小。

minimum k-cut 要求寻找一个边集的子集，使得去掉该子集后图变成含有 k 个 connected component 的图，这样的边集称为 k-cut，我们要求获得的 k-cut 的权值和最小。

两个问题，前者在 terminal set 元素个数大于 2 时是 NP-hard，后者在给定 时存在多项式时间的解，但如果是作为用户的输入可以变化，则也是 NP-hard，两个问题均存在 近似程度的解。

对 multiway cut 一个比较简单的想法就是对每个 terminal vertex 先找到一个能让它与别的顶点分离的 cut，这样把每个 terminal vertex 对应的 cut 里面 cost 最高的去掉，剩下的取并集，这样就能将这 个 terminal vertex 分离了。

问题是这个方法与最优 cut 相比差多少？其实很简单，我们假定最优的 cut 为 ，我们从里面选择一些子集，对第 个 terminal vertex 来说，我们选择能将其与其他 terminal vertex 分离的子集 ，这必然可行，这样我们可以把所有的 的 cost 加起来，这个 cost 不会超过两倍的最优解，这是因为每条边最多连接 2 个含有某个 terminal vertex 的 connected component，所以只会出现在两个子集中。然而我们选择的 min cut 的 cost 不比对应 大，所以所有 的并可以被 2 倍最优解 bound，然而我们扔掉了其中 cost 最大的一个 min cut，这最少是最优解的 。

对 minimum k-cut 来说，比较简单的想法是先用 min cut 将 connected component 分裂成两个，然后在更新后的 connected component 里面继续取 min cut，每次选择 cost 最低的 min cut。这个可以证明也有类似的 bound，但是证明比较繁琐。书上给出了另一种思路，即 Gomory-Hu tree。一个无向图的 Gomory tree 可以如下定义：

• 顶点集与原图一样；
• 由于是 tree，因此去掉任意一条边都能得到两个 connected component，而去掉的边对应就是两个 set 的 cut，这个 cut  cost（即这条边的 cost）正好是原来任意两个顶点的 min cut cost；

我们先不管如何创建这棵树，但是因为每条 Gomory-Hu tree 的边对应一个 min cut，那么我们去掉 条边就会对应 个 min cut，而将这些 min cut 并起来获得的也就是能将 graph 分离为 个 connected component 的 cut 了。这样导致了一个简单的算法，即计算 Gomory-Hu tree 然后选择边 cost 最低的 条对应的 cut 取并即可。证明的思路与前者基本类似。

事实上 Gomory-Hu tree 的建立过程与前面所说的分裂过程有一定的相似：

• 一开始我们将所有 connected component 当做整体来看，最后分裂出来的每个 connected component 都只有一个顶点；
• 这样我们先选择一个 connected component，其元素个数大于 1（保证可以分裂）；
• 将其他的 connected component 用 super node 替代，将选中的 component 里面的顶点完全解开，对应的边就是每个顶点互相的边 cost 以及与其他 component 在原 graph 中的的边的 cost，这样在这里面寻找 min cut，注意 component 之间的边的 cost 是连接两者所有边的 cost 的和；
• 选择 min cut 的时候，先任取两顶点，然后寻找 (s, t)-min cut 导致被选中的 component 分裂；分裂后引入两者之间的边 cost 为 min cut cost；

后面我们有时间会仔细研究一下 Gomory-Hu tree 其他的性质与应用。

—————–
Twelve years they served Chedorlaomer, and in the thirteenth year they rebelled.