次模函数近似算法求最小弱顶点覆盖

Submodular potential function for the minimum weak vertex cover problem

求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度。

The minimum weak vertex cover problem is non-deterministic polynomial-time hard （NP-hard）, and thus we can only produce an approximate solution to this problem. Here we start from a fundamental cycle to define a submodular potential function. Then using the theory of submodular potential functions, we give an approximation algorithm to solve the problem. The approximation factor of the algorithm is 1 ＋ In （ d - 1 ） , where d is the maximum degree of the vertices.