Parallel greedy matching keeps vertex connections stable in random graphs
Degree Stability of Parallel Greedy Matching in Random Graphs
Discrete MathematicsData Structures and Algorithms
Summary
The paper looks at a process where points in a random network try to pair up with neighbors each round, removing those matched pairs from the network. The authors show that even after many rounds, points still keep many of their initial connections, meaning the network remains well connected for a long time. This stability helps match a consistent number of points each round. Their work uses careful mathematical tools to track how each point’s connections shrink over time instead of just looking at overall trends.
What this means in practice
- •For network engineers: Improve design and analysis of distributed algorithms that find matches or pairings in large, random-like networks by ensuring vertex connection stability over many rounds.
- •For distributed systems developers: Develop more predictable parallel matching protocols for resource allocation in networks by leveraging the proven degree stability in random graph models.
Tested on simulated data.
Authors
Vishvajeet N, Shrinidhi Teganahally Sridhara
Abstract
We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.