近似算法（五）

daily blog

近似算法（五）

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

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

一个重要的概念是所谓图的 cyclomatic number，如果每条边给出一个 dimension，那么组成一个 cycle 的边均设为 1，其他设为 0，这样的向量张成 $\mathrm{GF}[2]^m, m = |E|$ 里面的子空间的维数称为 cyclomatic number，一般记为 $\mathrm{cyc} (G)$ ，可以证明 $\mathrm{cyc} (G) = |V| - |E| + \kappa (G)$ ，最后一项为联通分量的个数，我们可以对一个联通分量的情况容易给出证明。

我们可以发现，通过移掉某些顶点让图变成无环，这时对应的 cyclomatic number 会减少到 0，那么在依次去掉顶点的过程中，我们可以得到每个顶点对这个 cyclomatic number 的影响，记为 $\delta_{G_i} (v_i)$ ，于是我们容易发现 $\delta_G (v) = \deg (v) - (\kappa(G - v) - \kappa (G))$ 。

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

利用这个想法可以将 weight function 分解成为几个部分，每次都是选择 $c = \min_{v} \frac{w(v)}{\delta_G(v)}$ ，然后从每点权值去掉这个部分（ $c \delta_G(v)$ ），这样就会从图上得到一些权值为 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.

S	M	T	W	T	F	S
« Jan				Mar »
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29

demonstrate 的 blog

近似算法（五）

Like this:

Leave a Reply Cancel reply

争分夺秒

七嘴八舌

叽叽喳喳

本草纲目

穷搜猛索

friends

my online albums

my own blogs

长篇大论

无用操作

千夫已指

鸟言鸟语

机器请阅

Follow “demonstrate 的 blog”