Fast Maximal Independent Sets on Dynamic Graphs
Prajjwal Nijhara, Aditya Trivedi, Dip Sankar Banerjee · 2025
Finding the Maximal Independent Set (MIS) in a graph is a well-known problem with applications in resource allocation, load balancing, and routing optimization. This task is particularly challenging for large graphs as it requires multiple iterations over the entire set of vertices. Recently, there has been significant interest in developing techniques to maintain the MIS dynamically in evolving graphs rather than re-computing from scratch. In this paper, we propose new data structures and techniques for computing MIS in parallel on dynamic graphs. We specifically propose techniques to handle insertions and deletions in a batched setting. We conducted detailed experiments on shared memory multicore CPUs using graphs ranging from 50 million to ${1. 2}$ billion edges. Our results show that using our technique for insertions and deletions can provide up to 15.64x and 10.57x speedups on average over comparable baselines. Additionally, the final MIS we produce varies by only about ${0. 1 8 \%}$ in cardinality compared to the existing state-of-the-art.