Computing Maximum Independent Sets over Large Sparse Graphs

摘要

This paper studies the fundamental problem of efficiently computing a maximum independent set (or equivalently, a minimum vertex cover) over a large sparse graph, which is receiving increasing interests from the research communities of graph algorithms and graph analytics. The state-of-the-art algorithms for both exact and heuristic computations heavily rely on kernelization techniques that use reduction rules to reduce a large input graph to a smaller graph (called its kernel) while preserving the maximum independent set. However, the existing kernelization techniques either run slow (but return a small kernel), or return a large kernel (but run fast). In this paper, we propose two techniques—aggressive incremental reduction rules and connected component checking—to speed up the kernelization process while computing a small kernel. Furthermore, for efficient maximum independent set computation, we propose to control the giant kernel connected component size, and propose to invoke maximum clique solvers for solving the kernel graph. Extensive empirical studies on large real graphs demonstrate the efficiency and effectiveness of our techniques.