Distributed half-integral matching and beyond

By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires omega(log* n) communication rounds, while it is possible to find a maximal fractional matching in 0(1) rounds in bounded-degree graphs. However, all prior 0(1)-round algorithms for maximal fractional matching use arbitrarily fine-grained fractional values. In particular, none of them is able to find a half-integral solution, using only values from {0, 21, 1}. We show that the use of fine-grained fractional values is necessary, and moreover we give a complete characterization on exactly how small values are needed: if we consider maximal fractional matching in graphs of maximum degree Delta = 2d, and any distributed graph algorithm with round complexity T(Delta) that only depends on Delta and is independent of n, we show that the algorithm has to use fractional values with a denominator at least 2d. We give a new algorithm that shows that this is also sufficient.

Automated summary

This research demonstrates that finding a maximal fractional matching in distributed graph algorithms requires the use of fine-grained fractional values, and gives a specific characterization of the small value requirements, with a denominator of at least 2d. It also provides a new algorithm to meet these requirements.