FULLY DYNAMIC MAXIMAL MATCHING IN O(log n) UPDATE TIME

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. While there exists a trivial O(n) time algorithm for each edge update, the previous best known result for this problem is due to Ivkovic and Lloyd [Lecture Notes in Comput. Sci. 790, Springer-Verlag, London, 1994, pp. 99-111]. For a graph with n vertices and m edges, they gave an O((n + m)(0.7072)) update time algorithm which is sublinear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfeld [Proceedings of STOC'10, Cambridge, MA, 2010, pp. 457-464] designed a randomized algorithm that achieves expected amortized O(log(2) n) time for each update for maintaining a c-approximate maximum matching for some unspecified large constant c. In contrast, we can maintain a factor 2 approximate maximum matching in expected amortized O(log n) time per update as a direct corollary of the maximal matching scheme. This in turn also implies a 2-approximate vertex cover maintenance scheme that takes expected amortized O(log n) time per update.