Color Coding

Colorful 事件 ​

要找含 $k$ 个顶点的简单路径公理库路与圈Path and cycle in a graph由相邻顶点序列形成的路，以及首尾闭合的圈。，独立均匀把每个顶点染为 $[k]$ 中一色。固定目标路径 colorful（各顶点颜色互异）的概率为

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

概率只依赖参数 $k$，所以重复 $e^k\mathrm{poly}(k)\log \left(1/\delta \right)$ 次可把固定存在目标漏掉的概率降至 $\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 不重复使用顶点，即便图中其他顶点颜色碰撞也不影响该轮目标。

去随机化与边界 ​

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

路径恢复与内存布局 ​

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

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

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

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

参考资料

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