【学术】Color-Coding 随机染色

子图同构

图同构定义：对于图 \(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'\)。

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

子图同构问题是 NP-hard 问题。对于子图同构的特殊情况：

1. 判断图中是否有长度为 \(k\) 的简单路径。（k-path 问题）

2. 判断图中是否有长度为 \(k\) 的简单环。

由于当 \(k=n\) 时这两者等价于哈密顿路/回路，也是 NP-hard 的。但是当 \(k=O(\log n)\) 时有多项式复杂度。也就是通过 Color-Coding 随机染色。

k-path 问题（log-path）

构造映射 \(f\)，将每个点随机染色为 \(k\) 种颜色之一，然后找到一个点数为 \(k\) 的子图其中颜色两两不同，那么称找到一个同构子图。

找到子图的过程使用状压 dp 即可，\(dp_{u,S}\) 表示路径端点在 \(u\) 点且使用了 \(S\) 中的颜色，此处不过多赘述。正确性显然是很低的，不难发现只有 \(P=\dfrac{k!}{k^k}\)，若运行 \(T\) 次错误率便降到 \(P'=(1-P)^T\)，令 \(λ=\dfrac1 P\)，反复迭代可以得到结论：

\(T=λ-1\) 时，错误率降为约 \(\dfrac 1 e\)。

原理是 \(\lim\limits_{n\to \infty}\left(1+\dfrac 1n\right)^n=e\)。而 \(\lambda=2^{O(k)}\)，算上单次运行，总时间复杂度为 \(-2^{O(k)}m\log P'\)，当 \(k=O(\log n)\)，令 \(m=O(n^2)\) 便有多项式复杂度。若是追求确定性算法，构造大小为 \(2^{O(k)}\log n\) 的映射 \(f\) 的集合 \(F\)，但在 OI 中或许比较 useless。

对于模式图 \(H\) 是树，和寻找 \(k\) 元环的方式在 OI 中极不寻常，所以不做赘述。需要的看文末的参考文献。

将 Color-Coding 在 OI 中运用

• ※ Color-Coding 总是和斯坦纳树一起出现。先考虑颜色范围 \(<k\) 时使用斯坦纳树状压 dp 的暴力做法后，使用 Color-Coding 随机来优化。

对于 k-path 问题我没有什么例题， [CSP-S 2022] 假期计划确实可以使用 k-path 去做。

• [THUSCH2017] 巧克力

对于此题详细解法看我的2023杂题乱做中巧克力一题的解析。此题映射的方式与我们上文阐述的方式完全相同，是一道 Color-Coding 模板题。

• treemax

给定一棵有点、边权的树，需要你选择一个点集 \(S\)，点集大小最多为 \(k\) 且点集中点权两两不同，使点集中的点形成的生成树边权和最大，输出最大边权和。\(n\le 4000,k\le 5\)。

对于这种 \(k\) 极小而颜色范围不固定的问题，想要做 Color-Coding 先从弱化版入手：考虑若所有颜色范围在 \([0,k)\) 中。这个思路极为重要，在上面的几道题中也是一样的入手方向。

和斯坦纳树一样的方式，\(dp_{u,S}\) 表示考虑 \(u\) 子树，选择的点集 \(S\)，此时生成树的最大边权和。转移和斯坦纳树一样，不讲了。然后使用 Color-Coding 优化。做完了。是不是非常套路。当然前提是你见过。

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=4e3+4;
const int K=70;

int n,k,tot,head[N],dp[N][K],a[N],I[N],_=260,ans;
mt19937 rnd(time(0));

struct edge{
	int to,nxt,w;
}e[N<<1];

inline void addedge(int u,int v,int w){
	e[++tot].to=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
	return;
}

inline void dfs(int u,int fa){
	dp[u][1<<I[a[u]]]=dp[u][0]=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int S=(1<<k)-1;~S;S--){
			for(int T=S;;T=S&(T-1)){
				if(S^T)dp[u][S]=max(dp[u][S],dp[u][T]+dp[v][S-T]+e[i].w);
				if(T&&(S^T))ans=max(ans,dp[u][T]+dp[v][S^T]+e[i].w);
				if(!T)break;
			}
		}
	}
	return;
}

signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<n;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		addedge(u,v,w),addedge(v,u,w);
	}
	while(_--){
		memset(dp,-0x3f,sizeof(dp));
		for(int i=1;i<=n;i++)I[i]=rnd()%k;
		dfs(1,0);
	}
	printf("%lld",ans);
	return 0;
}

• 三部图判定

• 给定一张 \(n\) 个结点、\(m\) 条边的简单无向图，用 RGB 三种颜色给每个结点染色 满足任意一对邻居都不同色，或者报告无解。

对于一条边 \((u,v)\)，若 \(u\) 的染色确定，那么 \(v\) 仍有两种染色方式。若 \(v\) 的染色唯一那么就很好做了，所以考虑给每个点钦定一个颜色 \(c_{u}\) 表示 \(u\) 不能选择颜色 \(c_u\)，那么 \(v\) 的颜色就唯一确定为 \(\{R,G,B\}\setminus \{col_u,c_v\}\)。然后就可以 2-sat 做了。单次运行正确率为 \(P=\left(\dfrac2 3\right)^n\)，根据上文结论运行 \(-(P')^n\log \epsilon\) 保证 \(1-\epsilon\) 的正确率。所以 Color-Coding 的本质就是用随机集合覆盖目标元素。

• 「2020-2021 集训队作业」Storm

将每个点黑白染色，只保留端点不同色的边，然后费用流。注意到最终选出的边构成菊花图森林，而对于每个联通块，必须满足周围的点颜色和中间那个点不同，正确率 \(2^{-k}\)。

参考文献

https://arxiv.org/pdf/1908.11248.pdf

https://dl.acm.org/doi/pdf/10.1145/210332.210337

https://www.luogu.com.cn/blog/LuoTianyi-QwQ/color-coding

https://oi-wiki.org/misc/rand-technique/