Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs

We study dynamic (1−є)-approximate rounding of fractional matchings—a key ingredient in numerous breakthroughs in the dynamic graph algorithms literature. Our first contribution is a surprisingly simple deterministic rounding algorithm in bipartite graphs with amortized update time O(є−1 log2 (є−1 · n)), matching an (unconditional) recourse lower bound of Ω(є−1) up to logarithmic factors. Moreover, this algorithm's update time improves provided the minimum (non-zero) weight in the fractional matching is lower bounded throughout. Combining this algorithm with novel dynamic partial rounding algorithms to increase this minimum weight, we obtain a number of algorithms that improve this dependence on n. For example, we give a high-probability randomized algorithm with Õ(є−1 · (loglogn)2)-update time against adaptive adversaries. Using our rounding algorithms, we also round known (1−є)-decremental fractional bipartite matching algorithms with no asymptotic overhead, thus improving on state-of-the-art algorithms for the decremental bipartite matching problem. Further, we provide extensions of our results to general graphs and to maintaining almost-maximal matchings.