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.
It is easy to come up with an artificial problem with the complexity of @math , but so far no such tight results are known for classical graph problems such as maximal matchings. The lower-bound result by Kuhn and Wattenhofer @cite_3 comes close, but it only applies to a restricted family of algorithms.
@cite_3
2011595776 2006040238 2091660728 1727475799
We show that maximal matchings can be computed deterministically in O(log4 n) rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a nontrivial graph structure, and the only "classical" one, which can be computed distributively in polylogarithmic time without recourse to randomization. We give simple, deterministic, distributed algorithms for computing maximal matchings, maximal independent sets and colourings. We show that edge colourings with at most 2Δ-1 colours, and maximal matchings can be computed within O(log* n + Δ) deterministic rounds, where Δ is the maximum degree of the network. We also show how to find maximal independent sets and (Δ + 1)-vertex colourings within O(log* n + Δ2) deterministic rounds. All hidden constants are very small and the algorithms are very simple. We present a new randomized algorithm for finding a maximum matching in H-minor free graphs. For every fixed H, our algorithm runs in O(n3ω (ω+3)) For graphs with bounded genus, which are special cases of H-minor free graphs, we present a randomized algorithm for finding a maximum matching in O(nω 2) We also present a deterministic algorithm with a running time of O(n1+ω 2) In his seminal paper, Grover points out the prospect of faster solutions for an NP-complete problem like SAT. If there are n variables, then an obvious classical deterministic algorithm checks out all 2n truth assignments in about 2n steps, while his quantum search algorithm can find a satisfying truth assignment in about 2n 2 steps. For several NP-complete problems, many sophisticated classical algorithms have been designed. They are still exponential, but much faster than the brute force algorithms. The question arises whether their running time can still be decreased from T(n) to O (√T(n)) by using a quantum computer. Isolated positive examples are known, and some speed-up has been obtained for wider classes. Here, we present a simple method to obtain the full T(n) to O(√T(n)) speed-up for most of the many nontrivial exponential time algorithms for NP-hard problems. The method works whenever the widely used technique of recursive decomposition is employed. This included all currently known algorithms for which such a speedup has not yet been known.