参数化的并集与无着色数

《Information and Computation》：Parameterized reunion with achromatic number

　　

摘要 在本文中，我们研究全色数问题。给定一个图 $G$ 和一个整数 $k$，任务是判断是否存在 $G$ 的一个正规着色，其中使用至少 $k$ 种颜色，并且每一对不同颜色的颜色对出现在某条边的两个端点上。早在参数化复杂度的正式发展之前，就已经确定该问题是固定参数可解（FPT）的。事实上，Farber、Hahn、Hell 和 Miller [JCTB, 1986] 设计了一个运行时间为 $\mathcal{O}(f(k) \cdot |E(G)|)$ 的算法。虽然 $f(k)$ 的确切形式并未明确给出，但它看起来至少是关于 $k$ 的双重指数的。在我们的工作中，我们首先提出了一个关于 $k$ 有显式依赖性的算法，然后引入了另一个以图的顶点覆盖数作为参数的算法。更正式地说，我们证明了以下内容：• 全色数问题可在 $2^{\mathcal{O}(k^5)} + \mathcal{O}(|E(G)|)$ 时间内求解。• 当输入限制为 $d$-退化图时，全色数问题具有多项式核。我们还给出了在树上更高效的核。• 我们研究了该问题关于顶点覆盖的参数化复杂度，并证明它接受一个运行时间为 $2^{\mathcal{O}(\ell^2)} \cdot n^{\mathcal{O}(1)}$ 的 FPT 算法，其中 $\ell$ 是顶点覆盖的大小。我们通过证明一个假设 ETH 下 $2^{o(\ell)} \cdot n^{\mathcal{O}(1)}$ 的下界来补充我们的结果。引言 在本文中，我们重新审视全色数问题，该问题早在参数化复杂度的概念被确立之前就被证明接受固定参数可解（FPT）算法。图的一个正规着色是一种将颜色分配给顶点的方案，使得每条边的两个端点不被分配相同的颜色。图的一个完全着色是一种正规着色，使得对于任何一对不同的颜色，都存在一对相邻的顶点被分配了这些颜色。图 $G$ 的全色数，记为 $\psi(G)$，是在 $G$ 的完全着色中可使用的最大颜色数。在本文中，我们研究以下问题。输入：一个有 $n$ 个顶点和 $m$ 条边的图 $G$，以及一个整数 $k$。问题：$\psi(G) \geq k$ 是否成立？全色数问题的计算复杂度最早由 Yannakakis 和 Gavril 在 1980 年研究，他们证明了该问题是 NP 完全的 [2, 推论 2]。作者还观察到，与经典的全色数问题不同（该问题即使在 $k=3$ 时已知就是 NP 完全的，即输入图是否能用 3 种颜色正规着色），全色数问题对于固定的 $k$ 值不太可能是 NP 完全的。为此，他们证明了对于图 $G$，$\psi(G) \geq k$ 当且仅当存在一个大小至多为 $\binom{k}{2}$ 的子集 $W \subseteq V(G)$，使得 $\psi(G[W]) \geq k$。这立即给出了一个运行时间为 $\mathcal{O}(n^k 2)$ 的算法。在现代参数化复杂度（PC）术语中，这是全色数问题的一个 XP 算法。因此，一个自然的问题是是否存在一个运行时间为 $f(k) \cdot n^{\mathcal{O}(1)}$ 的算法，即该问题是否接受 FPT 算法。一个自然的问题是是否存在一个对每个固定的 $k$ 都有效的统一多项式时间算法。即，我们是否有一个 $n^{\mathcal{O}(1)}$ 时间的算法，其中 $\mathcal{O}(1)$ 不依赖于 $k$。（前 PC 时代）用现代术语来说，是否存在一个运行时间为 $f(k) \cdot n^{\mathcal{O}(1)}$ 的算法，即该问题是否接受 FPT 算法。（后 PC 时代）1986 年，Farber、Hahn、Hell 和 Miller [3] 为全色数问题设计了一个"线性时间算法"。即，一个运行时间为 $\mathcal{O}(m)$ 的算法；实际上是一个运行时间为 $f(k) \cdot m$ 的算法。这确立了全色数问题的参数化复杂度。运行时间中 $f(k)$ 的确切值未被给出，并且它看起来至少是关于 $k$ 的双重指数的。由于证明的非构造性本质，$f(k)$ 的精确封闭形式被省略了，但可以从 Hell 和 Miller [4] 的工作中得出一个上界，他们建立了此类不可约图大小的双重指数极限，从而得到一个一般的上界 $f(k) \leq e e k^2$。由于该算法最终依赖于对一个大小 $N \leq k \cdot f(k)$ 的顶点上的约化核图进行穷举搜索，我们可以通过搜索部分完全 $k$-着色来确定其全色数是否至少为 $k$。对于 $k \geq 2$，每个颜色对的一条见证边的端点构成一个大小至多为 $s = 2\binom{k}{2} = k(k-1)$ 的顶点集。枚举这些顶点集及其颜色分配给出了上界 $\left(\sum_{i=0}^{\min\{s, N\}} \binom{N}{i}\right) \cdot k^{\mathcal{O}(k^2)} \leq (N+1) \cdot k(k-1) \cdot k^{\mathcal{O}(k^2)}$。将上述上界 $N \leq k \cdot e e k^2$ 代入，得到一个穷举搜索上界 $(k \cdot e e k^2 + 1) \cdot k(k-1) \cdot k^{\mathcal{O}(k^2)}$。因此，这个关于 $k$ 的依赖性的上界仍然是双重指数的。这些结果是我们研究的起点。我们的目标是设计一个关于 $k$ 有显式依赖性的算法，由一个增长尽可能慢的函数来实现。此外，我们还探索了以结构参数为参数的该问题。虽然全色数 $\psi(G)$ 通常因其理论性质和计算复杂度而受到研究，但它在需要最大完全互连性的领域中有重要的实际应用。在网络设计和分布式计算中，全色数被用于将大型网络划分为最大数量的不同集群，使得每个集群都与所有其他集群保持直接通信链路 [5]。相关工作。关于全色数与其他图变体（如顶点覆盖数和独立数）之间的界已被研究 [6]、[7]。伪全色数问题是一个相关的问题，于 1969 年被提出 [8]，并已被广泛研究 [9]、[10]、[11]。伪全色数问题或图完全划分问题检查一个无向图是否可以被划分为 $k$ 个类，使得每对类之间由一条边连接。与全色数问题不同，我们不要求这些类是独立集。即使对于树的一个族，伪全色数也可能严格大于全色数 [12]。Halldórsson 等人 [13] 研究了该问题的近似复杂度，并获得了本质紧密的界。他们提出了一个随机多项式时间算法，实现了 $\Omega(1/\sqrt{\log n})$ 的近似比，该算法也可以去随机化。该问题有一个 $\mathcal{O}(k^2)$ 的核，这也证明了它在以解大小为参数时是 FPT 的 [14]。另一个相关的问题是和谐着色，其目标是找到图的一个正规着色，使得每对颜色最多一起出现在一条边上 [15]。已知该问题在树、区间图和置换图上都是 NP 难的 [16]、[17]、[18]。Georges 在路径、环、完全图及完全二部图上研究了该问题 [19]。Kolay 等人 [20] 从 FPT 角度研究了该问题，并证明了它在以解大小和图的顶点覆盖数为参数时都是 FPT 的。他们还给出了一个在分裂图上的精确指数时间算法。我们的第一个主要结果是以下关于全色数问题的 FPT 算法。定理 1 以解大小 $k$ 为参数的全色数问题可在 $2^{\mathcal{O}(k^5)} + \mathcal{O}(m)$ 时间内求解。定理 1 证明的思路受到全色数优化变体近似算法领域结果的启发。Kortsarz 和 Krauthgamer 给出了一个算法，对一般图将全色数的近似比达到了 $\mathcal{O}(n \cdot \log\log n / \log n)$ [21]。该算法又受到了 Máté [22] 关于不可约图上全色数的早期组合工作的启发。我们的参数化算法建立在这个近似算法之上，并在多处融入了新的思想和概念，将其转化为一个 FPT 算法。我们顺便提一下，Kortsarz 和 Krauthgamer [21] 证明了除非 P=NP，否则对于每个固定的 $\varepsilon > 0$ 都不存在 $(2-\varepsilon)$-近似算法。下一个自然的问题是，该问题是否接受多项式核。即，我们能否在多项式时间内将给定实例替换为大小关于 $k$ 为多项式级别的等价实例？我们不知道这个问题的答案，并将其作为一个具有挑战性的开放问题留给后人。然而，当输入实例限制在某些结构化图类中时，我们能否得到一些结论？在这方面，我们首先提到全色数问题即使在输入图是树的情况下也是 NP 完全的 [23]。因此，研究者们考虑了在多个树类上的全色数问题 [3]，并在这些图类上设计了多项式时间算法。在本工作中，我们为树上和 $d$-退化图上的全色数问题设计了多项式核，并获得了以下结果。定理 2 以解大小 $k$ 为参数的全色数问题在森林上接受大小为 $\mathcal{O}(k^2)$ 的核。定理 3 以解大小 $k$ 为参数的全色数问题在 $d$-退化图上接受大小为 $\mathcal{O}(k^{24d+2})$ 的核。我们进一步研究了全色数问题关于其他参数的性质。我们定义问题全色数/$\mathrm{Mod}(\pi)$，其中 $\pi$ 是一个图类，如下所述。对于一个无向图 $G$ 和一个图类 $\pi$，大小为 $\ell$ 到 $\pi$ 的调制器是一个大小为 $\ell$ 的顶点子集 $S$，使得 $G \setminus S$ 属于 $\pi$。输入：一个无向图 $G$，一个大小为 $\ell$ 到 $\pi$ 的调制器，以及一个正整数 $k$。问题：$\psi(G) \geq k$ 是否成立？回顾全色数问题即使在输入图是树的情况下也是 NP 完全的 [23]。这立即排除了将树宽或反馈顶点集大小作为参数。到无边图的调制器。我们研究的参数是图的顶点覆盖数，即一个顶点集，删除该集合的结果是无边图。这里 $\pi$ 是无边图的族。我们在这个方向上的结果如下。定理 4 全色数/VC 可在 $2^{\mathcal{O}(\ell^2)} \cdot n^{\mathcal{O}(1)}$ 时间内求解。为了证明定理 4，我们首先证明图的全色数被 $\ell+1$ 所界。然后，我们猜测调制器中顶点的颜色（一个将产生解的猜测）。可能存在一对颜色没有被分配给任何边的端点，例如，颜色类 $C_1$ 和 $C_2$ 之间可能没有边。为了解决这个问题，我们利用调制器外的一个顶点 $v$，将其分配为颜色 $C_1$ 或 $C_2$，从而解决由颜色类 $C_1$ 和 $C_2$ 形成的对（本质上，我们解决了由于颜色类 $C_1$ 和 $C_2$ 之间没有边而产生的冲突）。我们通过将问题归结为子图同构问题（给定一个宿主图 $G$ 和一个模式图 $H$，在 $G$ 中找到 $H$ 的一个副本）来解决这个问题，其中模式图 $H$ 的大小为 $\mathcal{O}(\ell^2)$，树宽为 $\mathcal{O}(1)$。已知子图同构可以在 $2^{\mathcal{O}(|H|)} \cdot |V(G)|^{tw+1}$ 时间内求解，其中 $tw$ 是模式图的树宽，从而得出我们算法所需的运行时间。我们证明全色数/VC 在接受顶点覆盖大小 $\ell$ 作为参数时不存在 $2^{o(\ell)}$ 时间的算法，除非 ETH 不成立，方法是通过对单调 3-NAE-SAT 进行多项式时间参数保持归约，而后者已知是 NP 难的 [24]。定理 5 除非 ETH 不成立，否则全色数/VC 不能在 $2^{o(\ell)} \cdot n^{\mathcal{O}(1)}$ 时间内求解，其中 $\ell$ 是顶点覆盖的大小。章节片段 预备知识 对于该问题，我们考虑无向图。对于给定的图 $G$，我们用 $V(G)$ 表示其顶点集，用 $E(G)$ 表示其边集。当上下文允许时，我们简单地将它们记为 $V$ 和 $E$。$n$ 表示顶点数，$m$ 表示边数。对于任意顶点 $u \in V$，$G$ 中与 $u$ 相邻的顶点集表示为 $N_G(u)$。特别地，$N_G(u)$ 表示 $u$ 在 $G$ 中的开邻域。当图从上下文中明显时，我们将其简写为 $N(u)$。全色数的 FPT 算法 在本节中，我们给出一个以解大小为参数的全色数问题的 FPT 算法。我们首先描述我们的核化过程，该过程以全色数问题的一个实例 $(G, k)$ 作为输入，并在 $\mathcal{O}(|E(G)|)$ 时间内返回一个等价的实例（核）。我们证明以下结果。定理 6 全色数问题接受一个大小为 $kk + 2^{k^3} + k + 2 e^{2k^2}$ 的核。

