浅谈染色技术与子图同构问题

TianyiLemon · 2023-02-05 01:54:36 · 个人记录

1. 概述

注意：本文中的染色技术≠图着色算法。

染色技术（color-coding）是一项在计算机科学领域应用十分广泛的技术，但它在 OI 中的应用依然停留在比较粗浅的层面。本文将简单介绍染色技术，以及它在解决子图同构问题方面的应用。最后，我会简单罗列一些染色技术在 OI 方面的应用。

由于笔者对这方面的了解还十分有限，有什么疏漏/需要补充的地方欢迎指正。

1.1 记号和约定：

• 若无特殊说明，n 代表图的点数，m 代表图的边数。

• 如果我们称函数 f=2^{O(k)}，这代表存在常数 c，使得 k 足够大时，总有 f\le 2^{ck}。有时我们更关心算法复杂度的量级，而非实际运行效率，这时可能会使用这个记号。

1.2 前置知识

• 定义 1.2.1 图同构（graph isomorphism）：对于图 G=(V,E) 和 G'=(V',E')，如果存在双射函数 f:V\to V'，使得 (v_i,v_j)\in E 当且仅当 (f(v_i),f(v_j))\in E'，则称 G 与 G' 同构，记作 G\cong G'。

  图同构问题目前没有有效多项式算法。

• NPC/NP-hard 问题：通俗地说，就是被普遍认为不存在多项式算法的问题。

• 定义 1.2.2 树分解（tree decomposition）：图 G=(V,E) 的树分解是一个二元组 (X,T)，其中 T=(I,F) 是一棵树，X=\{X_i| i\in I\} 是满足下列条件的 V 的子集族：

  • 对任意边 (u,v)\in E，存在 i\in I 满足 u,v\in X_i。
  • 如果 i,j,k\in I 且 j 在 T 中 i 到 k 的路径上，那么 X_i\cap X_k\subseteq X_j。

  树分解 (X,T) 的宽度为 \max_{i\in I}\{|X_i|\}-1。图 G 的树宽度（tree-width）是 G 所有可能树分解的宽度的最小值。

  本文不会过多探讨关于树分解的内容，你只需要知道树宽度不超过 1 的图等价于森林，树宽度不超过 2 的图等价于广义串并联图（series-parallel graph）。

• 定义 1.2.3 布尔矩阵乘法（boolean matrix multiplication）：对于 n\times m 的布尔矩阵 A 和 m\times k 的布尔矩阵 B，C=A\times B 是一个 n\times k 的矩阵，并且满足

  C_{i,j}=\bigvee_{k=1}^{m} A_{i,k}\wedge B_{k,j}

  其中 \vee 代表逻辑或运算，\wedge 代表逻辑与运算。

  目前，计算两个 n\times n 布尔矩阵乘法的最快复杂度和普通矩阵乘法相同，都是 O(n^{\omega})。

2. 子图同构问题

定义 2.1（子图同构问题） 给定点数为 n 的图 G=(V,E) 和点数为 k 的模式图 H=(V_H,E_H)，问是否存在一个 G 的子图 G' 满足 G'\cong H。如果存在，输出 G' 的一种方案。

子图同构问题是 NP-hard 问题。

子图同构问题有若干特殊情况：

• （k-path problem）判断图 G 中是否存在长度恰好为 k 的简单路径。

• 判断图 G 中是否存在一个长度恰好为 k 的简单环。

可以发现上面两个问题也是 NP-hard 问题，因为 k=n 时它们分别等价于哈密顿路和哈密顿回路存在性判定。第 3,4 章中会介绍 k=O(\log n) 时，上面两个问题的多项式解法。

3. 染色技术

在本节中，我们将证明，log-path problem 可以在多项式时间内求解。解法中用到的关键技术就是染色技术。

染色技术由 Alon,Yuster 和 Zwick 在 1995 年提出。其核心思想十分简单，主要分为两步：

• 构造一个映射 f:V\to \{0,1,\dots,k-1\}，也就是将图 G 中的每个点用 k 种颜色之一染色。
• 找出一个点数为 k 的子图 G'=(V',E')\cong H，且 V' 中每个点的颜色两两不同。也就是说，若 V'=\{v_1,v_2,\dots v_k\}，那么 \{f(v_1),f(v_2),\dots ,f(v_k)\}=\{0,1,\dots, k-1\}。

对于 k-path problem，第二步容易使用状压 DP 解决。具体地，设 dp_{u,S} 代表是否存在一条路径，它的一个端点为 u，且恰好使用了集合 S 中的颜色。有转移 dp_{v,S\cup\{f(v)\}}\leftarrow dp_{u,s}，其中 (u,v)\in E。

