Oded's choices (Nr. 371)

Faster Combinatorial Algorithms for Bipartite Matching

by Julia Chuzhoy and Sanjeev Khanna.

Oded's comments

The new algorithms, presented at SODA24 and STOC24, respectively, improve over the half-century algorithm of Hopcroft and Karp (for graphs of high density), are:

A deterministic $tildeO(m^{1/3} n^{5/3})$-time algorithm.
A randomized $n^{2+o(1)}$-time algorithm.

The first algorithm proceeds in polylogarithmic iterations such that as long as the gap between the current value and the optimal one is not too small, it is decreased by a factor of $1-(1/polylog)$. Considering the equivalent problem of finding max st-flows in a graph with unit capacities, the iterations proceed by finding relatively large sets of disjoint st-paths in the residual network. This is done by reducing the problem to a special case of the decremental single-source shortest paths (SSSP) in directed graph and improving the known algorithms by using features of the special case.

This fits the paradigm of reducing classical graph algorithm problems to problems about dynamic graphs, and illustrates the benefit of taking a close look at the reduction so to captialize on specicial features of the instances that it produces.

The original abstract

Maximum bipartite matching is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp solves the problem in time $O(m \sqrt{n})$ on a graph with $n$ vertices and $m$ edges. For the case of very dense graphs, a different algorithm based on fast matrix multiplication was subsequently developed, with running time of $O(n^{2.371})$. This remained the state of the art until recently, when a new method for solving maximum flow and related problems was introduced, that utilizes continuous optimization techniques, such as interior-point methods for solving linear programs. Following this, a sequence of remarkable new results that rely on this method have led to faster algorithms, culminating in a spectacular breakthrough, that gives an almost-linear time algorithm for maximum bipartite matching, and more generally, for min cost flow.

This raises a natural question: is it possible to obtain faster algorithms for the bipartite matching problem via combinatorial techniques? In this talk we present new results that provide a positive answer to this question, by designing faster combinatorial algorithms for the problem, via the classical augmenting-path based approach.

Back to list of Oded's choices.