Efficient Computation of a Near-Maximum Independent Set over Evolving Graphs.

Abstract

Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time $t_{i+1}$ based on the MIS/IS at time $t_i$. Due to the hardness of computing an exact MIS, we develop an efficient constant-time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.

Citation

Weiguo Zheng, Qichen Wang, Jeffrey Xu Yu, Hong Cheng, and Lei Zou. “Efficient Computation of a Near-Maximum Independent Set over Evolving Graphs.” IEEE International Conference on Data Engineering (ICDE), April 2018.