论文标题
分布式最大匹配验证
Distributed Maximum Matching Verification in CONGEST
论文作者
论文摘要
我们在标准分布式设置中研究了最大的基数匹配问题，其中给定$ n $ n $ node网络图的节点$ v $ $ g =（v，e）$在同步回合中的边缘$ e $上通信。更具体地说，我们考虑了分布式的交货模型，在每个回合中，$ g $的每个节点都可以向其每个邻居发送$ o（\ log n）$ - 位消息。我们表明，对于每张图$ g $和一个匹配的$ m $ $ g $，有一个随机的联合算法来验证$ m $是$ g $的最大匹配时间$ o（| m |）$（| m |）$（| m |）$（d + \ ell）$，在$ o（d + \ ell）中，$ d $是$ g $ of $ g $和$ g $和$ f e el $ \ ell $ \ ell \ ell the part part的prot part。我们希望我们的算法构成开发拥塞算法以计算时间$ \ tilde {o}（s^*）$的最大匹配的重要一步，其中$ s^*$是最大匹配的大小。
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 + \ell)$, where $D$ is the diameter of $G$ and $\ell$ 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 $\tilde{O}(s^*)$, where $s^*$ is the size of a maximum matching.
