Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching

Most graphs in real life keep changing with time. These changes can be in the form of insertion or deletion of edges. Such rapidly changing graphs motivate us to study dynamic graph algorithms. We address three important dynamic graph problems as follows. Maximal Independent Set (MIS) is one of the most prominently studied problems in the distributed setting. Recently, a lot of work studied the dynamic MIS in both deterministic and randomized settings. Allowing randomization the MIS can be maintained in O(poly log n) time under various models [FOCS19], but the best deterministic algorithm [STOC18] requires O(m³/⁴) amortized update time, which is fairly complex. We present a simple algorithm to improve this to O(m²/³). Additionally, we present simple algorithms to match the lower bound of amortized Ω(n) update time [ICALP16], for maintaining incremental Maximum Flow and Maximum Matching (for unweighted graphs). These algorithms are simple extensions of the incremental reachability algorithm and blossoms algorithm, respectively. Thus, our results either improve an existing upper bound or match the existing lower bounds. A common trait of our results is that they are surprisingly simple, and use no complex data structures or black-box algorithms for their implementation. Further, they are analysed using basic amortization arguments.