容易发现，执行一次这样的过程，只有很小的概率得到正确答案，所以我们需要重复执行多次，每次随机挑选一个 f。不妨估算一下需要执行多少次（不想看推导的可以直接跳到结论）。

对于一条长度为 k 的路径，它所有可能的染色方案数为 k^k。其中，它成为一条合法染色路径的方案数为 k!。所以，我们找出这样一条路径的概率至少为 P=\dfrac{k!}{k^k}，根据斯特林公式，P\approx \dfrac{\sqrt{2\pi k}}{e^k}。

假设我们运行了 T 次，那么错误率 \epsilon=(1-P)^T，不妨来估计一下这个东西的量级。

令 \lambda=\dfrac{1}{P}，则

众所周知，

所以

结论 3.1 我们每运行 \lambda-1 次求解染色问题的算法，错误率就会大约变为原来的 \frac{1}{e}。

这个结论非常有用，在 oi wiki 中也有提及。

在这个问题中 \lambda\approx 2^{O(k)}，所以为了得到 1-\epsilon 的正确率，我们需要运行 -2^{O(k)}\log \epsilon 次上述算法。

而单次求解的时间复杂度是 2^{O(k)}m 的，所以我们就在 -2^{O(k)}m\log \epsilon 时间内解决了 k-path problem。

当 k=O(\log n) 时，令 m=O(n^2)，那么上面这个函数就是一个关于 n 的多项式。这样我们就证明了本节开头提到的命题。在第 4.1 小节中，我们还会提到如何将上述算法的时间复杂度优化到 -2^{O(k)}n\log \epsilon。

实际上，将上述随机算法 “去随机化” 之后，我们还能得到一个时间复杂度 2^{O(k)}m\log n 的确定性算法。具体方法是构造一个大小为 2^{O(k)}\log n 的映射 f 的集合 F，使得对任意 V 的大小为 k 的子集 \{v_1,v_2,\dots v_k\}，存在 f\in F，满足 \{f(v_1),f(v_2),\dots ,f(v_k)\}=\{0,1,\dots, k-1\}。不过在 OI 中并不 practical。

为了方便，后文中标注的时间复杂度默认是确定性算法的时间复杂度。

4. 染色技术的一些拓展

实际上，上述 k-path problem 的解法可以拓展到 k-tree problem（名字我瞎取的），也就是模式图 H 是一棵树的情况。

4.1 k-tree problem 的解法

将 H=(U,F) 看作一棵有根树，令 \operatorname{sub}(x) 代表点 x 子树中的点构成的点集。dp_{u,S,x,k} 代表 G 中是否存在 u 为根的树，它用了 S 中所有的颜色，并且它与 \{x\}\cup \operatorname{sub}(u_1)\cup \dots\cup\operatorname{sub}(u_k) 的诱导子图同构，其中 x\in U 且 u_1,u_2,\dots,u_k 是 x 的儿子。 转移应该比较显然。

这样做时间复杂度是 2^{O(k)}m\log n 的。利用一个引理，我们可以将时间复杂度优化到 2^{O(k)}n\log n。

引理 4.1.1 若 m\ge (k-1)n，那么 G 中包含任意点数为 k 的树。

更一般地，对于树宽度为 t 的模式图 H，子图同构问题存在时间复杂度 2^{O(k)}n^{t+1}\log n 的算法。具体方式是构造出 H 的树分解，然后执行和 k-tree problem 类似的 DP 过程。不过同样因为 not practical，所以不过多介绍。

这里，我还想介绍一种时间复杂度 2^{O(k)}n^{\omega}\log n 的，判定 k 元环存在性的算法。

4.2 k 元环问题的解法

首先，我们可以将上述问题转化为：对任意一对起点 u,v，判断是否存在一条点数为 k 的简单路径，它的两个端点分别是 u,v。如果 u,v 满足上述条件且 (u,v)\in E，那么我们就找到了一个 k 元环。

通过枚举起点 s，然后套用 k-path problem 的解法，不难得到一个 2^{O(k)}nm\log n 的解法。

为了得到 2^{O(k)}n^{\omega} \log n 的算法，我们需要用到分治的思想。

令 solve(S) 代表考虑点集 V_0=\{v|f(v)\in S\} 的生成子图，对任意 u,v\in V_0，求出是否存在长度为 |S| 的路径，它的两个端点分别为 u,v。

容易发现，solve(\{0,1\dots,k-1\}) 即为我们所求。