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 log 2 (ǫ -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 • (log log n) 2 )-update time against adaptive adversaries. 1 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.