Dynamic Maximal Independent Set using Predictions

Shahbaz Khan, Anshul Kumar

We present the first dynamic maximal independent set (MIS) of a graph with $n$ vertices and up to $m$ edges under edge updates in the prediction model, where a predicted update seq…