Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures

摘要

The Maximum Vertex Weight Clique (MVWC) problem is a generalization of the Maximum Clique problem, which exists in many real-world applications. However, it is NP-hard and also very difficult to approximate. In this paper we developed a local search MVWC solver to deal with large sparse instances. We first introduce random walk into the multi-neighborhood greedy search, and then implement the algorithm with efficient data structures. Experimental results showed that our solver significantly outperformed state-of-the-art local search MVWC solvers. It attained all the best-known solutions, and found new best-known solutions on some instances.