树的凸重新着色改进近似算法

### 树的凸重新着色改进近似算法 在处理树的凸重新着色问题时，有多种衡量指标和先前的研究成果。下面将详细介绍相关概念、先前结果、我们的新成果以及具体的算法设计。 #### 背景与先前结果 在树的凸重新着色问题中，有几个重要的衡量指标。一种是所有字符的总和相关指标，另一种是系统发生数，它被定义为单个状态所诱导的最大连通分量数。Moran和Snir定义了从系统发生树到凸树的自然距离——重新着色距离。需要注意的是，简约分数和系统发生数并没有明确指定给定树到实际凸着色的距离。有些树虽然系统发生数和简约分数较大，但只需改变一个顶点的颜色就可以变成凸树；而有些系统发生数较小的树，却需要改变大量顶点的颜色才能变成凸树。 先前，Moran和Snir首次定义了最小凸重新着色问题。他们证明了即使在具有单位权重的字符串（有两个叶子的树）上，该问题也是NP难的。他们还提出了基于动态规划的算法来计算树的最优凸重新着色，该算法的运行时间为$O(n · n^*· ∆^{n^*+2})$，其中$n^*$是输入树中违反凸性的颜色数量，$∆$是树中顶点的最大度数。在后续论文中，他们又提出了基于局部比率技术的3 - 近似算法，以及针对字符串的2 - 近似算法。 #### 我们的新成果 我们获得了一个多项式时间的$(2 + ε)$ - 近似算法来解决最小凸重新着色问题。该算法依赖于一个精度参数$k ≥2$，并由两个阶段组成： 1. **第一阶段**：这是一个局部比率算法，我们通过操作权重，将原始的加权彩色树转换为我们称之为$k$ - 简单的加权彩色树。此阶段的近似比率为$2 + \frac{2}{k - 1}$，运行时间为$O(n^2)$。 2. **第二阶段**：使用动态规划来计算最优解。此阶段的运行时间为$O(n^2 + nk^22^k)$。例如，如果我们设置$k = \log n/2 + 1$，就可以得到一个$(2 + 4/ \log n)$ - 近似算法，其时间复杂度为$O(n^2)$。此外，我们用于计算最优凸重新着色（针对一般彩色树）的动态规划算法比之前已知的最佳算法更快，我们算法的运行时间（用$n^*$和$∆$表示）为$O(n^2 + n · n^*· ∆^{n^*})$。 #### 预备知识 ##### 部分着色 - 树$T$的部分着色是一个函数$C : V →C ∪\{∅\}$，其中$∅$表示没有颜色。如果$C(v) = ∅$，则认为顶点$v$未着色。树和部分着色的对$(T, C)$称为部分着色树。如果部分着色$C$可以扩展为（完全）凸着色，则称其为凸部分着色。 - **观察1**：凸部分着色可以在$O(n^2)$时间内完成。 - 我们考虑最小凸重新着色问题的扩展版本，其中输入和输出着色都可以是部分的。给定树$T = (V, E)$和树的部分着色$C$，我们的目标是计算凸部分重新着色$C'$。如果$C(u) \neq ∅$且$C'(u) \neq C(u)$，则称重新着色$C'$使顶点$u$脱色，即$C'$改变或移除了$u$的原始颜色。给定树顶点上的非负权重函数$w$，$C'$的重新着色距离是脱色顶点的总权重。 - **观察2**：最优凸部分重新着色的权重等于最优凸重新着色的权重。 - 对于部分着色树$(T, C)$，顶点集$X ⊆V$称为覆盖，如果存在凸部分重新着色$C'$，使得$X$是被$C'$脱色的顶点集。对于顶点集$U ⊆V$和权重函数$w$，定义$w(U) = \sum_{u∈U} w(u)$。因此，覆盖$X$的成本定义为$w(X)$，相应凸部分着色$C'$的重新着色距离为$w(C') = w(X)$。 ##### 最优解的形式 - 对于顶点子集$U ⊆V$，用$C(U)$表示用于着色$U$的颜色集，即$C(U) = \{c ∈C : C(u) = c 且 u ∈U\}$，注意$C(u)$不包括$∅$。对于树$T$的子树$T'$，用$C(T')$表示$T'$中使用的颜色集，即$C(T') = C(V (T'))$。 - 在彩色树$(T, C)$中，颜色块是诱导单色子树的最大顶点集。$c$ - 块是由颜色$c$着色的颜色块。如果$C$是凸着色，那么对于每种颜色$c$，只存在一个$c$ - 块。Moran和Snir将着色$C'$称为$C$的扩展重新着色，如果在$C'$的每个块中至少有一个顶点$v$未被重新着色，即$C'(v) = C(v)$。 - **观察3**：对于加权彩色树$(T, C, w)$，存在树的扩展最优凸重新着色。 - 由此可知，存在最优凸（部分）重新着色$C'$，它只使用$C$原本使用的颜色。接下来，我们将证明存在一种最优部分重新着色，其中每个顶点的颜色选择有限，并且着色为$∅$的顶点不在某些颜色$c$的两个$c$ - 块之间的路径上。 给定树$T$，用$T \ v$表示移除顶点$v$后得到的子树集。对于彩色树$(T, C)$，如果$T \ v$中至少有两个子树包含顶点$u$，使得$C(u) = c$，则称$v$分离$c$。顶点$v$相对于颜色$c \neq ∅$的分离数$sep_v(c)$定义为$T \ v$中包含顶点$u$且$C(u) = c$的子树数量。设$S(v)$是被$v$分离的颜色集，即$S(v) = \{c : sep_v(c) > 1\}$。定义$\Sigma_v = |S(v)|$和$\Pi_v = \prod_{c∈S(v)} sep_v(c)$（如果$\Sigma_v = 0$，则$\Pi_v = 1$）。 **定义1**：对于彩色树$(T, C)$，定义顶点$v$的颜色集$G(v) = S(v) ∪\{C(v), ∅\}$。部分重新着色$C'$称为良好的，如果： 1. 对于每个$v ∈V$，$C'(v) ∈G(v)$。 2. 如果$C'(v) = ∅$，则$v$相对于$C'$不分离任何颜色$c$。 **引理1**：对于加权彩色树$(T, C, w)$，存在良好的最优凸部分重新着色$C'$。 **证明**：设$C'$是最优凸重新着色，$X$是相应的覆盖。我们构造一个对应于相同覆盖$X$的良好最优部分重新着色$C''$。首先，对于每个$v \notin X$，设置$C''(v) = C(v)$。然后，对$X$中的顶点进行脱色。注意，相对于$C'$，每个$v ∈X$最多分离1种颜色（因为$X$是覆盖）。因此，对于每个分离颜色$c$的$v ∈X$，定义$C''(v) = C'(v) = c$；否则，定义$C''(v) = ∅$。显然，$C''$是良好的。而且，由于我们只改变了$X$中的顶点，所以$w(C'') = w(C')$。同时，$C''$是凸的，因为它可以扩展为$C'$。 **引理2**：设$v ∈V$是顶点，$T' ∈T \ v$是子树。如果$C'$是良好的部分重新着色，则$C'(T') ⊆C(T') ∪\{∅\}$。 **证明**：考虑$T'$中的顶点$u$。如果$C'(u) = C(u)$或$C'(u) = ∅$，则结论成立。否则，因为$C'(u) \neq C(u)$，可知$u ∈X$。由此可知$u$分离$C'(u)$，因此$C'(u) ∈C(T')$。 #### 动态规划算法 我们将输入树$T$视为有根树，通过选择任意根$s$来实现。设$v ∈V$是