A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

Abstract

We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs $G=(V,E)$ using only a few shared random bits. Specifically, in the $\congest$ model, we compute a matching whose expected number of blocking pairs is at most $\epsilon |E|$ in $O\left(\frac{\log (1/\epsilon )}{{\epsilon }^4}\right)$ rounds using $O\left(\log (1/\epsilon )\right)$ shared random bits. Thus, for every constant $\epsilon >0$, the round complexity is $O(1)$, independent of the number of vertices and the maximum degree. Previous algorithms achieve constant round complexity only for bounded-degree or almost-regular graphs; on general graphs, their round complexity depends polylogarithmically on $n$. Our main technical idea is a degree-guarded freezing rule that allows widely varying degrees to be handled by a single global charging argument, avoiding the $\Theta (\log n)$ successive degree thresholds used in previous work. The shared random bits are used only to select a common random output iteration. As consequences, we obtain an $O\left(\frac{\log (1/\epsilon )}{{\epsilon }^4}+\frac{\log n}{\epsilon }\right)$-round $\congest$ algorithm without pre-shared randomness, via a low-diameter decomposition, and an $O\left(\frac{\log (1/\epsilon )}{{\epsilon }^4}\right)$-round algorithm in the fully-scalable Massively Parallel Computation ($\mpc$) model with linear total memory.