此外，我们可以在O(m)的时间内找到它，其中m是给定图的边数。

设R为一个等价关系。

按顶点覆盖参数化

在本节中，我们研究Achromatic Number（非极大团数）相对于一个结构参数的参数化复杂度，该参数是无边图的调节器（也称为顶点覆盖）。我们将此版本的Achromatic Number称为Achromatic Number/VC，其正式定义如下。

Achromatic Number/VC
参数：?
输入：一个无向图G，一个大小为?的集合S?V(G)，使得G?S是一个独立集，以及一个正整数k。
问题：ψ(G)≥k是否成立？

以下是本节的主要结果。

定理4. 森林的核
我们在算法3中描述我们的规约算法。

定理2. 按解的大小k参数化的Achromatic Number在森林上具有大小为O(k2)的核。

证明：当k=1的情况直接处理，因此假设k≥2。设T为在穷尽应用约减规则1和2之后得到的森林。设L为其叶子集合，P为其邻居集合。给每个p∈P赋予权重w(p)=|N_T(p)∩L|。每个叶子恰好有一个邻居，因此∑_p∈P w(p)=|L|。由于T[P]是二部图，选择一侧

d-退化图的核

在本节中，当图是d-退化的时候（其中d是一个固定常数），我们得到了Achromatic Number的一个多项式核。首先，我们陈述一个关键的定理，我们用它来设计d-退化图的多项式核。然后，我们证明几个引理来展示我们的规约算法的正确性。我们从以下引理开始，该引理断言如果一个图包含一个大的诱导匹配，则该图的非极大团数也较大。

