树中的部分多割问题算法解析

### 树中的部分多割问题算法解析 在图论和算法设计领域，多割问题是一个重要的研究方向。本文将深入探讨树中的部分多割问题，介绍相关算法及其原理。 #### 1. 问题概述与主要结果 在树结构中，我们主要关注两个问题：奖赏收集多割问题和部分多割问题。对于奖赏收集多割问题，目标是找到一个边集，使得分离指定顶点对的边成本和未分离顶点对的惩罚之和最小。而部分多割问题则要求在树中分离至少 $t$ 对顶点，同时最小化边的总成本。 本文的主要结果包括： - 为奖赏收集多割问题设计了一个具有拉格朗日乘数保持（LMP）性质的 2 - 近似算法。 - 提出了一个 $( \frac{8}{3} + \epsilon )$ - 近似算法来解决部分多割问题，该算法的运行时间对于任何固定的 $\epsilon > 0$ 都是强多项式的。 - 为多割线性规划松弛问题提供了一个易于分析和实现的舍入算法。 #### 2. 奖赏收集多割问题 ##### 2.1 GVY 算法 多割问题可以用整数规划来表示： ```plaintext minimize ∑(e∈E) ce * de (MC) subject to ∑(e∈[si,ti]) de ≥ 1, ∀i = 1, ..., k (2.1) de ∈ {0, 1}, ∀e ∈ E (2.2) ``` 其中，$de$ 表示边 $e$ 是否被选中用于多割，约束 (2.1) 确保从每条路径 $[si, ti]$ 中至少选择一条边。该整数规划的线性规划松弛（MCf）是将整数约束 (2.2) 替换为 $de ≥ 0$。其对偶线性规划为： ```plaintext maximize ∑(i = 1 to k) fi subject to ∑(i:e∈[si,ti]) fi ≤ ce, ∀e ∈ E (2.3) fi ≥ 0, ∀i = 1, ..., k (2.4) ``` 对偶程序可以看作是最大多商品流问题，目标是最大化路由商品的总和。 GVY 算法遵循原始 - 对偶范式，构建可行的原始和对偶解，其成本彼此相差不超过 2 倍。该算法的步骤如下： ```plaintext Algorithm 1: The GVY Algorithm Root T at an arbitrary vertex and initialize D = ∅, f = 0. Phase 1: Constructing D and f while there is an unprocessed vertex do Pick the deepest such vertex, v. Without exceeding capacities, route maximal flow between pairs {si, ti} whose lowest common ancestor is v. Add all edges that became saturated to D. Phase 2: Eliminating redundant edges foreach e ∈ D, in reverse order of addition to D, do If D \ {e} is a multicut, delete e from D. return D, f. ``` 该算法生成的解具有两个重要的结构性质： - **性质 1**：仅选择饱和边。即对于每条边 $e$，如果 $e ∈ D$，则 $\sum_{i:e∈[si,ti]} fi = ce$。 - **性质 2**：如果在 $si$ 和 $ti$ 之间存在正流量，则从路径 $[si, ti]$ 中最多选择两条边。即对于每个 $1 ≤ i ≤ k$，如果 $fi > 0$，则 $|D ∩ [si, ti]| ≤ 2$。 ##### 2.2 奖赏收集算法 将奖赏收集多割问题转化为多割问题的方法是：对于每个 $1 ≤ i ≤ k$，向树 $T$ 中添加一个新的叶顶点 $t′_i$，并将其连接到 $ti$，新增边 $(ti, t′_i)$ 的成本为 $pi$。新的多割问题要求在得到的树 $T′$ 中分离对 $\{s1, t′_1\}, ..., \{sk, t′_k\}$。 通过这种转化，两个问题是等价的。设 $D ⊆ E$ 是树 $T$ 中奖赏收集多割问题的任何解，$N ⊆ \{1, ..., k\}$ 是未被 $D$ 分离的对的索引集。该解的成本是 $\sum_{e∈D} ce + \sum_{i∈N} pi$。我们可以通过选择边集 $D ∪ \{(ti, t′_i) : i ∈ N\}$ 轻松构造 $T′$ 中的相应多割，其成本相同。 此外，通过仔细检查 GVY 算法的第 2 阶段，我们发现了第三个结构性质： - **性质 3**：如果边 $(ti, t′_i)$ 在第 2 阶段后仍然存在，则路径 $[si, t′_i]$ 上没有选择其他边。即对于每个 $1 ≤ i ≤ k$，如果 $(ti, t′_i) ∈ D$，则 $D ∩ [si, ti] = ∅$。 基于这些性质，我们可以证明以下引理和定理： - **引理 1**：$\sum_{e∈DT} ce ≤ 2 \sum_{i∉N} fi$。 - **引理 2**：$\sum_{i∈N} pi = \sum_{i