DyGMIS: Fast and Scalable Fully Dynamic MIS Maintenance on Large Evolving Graphs

Abstract

Finding a Maximal Independent Set (MIS) in a graph is a fundamental combinatorial problem. Maintaining an MIS over large dynamic graphs is challenging as recomputation from scratch is expensive, and existing dynamic approaches either process updates sequentially or introduce costly synchronization to handle concurrent writes. In this work, we present DyGMIS, a fully dynamic batch-parallel algorithm for MIS maintenance. DyGMIS introduces an influence decomposition technique, which derives the exact algorithmic influence boundary of each MIS update, and partitions each batch into non-interfering execution zones. DyGMIS enables lock-free parallel execution with no atomic operations or synchronization barriers in the critical update phase, and further overlaps batch transfer with MIS computation via a multi-stream GPU pipeline that hides PCIe latency and maximizes SM utilization. We evaluate DyGMIS on diverse real-world graphs and update workloads against both static recomputation and existing parallel dynamic approaches. On multi-core CPUs, DyGMIS achieves up to 7.72 × speedup, and on GPUs up to 42.73 × speedup over prior parallel methods. The maintained MIS differs by less than \(0.18\%\) in cardinality compared to static recomputation, confirming solution quality.