问题求解（三） Open Topic 16 笔记
OT：除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。
图染色问题的两种精确算法
简介
- 最小点染色算法：动态规划 [1] (Lawler, 1976), 时间复杂度 \(O(nm(1+\sqrt[3]{3})^n)\)，约为 \(O(nm\cdot 2.445^n)\)。
- 最小边染色算法：二分图最小边染色 [2] (Schrijver, 1998)，时间复杂度 \(O(\Delta m)\)。
动态规划
思路
若要对于 \(G=\langle V, E\rangle\) 染色 \(\lbrace 1, 2, \cdots, k\rbrace\)，可以考虑枚举染色为 \(k\) 的顶点子集（独立集） \(S\subseteq V\)。容易得到
\[ \chi (G)=1+\min_{S}\lbrace \chi(G-S)\rbrace \]
其中要求 \(S\subseteq V\) 且 \(S\) 为 \(G\) 的独立集。
边界条件 \(\chi(\varnothing)=0\)。
Observation 1. 贪心地，只需考虑 \(S\) 是极大独立集。
若干结论
Claim 1. 对于任意图 \(G\)，其大小为 \(r\) 的极大独立集数量不超过 \(3^{r/3}\)。
Claim 2. 存在算法可以在 \(O(mrk)\) 时间内生成所有大小为 \(r\) 的极大独立集，\(k\) 为大小为 \(r\) 的极大独立集的数量。
故对于所有的 \(V'\subseteq V\)，递推得到 \(\chi(G[V'])\) 的时间之和线性于
\[ \sum_{r=0}^n \binom{n}{r}mr3^{r/3}\le nm\sum_{r=0}^n\binom{n}{r}(\sqrt[3]3)^r=nm(1+\sqrt[3]3)^n. \]
即时间复杂度为 \(O(nm(1+\sqrt[3]3)^n)\)。
二分图最小边染色
主要思路
- \(\quad\) 任意二分图 \(G\)
- \(\to\) \(\Delta(G)\)-正则二分图 \(G'\)
- \(\to\) 对 \(G'\) 进行分治染色。
合理性
由于二分图是第一类图，故一定有 \(\chi'(G)=\Delta(G)\)。只需求其 \(\Delta(G)\) 边染色。
将 \(G\) 转化为 \(\Delta(G)\)-正则二分图 \(G'\) 后，由于 \(G'\) 仍然可以 \(\Delta(G)\) 边染色，故不会影响解的存在性。
二分图 \(G\) 至正则二分图 \(G'\)
- 若在 \(G\) 左部 \(X\) 存在 \(u, v\in X\)，满足 \(d(u)+d(v)\le \Delta(G)\)，可以将点 \(u,v\) 合并，直至不存在；
- 对于右部，同理。
- 再对于 \(d(v)<\Delta(G)\) 的点 \(v\)，向另一部未满的点随意连边。
分治染色
对于 \(k\)-正则二分图 \(G'\) 进行染色，分为两种情况
- 若 \(k\) 为偶数，可以对 \(G'\) 进行欧拉划分，得到两个 \(\frac{k}{2}\)-正则二分图，分治进行染色
- 若 \(k\) 为奇数，可以先求 \(G'\) 的一个完美匹配进行染色，则归约到 \(k-1\) 为偶数的情况。
Theorem. 存在 \(O(km)\) 的求 \(k\)-正则二分图完美匹配的算法。[2]
则该分治算法的复杂度为
\[ \begin{aligned} T(2k, 2m)&=2T(k, m)+O(m)\\ T(2k+1, 2m)&=2T(k, m)+O(km) \end{aligned} \]
解得 \(T(k, m)=O(km)\).
参考文献
[1] Lawler, E. L. (1976). A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3), 66-67.
[2] Schrijver, A. (1998). Bipartite edge coloring in O(Δm) time. SIAM Journal on Computing, 28(3), 841-846.