引理28 设G为一个...

按顶点覆盖参数化的下界

在本节中，我们证明除非指数时间假设（ETH）不成立，否则Achromatic Number/VC不存在2^(o(?))时间算法，其中?是顶点覆盖的大小。回顾一下，由Impagliazzo和Paturi [27]提出的ETH指出，3-SAT不能在亚指数时间内求解，即在2^(o(n))时间内求解，其中n表示变量的个数。我们给出了一个从单调3-NAE-SAT出发的多项式时间保持参数的规约，该问题是已知的NP难问题 [24]。具体地，我们证明...

结论

在本文中，我们对Achromatic Number进行了参数化研究，并设计了一种在一般图上的FPT算法，具有明确的运行时间。我们还研究了该问题相对于结构参数化的性质。我们的工作留下了几个令人感兴趣的开放问题。

1. Achromatic Number在一般图上是否有多项式核？
2. 我们证明了Achromatic Number/VC可以在2^(O(?2))·n^(O(1))的时间内求解。我们还证明了Achromatic Number/VC算法运行时间的以下下界...

CRediT作者贡献声明

Satyabrata Jana：写作 – 审阅与编辑，写作 – 初稿撰写，形式分析，概念构思。Souvik Saha：写作 – 审阅与编辑，写作 – 初稿撰写，形式分析，概念构思。Saket Saurabh：写作 – 审阅与编辑，写作 – 初稿撰写，监督指导，形式分析，概念构思。Anannya Upasana：写作 – 审阅与编辑，写作 – 初稿撰写，形式分析，概念构思。

利益冲突声明

作者声明他们没有已知的竞争性经济利益或个人关系可能对本论文所报告的工作产生影响。

Satyabrata Jana | Souvik Saha | Saket Saurabh | Anannya Upasana