On the Locality of Hall's Theorem

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems.

The current lower bound techniques for deterministic algorithms are often tailored to obtaining a logarithmic bound and essentially cannot be used to prove lower bounds beyond Ω(log n). In contrast, the best deterministic upper bounds, usually obtained via network decomposition or rounding approaches, are often polylogarithmic, raising the fundamental question of how to resolve the gap between logarithmic lower and polylogarithmic upper bounds and finally obtain tight bounds.

We develop a novel algorithm design technique aimed at closing this gap. It ensures a logarithmic runtime by carefully combining local solutions into a globally feasible solution. In essence, each node finds a carefully chosen local solution in O(log n) rounds and we guarantee that this solution is consistent with the other nodes' solutions without coordination. The local solutions are based on a distributed version of Hall's theorem that may be of independent interest and motivates the title of this work.

We showcase our framework by improving on the state of the art for the following fundamental problems: edge coloring, bipartite saturating matchings and hypergraph sinkless orientation (which is a generalization of the well-studied sinkless orientation problem). For each of the problems we improve the runtime for general graphs and provide asymptotically optimal algorithms for bounded degree graphs. In particular, we obtain an asymptotically optimal O(log n)-round algorithm for (3∆/2)-edge coloring in bounded degree graphs. The previously best bound for the problem was O(log 4 n) rounds, obtained by plugging in the state-of-the-art maximal independent set algorithm from [Ghaffari, Grunau, SODA'23] into the 3∆/2-edge coloring algorithm from [Ghaffari, Kuhn, Maus, Uitto, STOC'18].