染色

染色问题的暴力复杂度为 .

由于染色问题要求相邻两点颜色不同, 可以考虑借助独立集的性质, 在给定的图上加上一些互不相邻的点后色数恰好加一(或者说染色后每一种颜色的顶点集合都是一个独立集), 对于 , 记 , 的最大独立集集合为 , 那么就有下面的递推 可以断言 .

这个 DP 算法的复杂度为 , 证明需要用到最大独立集的 branching 算法的时间复杂度.

先把证明贴到下面:

集合覆盖

最小支配集

首先叙述最小支配集问题与集合覆盖问题 的关系: 令 , 可以将求解最小支配集的问题转化为集合覆盖问题. 称 被 支配当且仅当 , 那么 是所有被 支配的点的集合, 因此对于 , 是最小支配集当且仅当 能够覆盖 .

对于一般的图 而言, 存在一个求解其最小支配集的动态规划算法, 时间复杂度为 , 其中 为最大独立集, 特别地, 对于二分图而言 , 时间复杂度为 . 下面叙述这个算法.

设 , 首先 一定是支配集, 考虑反证法, 假设存在 且 没有被 支配, 那么 不与 中的点相邻, 而 又不与 中的相邻, 那么 就是一个孤立的点, 而我们只考虑连通图.

考虑枚举 的子集 在 上的投影来寻找最小支配集, 令 , 逐步向 中添加 中的顶点, 可以得到支配集. ?

对于每个 , 令 , 那么就有.

令 , 表示最大独立集 中没有被 支配的部分, 再令 表示 中没有被 支配的部分, 那么通过置 , 便可将原问题转化成一个新的规模稍小一些的集合覆盖问题, 这个集合覆盖问题可以在 内解决, 那么总的时间复杂度为 .

看不懂. 先放弃了. 以后有时间再看吧. /kk

剩下是设计一个新的动态规划算法将时间复杂度从 降到 的过程.