Node and edge averaged complexities of local graph problems

We continue the recently started line of work on the distributed node-averaged complexity of distributed graph algorithms. 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 of the central distributed symmetry breaking problems and provide the following results (among others). As our main result, we show that 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 lower bound by Kuhn, Moscibroda, and Wattenhofer [JACM’16]. As a side result, we obtain that the worst-case randomized round complexity for computing an MIS in trees is also Ω (min{logΔ/loglogΔ,√(log n/loglog n)} ) —this essentially answers open problem 11.15 in the book by Barenboim and Elkin and resolves the complexity of MIS on trees up to an O(√(loglog n)) factor. We also show that, perhaps surprisingly, a minimal relaxation of MIS, which is the same as (2, 1)-ruling set, to the (2, 2)-ruling set problem drops the randomized node-averaged complexity to O (1). 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) .