点覆盖问题的近似算法研究

Research of Approximation Algorithm of Vertex Cover

点覆盖问题是最重要的NP完全问题之一,也是近年来参数算法设计中研究得最多的问题之一。针对现有点覆盖近似算法的一些不足,基于点覆盖问题参数算法的进展,提出了该问题一个基于NT定理规约的2-近似算法。利用了参数算法中的核化技术对图进行化简,在剩余图上采用贪心策略来指导节点的选择,核化技术为算法提供了有效的近似度保障。为检验新算法性能,在不同类型的随机图上通过仿真实验比较了新算法和经典的基于匹配的2-近似算法。仿真实验结果表明新算法较基于匹配的2-近似算法有着明显的优势。

Vertex cover is one of the most important NP complete problems, and it is also one of the most studied problems in parameterized algorithm design in recent years. According to some deficiencies of existing vertex cover approximation algorithms, a novel NT theorem based 2-approximation algorithm was proposed based on advances in parameterized algorithm. The new algorithm first used kernelization technology to reduce the origin graph, then used greedy strategy to guide the vertex selection in the remaining graph, kernelization provided effective guarantee for the approximation algorithm. In order to test the performance of the new algorithm, simulations on different types of random graph were carried to compare the new algorithm and the classical matching-based 2-approximation algorithm. Simulation results show that the new algorithm outperforms the matching-based 2-approximation algorithm.