2023/12/19 by Julia Chuzhoy, Sanjeev Khanna, Chuzhoy, Julia +1 · 4 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2312.12584
openalex publication_date 2023/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The maximum bipartite matching problem is among the most fundamental and well-studied problems in combinatorial optimization. A beautiful and celebrated combinatorial algorithm of Hopcroft and Karp (1973) shows that maximum bipartite matching can be solved in O(m √(n)) time on a graph with n vertices and m edges. For the case of very dense graphs, a fast matrix multiplication based approach gives a running time of O(n2.371). These results represented the fastest known algorithms for the problem until 2013, when Madry introduced a new approach based on continuous techniques achieving much faster runtime in sparse graphs. This line of research has culminated in a spectacular recent breakthrough due to Chen et al. (2022) that gives an m1+o(1) time algorithm for maximum bipartite matching (and more generally, for min cost flows). This raises a natural question: are continuous techniques essential to obtaining fast algorithms for the bipartite matching problem? Our work makes progress on this question by presenting a new, purely combinatorial algorithm for bipartite matching, that runs in O(m1/3n5/3) time, and hence outperforms both Hopcroft-Karp and the fast matrix multiplication based algorithms on moderately dense graphs. Using a standard reduction, we also obtain an O(m1/3n5/3) time deterministic algorithm for maximum vertex-capacitated s-t flow in directed graphs when all vertex capacities are identical.