Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess
Finding A Small Vertex Cover in Massive Sparse Graphs: Construct, Local Search, and Preprocess
复制标题
在大规模稀疏图中查找小顶点覆盖：构造、局部搜索和预处理
DOI：
10.1613/jair.5443
复制
发表时间：
2017-01-01
影响因子：
5
通讯作者：
Luo, Chuan
中科院分区：
文献类型：
--
作者：
Cai, Shaowei;Lin, Jinkun;Luo, Chuan
图的最小顶点覆盖问题是一个NP难的组合优化问题，在理论和实践中具有重要意义。由于其NP困难性，人们对开发启发式算法以在合理的时间内找到小顶点覆盖非常感兴趣。以前，MinVC的启发式算法主要集中在求解相对较小的图，并且它们不适合求解大规模图，因为它们通常具有高复杂度的启发式算法。本文探讨了在超大规模真实世界图中求解MinVC的技术，包括构造算法、局部搜索算法和预处理算法。构造和搜索算法都是基于低复杂度的启发式算法，我们将它们联合收割机结合起来，开发了一种名为FastVC的MinVC启发式算法。实验结果表明，我们的算法是非常快的，比以前的启发式算法MinVC有更好的性能。我们还开发了一个预处理算法来简化MinVC算法的图形。通过将预处理算法应用于局部搜索算法，我们获得了两个高效的MinVC求解器NuMVC 2 +p和FastVC 2 +p，它们在海量图上显示出进一步的改进。
The problem of finding a minimum vertex cover (MinVC) in a graph is a well known NP-hard combinatorial optimization problem of great importance in theory and practice. Due to its NP-hardness, there has been much interest in developing heuristic algorithms for finding a small vertex cover in reasonable time. Previously, heuristic algorithms for MinVC have focused on solving graphs of relatively small size, and they are not suitable for solving massive graphs as they usually have high-complexity heuristics. This paper explores techniques for solving MinVC in very large scale real-world graphs, including a construction algorithm, a local search algorithm and a preprocessing algorithm. Both the construction and search algorithms are based on low-complexity heuristics, and we combine them to develop a heuristic algorithm for MinVC called FastVC. Experimental results on a broad range of real-world massive graphs show that, our algorithms are very fast and have better performance than previous heuristic algorithms for MinVC. We also develop a preprocessing algorithm to simplify graphs for MinVC algorithms. By applying the preprocessing algorithm to local search algorithms, we obtain two efficient MinVC solvers called NuMVC2+p and FastVC2+p, which show further improvement on the massive graphs.