问题描述

给定无重边,正边权,无向图 \(G = (V, E)\),求 \(G\) 的边权和最小的连通生成子图。

如果,每个点的度没有限制,那么就相当于求 \(G\) 的最小生成树,存在多项式时间最优算法。

但如果,每个点的度存在限制,这个问题就没有那么简单了。

不妨设第 \(i\) 个点的度为 \(deg(i)\),度限制为 \(d(i)\)

那么就有如下两个问题:

问题一:求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) \leq d(i)\)

问题二:求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) = d(i)\)

显然,对于问题二,如果所有的 \(d(i) = 2\),那么这个问题相当于 TSP 问题。

不幸的是,这两个问题都是 NP-hard 的,甚至目前没有找到多项式时间的近似算法。

但是,我们可以对 \(G\) 加一些限制条件,使得多项式时间的近似算法成为可能。

问题重述

给定无重边,正边权,无向完全图 \(G = (V, E)\),且边集满足三角形不等式。

问题一 (BMST):求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) \leq d(i)\)

问题二 (ConnFact):求 \(G\) 的边权和最小的连通生成子图,且 \(deg(i) = d(i)\)

问题一解决

\(V\)\(d(i) = 1\) 的点的集合,\(V_{\geq 2}\)\(d(i) \geq 2\) 的点的集合。称满足 \(deg(i) \leq d(i)\)\(G\) 的连通生成子图为 \(d\)-\(bounded\) \(tree\),其中,边权和最小的为 \(Tree_d\)

不妨设 \(|V_{\geq 2}| \geq 2\) ,否则可以通过分类讨论解决。

不妨设已知 \(Tree_d\) 的一条边 \(e_0\),两端点分别为 \(i_0\)\(j_0\)

\(G\) 的基础上,考虑最小费用流问题 \(MCF_{e_{0}}\)

  1. 汇点 \(r\)
  2. \(G\) 中删去边 \(e_0\)
  3. 对于 \(G\) 的所有边,容量为 \(1\),费用为边权。
  4. 对于所有 \(V_{\geq 2}\) 中的点 \(i\),点容量限制为 \(d_i - 1\)
  5. 对于所有 \(V_{\geq 2} \backslash\{ i_0, j_0 \}\) 中的点 \(i\),连一条边 \({(i, r)}\),容量为 \(d_i - 2\),费用为 \(0\)
  6. 对于 \(i_0\)\(j_0\),连一条边 \((i, r)\),容量为 \(d_i - 1\),费用为 \(0\)
  7. 对于所有 \(V_{=1}\),有流量 \(1\)

显然,\(Tree_d\) 删去边 \(e_0\) 是该费用流问题的一个解。

那么设 \(f^\ast\)\(MCF_{e_0}\) 的一个整数最优解,且满足 \(f^\ast\) 的支配图 \(S^\ast\) 所含点数最少。

那么有如下性质:

  1. \(w(S^\ast) \leq w(Tree_d)\)
  2. \(S^\ast\) 是森林。
  3. \(deg(i_0) \leq d(i_0) - 1\)\(deg(j_0) \leq d(j_0) - 1\)
  4. 对于每一个连通分量,若不包含点 \(i_0\)\(j_0\),则其一定包含 \(V_{\geq 2} \backslash\{ i_0, j_0 \}\) 中的点 \(i\),且 \(deg(i) \leq d_i - 2\)

\(i_0\) 为起点 \(j_0\) 为终点,将每一个连通分量中满足性质 4 的点通过类似 Metric TSP 问题的解法连接成路径 \(P\)

则有,\(w(T) \leq w(S^ast) + w(P) \leq w(Tree_d) + 2w(Tree_d) \leq 3w(Tree_d)\)

comments powered by Disqus