We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and or more general than their known counterparts. The common denominator of these results is a deterministic distributed rounding method for certain linear programs, which is the first such rounding method, to our knowledge. A sampling of our end results is as follows. -- An @math -round deterministic distributed algorithm for computing a maximal matching, in @math -node graphs with maximum degree @math . This is the first improvement in about 20 years over the celebrated @math -round algorithm of Hanckowiak, Karonski, and Panconesi [SODA'98, PODC'99]. -- A deterministic distributed algorithm for computing a @math -approximation of maximum matching in @math rounds. This is exponentially faster than the classic @math -round @math -approximation of Panconesi and Rizzi [DIST'01]. With some modifications, the algorithm can also find an @math -maximal matching which leaves only an @math -fraction of the edges on unmatched nodes. -- An @math -round deterministic distributed algorithm for computing a @math -approximation of a maximum weighted matching, and also for the more general problem of maximum weighted @math -matching. These improve over the @math -round @math -approximation algorithm of Panconesi and Sozio [DIST'10], where @math denotes the maximum normalized weight.
Ghaffari, Kuhn, and Maus @cite_16 recently proved a -type result which shows that for efficient deterministic distributed graph algorithms is deterministically fractional values to integral values while approximately preserving some linear constraints. Stating this result in full generality requires some definitions. See @cite_16 for the precise statement. To put it more positively, if we find an efficient deterministic method for rounding, we would get efficient algorithms for essentially all the classic local graph problems, including the four mentioned above. Our results become more instructive when viewed in this context. The common denominator of our results is a deterministic distributed method which allows us to round fractional matchings to integral matchings. This can be more generally seen as rounding the fractional solutions of a special class of (LPs) to integral solutions. To the best of our knowledge, this is the first known method. We can now say that
@cite_16
2552279664
This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2O(√logn). Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in logn rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in logn rounds in the LOCAL model. Perhaps most surprisingly, we show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values. In addition, our formal framework also allows us to develop polylogarithmic-time randomized distributed algorithms in a simpler way. As a result, we provide a polylog-time distributed approximation scheme for arbitrary distributed covering and packing integer linear programs.