顶点覆盖 2-近似算法

顶点覆盖 2-近似算法是解决最小顶点覆盖问题的一种近似算法。最小顶点覆盖要求在图中选出尽可能少的顶点,使每条边至少有一个端点被选中,该问题是 NP 困难的。2-近似算法放弃求最优解,转而在多项式时间内给出一个规模不超过最优解两倍的可行解。

概述

由于最小顶点覆盖难以在多项式时间内精确求解,人们退而求其次寻求有质量保证的近似解。所谓 2-近似,是指算法输出解的规模至多为最优解的两倍。这个基于极大匹配思想的贪心算法极其简单,却能给出严格的理论保证,是近似算法领域的经典入门案例。

核心原理

算法过程如下:初始化空的覆盖集合;当图中还存在未被覆盖的边时,任取这样一条边,把它的两个端点同时加入覆盖集合,并视为覆盖了所有与这两个端点相连的边;重复直至所有边都被覆盖。

• 正确性:每条边至少有一个端点被选中,输出的确是一个合法顶点覆盖。
• 近似比证明:算法所选的边两两不共享端点,构成一个匹配;任何顶点覆盖都必须为这些边各覆盖至少一个端点,故最优解不小于匹配的边数,而算法解恰为其两倍。
• 复杂度:只需遍历边一次,运行时间为线性级。

应用场景

顶点覆盖在网络监控节点部署、生物信息学中的冲突消解、以及各类需要用少量元素覆盖全部关系的场景中都有应用。当规模过大无法精确求解时,2-近似算法可快速给出可用且有质量下界保证的方案。

常见问题

问:为什么把边的两个端点都加入而不只加一个?答:因为无法确定哪个端点属于最优解,同时加入两个端点才能保证不遗漏,并借助匹配的性质证明近似比恰为二。

问:存在更好的近似算法吗?答:目前已知的近似比略优于二的算法非常有限;在一定复杂性假设下,顶点覆盖被认为难以在多项式时间内取得明显优于二的近似比。