论文标题
真正紧密的$δ$界限用于两部分最大匹配和变体
Truly Tight-in-$Δ$ Bounds for Bipartite Maximal Matching and Variants
论文作者
论文摘要
在最近的突破结果中，Balliu等人。 [focs'19]被证明是确定性的$ω（\ min（δ，\ log n /\ log \ log n））$ - 圆形和一个随机的$ω（\ min（\ tu \ log \ log \ log n /\ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log n））$ - 在$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n的复杂性中的较低范围 - 这两个下限均无渐进地紧密，这是最大程度$δ$的函数。 我们为$δ$提供真正的紧密界限，以使两部分最大匹配的复杂性和许多天然变体的复杂性，直至添加剂常数。 作为副产品，我们的结果得出了Balliu等人的证明的简化版本。 我们表明，我们的结果可以通过有限的自动圆形消除来获得，这是Brandt [PODC'19]最近的自动圆形消除技术的一种版本，从实际的角度来看，它特别适合自动化。 在这种情况下，我们的工作可以看作是迈向本地模型中下限自动化的又一步。
In a recent breakthrough result, Balliu et al. [FOCS'19] proved a deterministic $Ω(\min(Δ,\log n /\log \log n))$-round and a randomized $Ω(\min(Δ,\log \log n/\log \log \log n))$-round lower bound for the complexity of the bipartite maximal matching problem on $n$-node graphs in the LOCAL model of distributed computing. Both lower bounds are asymptotically tight as a function of the maximum degree $Δ$. We provide truly tight bounds in $Δ$ for the complexity of bipartite maximal matching and many natural variants, up to and including the additive constant. As a by-product, our results yield a considerably simplified version of the proof by Balliu et al. We show that our results can be obtained via bounded automatic round elimination, a version of the recent automatic round elimination technique by Brandt [PODC'19] that is particularly suited for automatization from a practical perspective. In this context, our work can be seen as another step towards the automatization of lower bounds in the LOCAL model.
