Color Coding | Codeboy's Blog

形式陈述

Colorful 事件

输入为有限简单无向图 $G=(V,E)$ ， $n=|V|,m=|E|$ ，整数 $k\ge1$ 以及有理数 $0<\delta<1$ 。任务是找出含 $k$ 个顶点、因而有 $k-1$ 条边的简单路径； $k>n$ 时直接报告不存在， $k=1\le n$ 时返回任一顶点。以下取 $2\le k\le n$ ，使用随机化算法的固定输入、独立新随机源约定。

独立均匀把每个顶点染为 $[k]=\{1,\ldots,k\}$ 中一色。对任意预先固定的目标路径，各色互异（colorful）的概率为

p=\frac{k!}{k^k}\ge e^{-k}.

分子数的是颜色在这 $k$ 个顶点上的全部双射，分母是全部 $k^k$ 种等概率着色。给定图若确实有目标路径，固定其中任一条分析即可；算法无须知道是哪条，也无须对所有路径求并。独立重复 $R=\lceil p^{-1}\ln(1/\delta)\rceil$ 轮，每轮查找任意 colorful 路径，漏掉固定目标的概率至多 $(1-p)^R\le e^{-pR}\le\delta$ 。

颜色子集 DP

固定着色 $c:V\to[k]$ 。令 $D[S,v]$ 表示存在以 $v$ 结尾、所用颜色恰为 $S$ 的 colorful 路径。空集状态全为假，单色基例为 $D[\{c(v)\},v]=\mathrm{true}$ ；其他单色状态为假。按 $|S|$ 递增填表，对 $|S|\ge2$ ，

D[S,v]= \begin{cases} \displaystyle\bigvee_{u:\{u,v\}\in E}D[S\setminus\{c(v)\},u],&c(v)\in S,\\ \mathrm{false},&c(v)\notin S. \end{cases}

前驱路径不含颜色 $c(v)$ ，所以也不含顶点 $v$ ；接上边 $uv$ 保持简单和异色。反过来，任何非单点 colorful 路径删去末点都给出一个这样的前驱状态。这证明转移既不产生假路径，也不会漏掉当前着色下的真路径。检查 $D[[k],v]$ 的任一真状态即可。

按邻接表扫描并显式初始化各层，一轮需要 $O(2^k(n+m))$ 次基本状态访问，布尔表占 $O(2^k n)$ 位。这个界包括孤立点和空边集；若子集掩码、状态地址或前驱编号不能放入一个操作字，还须计入相应的位操作成本。父指针保存完整路径时另需 $O(2^k n\log(n+1))$ 位。

直觉

简单路径图像

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

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

图中跟踪 $p-q-r$ 的蓝、红、绿三色状态。标注的 $O(2^k|E|)$ 是 $k\ge2$ 时删去孤立点后的 DP 核心成本，因为剩余顶点数不超过 $2|E|$ ；读取原图和删除孤立点仍需 $O(n+m)$ 。

例子与边界

去随机化与边界

这里需要的 $k$ -perfect 着色族是有限函数族 $\mathcal H\subseteq[k]^V$ ，满足

\forall S\subseteq V,\ |S|=k,\quad \exists h\in\mathcal H:\ h|_S\text{ 为单射}.

枚举全部 $h\in\mathcal H$ 并运行同一 DP，就一定发现任意存在的目标路径。量词要求同时覆盖所有未知的 $k$ 元目标集；静态字典的完美哈希只为一个事先给定的键集消除碰撞，单独一个这样的函数不能提供这里的覆盖保证。

例如在四个顶点上取 $k=3$ ，两种着色 $(1,1,2,3)$ 与 $(1,2,3,3)$ 已覆盖全部四个三元子集：前者分开包含后两个顶点的三元组，后者分开包含前两个顶点的三元组。一般情形中，随机取 $t$ 个着色，某固定 $k$ 集合全部失败的概率至多 $e^{-pt}$ ；由并集界，所有 $\binom nk$ 个集合都被覆盖的失败概率至多 $\binom nk e^{-pt}$ 。令 $t=\lceil(\ln\binom nk+1)/p\rceil$ 就证明了小族的存在，但这段存在性证明本身没有给出高效的确定构造。

原论文 §4 另外给出大小 $2^{O(k)}\log(n+1)$ 的显式族构造；选用该构造及其求值模型后，可以保持 $2^{O(k)}$ 的参数依赖，并增加对数规模因子。若只给任意可枚举族，准确总成本是族的构造与求值成本，加上 $|\mathcal H|$ 轮 DP，不能只报告族的基数。

对一般目标子图，colorful 检测仍需另设结构算法；着色只处理顶点互异，不自动解决全部子图匹配约束。

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 大小。

推论与应用

固定一种着色后，本页的彩色路径检测就是按颜色子集与终点求值的动态规划。例如路径 $a-b-c-d$ 着色为 $(1,2,1,3)$ 时， $a-b-c$ 不是异色路径，但状态 $D[\{1,2\},c]$ 可由 $b$ 延伸，再得到 $D[\{1,2,3\},d]$ ，恢复 $b-c-d$ 。

路径恢复与内存布局

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

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

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

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

公平位实现的严格时间预算

上述轮数先按精确均匀颜色抽样计数。若只使用公平随机位，非二次幂 $k$ 可用 $q=\lceil\log_2k\rceil$ 位生成 $[0,2^q-1]$ 中整数，拒绝不小于 $k$ 的结果。为给每条执行固定时间预算，改取 $R=\lceil p^{-1}\ln(2/\delta)\rceil$ ，并将每个颜色抽样限制为 $B=\lceil\log_2(2nR/\delta)\rceil$ 次尝试；若超时，返回“未找到”并计为漏报。

单次尝试接受率大于 $1/2$ ，至多 $nR$ 个抽样中发生截断的概率由并集界控制为 $nR2^{-B}\le\delta/2$ ；与无限重试的理想着色算法耦合，后者漏报概率也至多 $\delta/2$ 。总失败至多 $\delta$ ，随机位与比较开销为 $O(nRB\log k)$ ，再加上述 DP 工作。 $k=1$ 分支不需要随机位，正例输出仍始终可验证。实现可用对数的可计算向上界选择整数预算，计入精度参数编码和整数运算的成本。

参考资料

Noga Alon、Raphael Yuster、Uri Zwick，Color-Coding，JACM 42(4)，1995，§3 的着色与路径 DP、§4 的显式分离族。
Marek Cygan et al., Parameterized Algorithms, Springer, 2015.

形式陈述 ​

Colorful 事件 ​

颜色子集 DP ​

简单路径图像 ​

去随机化与边界 ​

One-sided 正确性 ​

路径恢复与内存布局 ​

公平位实现的严格时间预算 ​

反向链接