2020/02/18 by Ahmadi, Mohamad, Kuhn, Fabian · 2 citations
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2002.07649
We study the maximum cardinality matching problem in a standard distributed setting, where the nodes V of a given n-node network graph G=(V,E) communicate over the edges E in synchronous rounds. More specifically, we consider the distributed CONGEST model, where in each round, each node of G can send an O(log n)-bit message to each of its neighbors. We show that for every graph G and a matching M of G, there is a randomized CONGEST algorithm to verify M being a maximum matching of G in time O(|M|) and disprove it in time O(D + ℓ), where D is the diameter of G and ℓ is the length of a shortest augmenting path. We hope that our algorithm constitutes a significant step towards developing a CONGEST algorithm to compute a maximum matching in time O(s^*), where s^* is the size of a maximum matching.