We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with k colours, there is a trivial greedy algorithm that finds a maximal matching in k-1 synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: if A is a deterministic distributed algorithm that finds a maximal matching in anonymous, k-edge-coloured graphs, then there is a worst-case input in which the running time of A is at least k1 rounds. If we focus on graphs of maximum degree Δ, it is known that a maximal matching can be found in O(Δ+ log* k) rounds, and prior work implies a lower bound of Ω(polylog(Δ) + log* k) rounds. Our work closes the gap between upper and lower bounds: the complexity is Θ(Δ+ log* k) rounds. To our knowledge, this is the first linear-in-Δ lower bound for the distributed complexity of a classical graph problem.
Some @math upper bounds are known for graph problems. For example, good approximations of fractional matchings can be found in @math rounds @cite_12 ; however, this does not seem to yield a deterministic @math -time algorithm for any of the above problems. Ha 'n ''s @cite_7 algorithm finds a maximal matching in @math rounds, avoiding the linear dependence on @math ; however, it comes at the cost of a non-optimal dependence on @math .
@cite_7 @cite_12
2011595776 1998137177
By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in @math O(Δ) rounds, independently of @math n; here @math Δ is the maximum degree of the graph and @math n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in @math o(Δ) rounds, independently of @math n. Our work gives the first linear-in- @math Δ lower bound for a natural graph problem in the standard @math LOCAL model of distributed computing--prior lower bounds for a wide range of graph problems have been at best logarithmic in @math Δ. We present a simple distributed @math -approximation algorithm for maximum weight independent set (MaxIS) in the @math model which completes in @math rounds, where @math is the maximum degree, @math is the number of rounds needed to compute a maximal independent set (MIS) on @math , and @math is the maximum weight of a node. Whether our algorithm is randomized or deterministic depends on the MIS algorithm used as a black-box. Plugging in the best known algorithm for MIS gives a randomized solution in @math rounds, where @math is the number of nodes. We also present a deterministic @math -round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a @math -approximation for maximum weight matching without incurring any additional round penalty in the @math model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of for which we describe a mechanism that allows the simulation to run in the @math model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to ( @math ) allows us to devise a distributed algorithm requiring @math rounds for any constant @math . For the unweighted case, we can even obtain a @math -approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on @math . This paper addresses the cornerstone family of in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the @math nodes can only send @math -bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. Our techniques give a deterministic maximal independent set (MIS) algorithm in the CONGEST model, where the communication graph is identical to the input graph, in @math rounds, where @math is the diameter of the graph. The best known running time in terms of @math alone is @math , which is super-polylogarithmic, and requires large messages. For the CONGEST model, the only known previous solution is a coloring-based @math -round algorithm, where @math is the maximal degree in the graph. On the way to obtaining the above, we show that in the model, which allows all-to-all communication, there is a deterministic MIS algorithm that runs in @math rounds. , where @math is the maximum degree. When @math , the bound improves to @math and holds also for @math -coloring. In addition, we deterministically construct a @math -spanner with @math edges in @math rounds. For comparison, in the more stringent CONGEST model, the best deterministic algorithm for constructing a @math -spanner with @math edges runs in @math rounds. We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset linear programming relaxation for this problem. For directed graphs and @math -out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node @math in the solution is at most @math , where @math is the degree upper bound on @math . For undirected graphs and element-connectivity requirements with maximum connectivity requirement @math , our algorithm computes a solution that is a @math -approximation on the cost, and the degree of each node @math in the solution is at most @math . These ratios improve the previous @math -approximation on the cost and @math -approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected $k...