论文标题
节点和边缘平均本地图问题的复杂性
Node and Edge Averaged Complexities of Local Graph Problems
论文作者
论文摘要
在图$ g =（v，e）$上运行的分布式算法的节点平均复杂性是$ g $的节点$ v $完成其计算并提交输出的时间的平均值。我们研究了一些分布式对称性破坏问题的节点平均复杂性，并提供以下结果（以及其他结果）： - 计算最大独立集（MIS）的随机节点平均复杂性（MIS）中的最大程度$δ$的图形至少为$ω\ big（\ min \ big \ big \ frac {\ frac {\logΔ} n}} \ big \} \ big）$。通过对众所周知的下限[JACM'16]的新型改编而获得这种结合。作为综上的结果，我们为计算树木中的错误的最坏情况随机圆形复杂性获得了相同的下限 - 这本质上回答了Barenboim和Elkin书中的开放问题11.15，并解决了$ O（\ sqrt {\ sqrt {\ log log \ log \ log \ n}）的树木上误差的复杂性。我们还表明，$（2,2）$ - 统治集，这是MIS的最小放松，具有$ O（1）$随机节点平均复杂性。 - 对于最大匹配，我们表明，虽然随机节点积极的复杂性为$ω\ big（\ min \ big \ {\ frac {\logΔ} {\logδ} {\ log \logδ}，\ sqrt {\ sqrt {\ frac {\ frac {\ log n} {\ log log \ log \ log \ log \ big边缘平均复杂性为$ O（1）$。此外，我们表明，最大匹配的确定性边缘平均复杂性为$ O（\ log^2δ+ \ log^* n）$，最大匹配的确定性节点水平的复杂性为$ O（\ log^3Δ+ \ log^* n）$。 - 最后，我们考虑了计算图形无沥青方向的问题。即使在有界度图上，该问题的确定性最差案例复杂性也为$θ（\ log n）$。我们表明，可以通过节点平均复杂性$ O（\ log^* n）$确定性解决问题，同时将最差的复杂性保留在$ O（\ log n）$中。
The node-averaged complexity of a distributed algorithm running on a graph $G=(V,E)$ is the average over the times at which the nodes $V$ of $G$ finish their computation and commit to their outputs. We study the node-averaged complexity for some distributed symmetry breaking problems and provide the following results (among others): - The randomized node-averaged complexity of computing a maximal independent set (MIS) in $n$-node graphs of maximum degree $Δ$ is at least $Ω\big(\min\big\{\frac{\logΔ}{\log\logΔ},\sqrt{\frac{\log n}{\log\log n}}\big\}\big)$. This bound is obtained by a novel adaptation of the well-known KMW lower bound [JACM'16]. As a side result, we obtain the same lower bound for the worst-case randomized round complexity for computing an MIS in trees -- this essentially answers open problem 11.15 in the book of Barenboim and Elkin and resolves the complexity of MIS on trees up to an $O(\sqrt{\log\log n})$ factor. We also show that, $(2,2)$-ruling sets, which are a minimal relaxation of MIS, have $O(1)$ randomized node-averaged complexity. - For maximal matching, we show that while the randomized node-averaged complexity is $Ω\big(\min\big\{\frac{\logΔ}{\log\logΔ},\sqrt{\frac{\log n}{\log\log n}}\big\}\big)$, the randomized edge-averaged complexity is $O(1)$. Further, we show that the deterministic edge-averaged complexity of maximal matching is $O(\log^2Δ+ \log^* n)$ and the deterministic node-averaged complexity of maximal matching is $O(\log^3Δ+ \log^* n)$. - Finally, we consider the problem of computing a sinkless orientation of a graph. The deterministic worst-case complexity of the problem is known to be $Θ(\log n)$, even on bounded-degree graphs. We show that the problem can be solved deterministically with node-averaged complexity $O(\log^* n)$, while keeping the worst-case complexity in $O(\log n)$.
