Node and Edge Averaged Complexities of Local Graph Problems
share
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 Ω(min{logΔ/loglogΔ,√(log n/loglog n)}). 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(√(loglog 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 Ω(min{logΔ/loglogΔ,√(log n/loglog n)}), 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).
READ FULL TEXT