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 $O(1)$ rounds in bounded-degree graphs. However, all prior $O(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, \frac12, 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 $2^d$. We give a new algorithm that shows that this is also sufficient.
翻译:根据先前的工作,已知任何找到最大匹配值的分布式图表算法都需要$\Omega(\log<unk> n) $$(log<unk> n) 的通信圆圈,同时有可能在约束度图形中找到以美元(1美元) 圆圆圆的最小分数匹配值。然而,所有用于最大分数匹配的先前的美元(1美元) 圆圆算法都任意使用细微的分数值。 特别是,它们都找不到半整数的解算法, 仅使用$0, \frac12, 1 美元。 我们显示, 使用精细分数分数的分数值是必要的, 此外, 我们完整地描述需要多少值: 如果我们考虑最高分数 $\Delta = 2d$ 的最大分数匹配值, 以及任何仅依靠$T (\Delta) 圆复杂度的分布式图表算法, 仅依靠$\Delta 美元, 且不依赖$n $, 我们证明该算法必须使用分数值至少为 $2美元。 我们给出了一个新的算法。</s>