Color Coding | Codeboy's Blog

形式陈述

Colorful 事件

要找含 $k$ 个顶点的简单路径，独立均匀把每个顶点染为 $[k]$ 中一色。固定目标路径 colorful（各顶点颜色互异）的概率为

\frac{k!}{k^k}\ge e^{-k}\operatorname{poly}(k)^{-1}.

概率只依赖参数 $k$ ，所以重复 $e^k\operatorname{poly}(k)\log(1/\delta)$ 次可把固定存在目标漏掉的概率降至 $\delta$ 。

颜色子集 DP

令 DP $[S,v]$ 表示是否存在一条以 $v$ 结尾、所用颜色恰为 $S$ 的 colorful 路。基例是 $S=\{color(v)\}$ ；转移从邻居 $u$ 的 DP $[S\setminus\{color(v)\},u]$ 延伸，要求 $color(v)\notin S\setminus\{color(v)\}$ 。检查 $|S|=k$ 的任意终点即可。单次典型时间 $O(2^k|E|)$ ，空间 $O(2^k|V|)$ 。

直觉

简单路径图像

普通子集 DP 若按顶点集合会有 $2^{|V|}$ 状态；随机颜色把只关心的 $k$ 个目标顶点压成 $2^k$ 个颜色集合。若目标路径 colorful，颜色互异自动保证 DP 不重复使用顶点，即便图中其他顶点颜色碰撞也不影响该轮目标。

随机着色图中的 colorful 路径与颜色子集 DP 状态 — Color Coding 的异色路径与颜色集合状态

例子与边界

去随机化与边界

$k$ -perfect hash family 保证每个 $k$ 顶点集合至少被某个着色映成互异颜色，枚举该族可去随机化；这与独立随机染色的概率保证不同。路径“长度 $k$ ”必须说明是 $k$ 个顶点还是 $k$ 条边。对一般目标子图，colorful 检测本身可能仍 NP-hard；着色只消除顶点互异约束，不自动解决结构匹配。

One-sided 正确性

DP 返回 colorful path 时，颜色互异保证顶点互异，所以输出一定是真实简单路径；随机性只可能让已有目标在本轮不 colorful 而漏报。因此这是 one-sided Monte Carlo，可保存 DP 父指针恢复并验证路径。

重复次数来自 $(1-p)^R\le e^{-pR}$ ，其中 $p=k!/k^k$ ，而不是笼统“多试几次”。去随机化枚举 hash family 后运行同一 DP，总时间还要乘 family 大小。

推论与应用

固定一种着色后，“是否存在彩色路径/子图”通常由动态规划按颜色子集和端点合并；为了从随机成功概率转成确定性覆盖，可用完美哈希族保证每个目标 k 元顶点集在某个着色下被注入地着色。

路径恢复与内存布局

若要输出路径，每个首次置真的状态保存前驱顶点 $u$ ；从任意真状态 DP[allColors,v] 反复删除当前颜色并读父指针，逆序即可恢复 $k$ 个顶点。恢复后仍应线性检查相邻边和顶点互异，作为随机算法输出的廉价证书。

只回答存在性时，可按子集大小分层保存 bitset，或让每个 (S,v) 用一位表示；要回溯则父指针通常需要 $\Theta(\log |V|)$ 位，使空间从布尔表显著增大。滚动数组也会覆盖较小子集的父状态，需要在空间与可恢复性之间选择。

对无向路径，转移会从边的两个方向更新；有向路径只能沿入边到 $v$ 。若枚举邻接时方向混用，DP 仍可能产生颜色互异的顶点序列，却不对应原有向图中的路径。

一次着色的表可在找到目标后立即停止；多轮试验之间必须清空状态和父指针，但图邻接表可以复用。去随机化时着色族的枚举顺序不改变这套表语义，只改变外层运行次数。

参考资料

Noga Alon, Raphael Yuster, Uri Zwick, Color-Coding, JACM, 1995.
Marek Cygan et al., Parameterized Algorithms, Springer, 2015.

形式陈述 ​

Colorful 事件 ​

颜色子集 DP ​

简单路径图像 ​

去随机化与边界 ​

One-sided 正确性 ​

路径恢复与内存布局 ​