Fast MIS on Incremental Graphs

Maintaining the Maximal Independent Set (MIS) in dynamic graphs is crucial for applications like resource allocation, load balancing, and network optimization. Traditional approaches require complete re-computation, making them inefficient for large and evolving graphs. Our proposed methods utilize Tuple Valued Bitmap (TVB) and its extension with levels, TVBL, to enhance parallelism and minimize search space. Experimental evaluations on large-scale graphs, ranging from 50 million to 1.2 billion edges, demonstrate significant speedups—up to 15.64x for insertions, with minimal impact on the MIS cardinality. This approach offers a scalable solution for dynamic graphs, paving the way for further optimization in fully dynamic and streaming settings.