周二组会讲到的内容, 感觉还蛮神奇的, 记录一下.

Crown 定义

中的 Crown 的定义是二元组 , 满足: - 是独立集 - - 和 之间存在大小为 的匹配 (即 中的所有点都被匹配到)

寻找一个图中所有的 crown 的算法是由 Minimum Vertex Cover 的整数线性规划导出的. 图 的 Minimum Vertex Cover 的整数规划如下形式:

将其松弛为线性规划:

定理1 线性规划 存在一个最优解 .

PROOF 设 的最小点覆盖为 , 那么对 , ; , , 这个解记作 , 它是 LP 的一个 feasible solution, 可以通过对部分点的重新赋值得到更优解.

若存在点集 满足:

• 对每个 都有

那么对每个 , 置 , 可以得到一个更好的解.

现在证明如果不存在这样的点集 时, 当前的解就是最优解.

定理2 对于 , 将其取值为 对应的点集分别记作 , 则 是 中的 Crown.

PROOF

Crown 的应用

Crown 可以作为 Maximum Matching 的 reduction 规则.