大数据算法课程笔记5a: fixed-parameter vertex cover

本文主要是介绍大数据算法课程笔记5a: fixed-parameter vertex cover，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 问题描述

一个vertex cover是一个点集的集合，并且保证图中的每一条边都存在至少一个顶点位于该点集中。

具体地， $G=(V,E)$ 的一个vertex cover $S$ 满足

S \subseteq V \land {\forall e = (v, w) \in E, v \in S or w \in S}

$S\subseteq V\wedge \{\forall e = (v,w)\in E, v\in S\text{ or } w\in S\}$
fixed parameter vertex cover问题即寻找

|S|=k $|S|= k$ 的vertex cover。

遍历 $V$ 的所有可能子集，复杂度为 $O(|V|^k)$ 。

注意到上诉算法的fixed paramter位于 $|V|$ 的指数项，所以我们无法说该算法是 $|V|$ 的多项式算法。

定义FPT为复杂度为 $O(f(k)n^{O(1)})$ 的算法。这个可以证明和 $O(f'(k)+n^{O(1)})$ 是等价的，其中 $n$ 表示为问题的size/难度。

对于vertex cover问题，也存在FPT的算法，具体如下：

FPT

树的深度最多为 $k$ ，所以最终算法复杂度为 $O(|E|2^k)$ ，或者 $O(2^k+|V|+|E|)$ 。

所谓kernelization，是针对输入的一个预处理。通过一些限定条件，使得输入的大小变为一个和fixed parameter相关的更小的输入。

针对vertex cover问题，缩减的工作是通过删除所有度超过 $k+1$ 的节点完成的。而重要的是缩减后的输入大小是节点数缩减为 $k(k+1)$ ，因为vertex cover内部的点集数不超过 $k$ ，而每个节点的度也不超过 $k$ ，所以所有相连节点的数目不超过 $k(k+1)$ 。

对于缩减后的输入应用以上算法都可以得到更好的结果。

至于所有度超过 $k+1$ 的节点都位于 $S$ 内，是使用反证法证明的。如果该点不在 $S$ 内，则有其余超过 $k+1$ 个点都必须在 $S$ 中才能满足与该点相连的边被覆盖到，而 $|S|\le k$ 。

这篇关于大数据算法课程笔记5a: fixed-parameter vertex cover的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！