We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: -- We present a @math round deterministic algorithm for @math -edge-coloring, where @math denotes the maximum degree. Modulo the @math factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of @math -edge-coloring in @math rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. -- We show that sinkless orientation---i.e., orienting edges such that each node has at least one outgoing edge---on @math -regular graphs can be solved in @math rounds randomized and in @math rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for @math -coloring @math -regular trees. -- We present a randomized @math round algorithm for orienting @math -arboricity graphs with maximum out-degree @math . This can be also turned into a decomposition into @math forests when @math and into @math pseduo-forests when @math . Obtaining an efficient distributed decomposition into less than @math forests was stated as the 10th open problem in the book by Barenboim and Elkin.
See thm:directedDegreeSplit and lem:forestDecomp for the formal statements. We note that efficient distributed orientation with out-degree less than @math had remained open. The best previously known results were as follows: an orientation with out-degree at most @math in @math rounds and an orientation with out-degree at most @math in @math rounds, both due to Barenboim and Elkin @cite_23 . The same authors state the closely-related problem of efficient distributed decomposition into less than @math forests as the 10th open problem in their book [Section 11] barenboim2013monograph .
@cite_23
2534944111 2951615666 2552279664 2487418934
We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: • We present a poly log n round deterministic algorithm for (2Δ−1)·(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e.g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ − 1) · poly log Δ-edge-coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. • We show that sinkless orientation---i.e., orienting edges such that each node has at least one out-going edge---on Δ-regular graphs can be solved in O(logΔ log n) rounds randomized and in O(logΔ n) rounds deterministically. These prove the corresponding lower bounds by [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of for Δ-coloring Δ-regular trees. • We present a randomized O(log4 n) round algorithm for orienting a-arboricity graphs with maximum out-degree a(1 + e). This can be also turned into a decomposition into a(1 + e) forests when a = Ω(log n) and into a(1 + e) pseduo-forests when a = o(log n). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin. We show that any randomised Monte Carlo distributed algorithm for the Lov 'asz local lemma requires @math communication rounds, assuming that it finds a correct assignment with high probability. Our result holds even in the special case of @math , where @math is the maximum degree of the dependency graph. By prior work, there are distributed algorithms for the Lov 'asz local lemma with a running time of @math rounds in bounded-degree graphs, and the best lower bound before our work was @math rounds [ 2014]. 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. Abstract A partition ( C 1 , C 2 , … , C q ) of G = ( V , E ) into clusters of strong (respectively, weak) diameter d , such that the supergraph obtained by contracting each C i is l -colorable is called a strong (resp., weak) ( d , l ) -network-decomposition. Network-decompositions were introduced in a seminal paper by Awerbuch, Goldberg, Luby and Plotkin in 1989. showed that strong ( d , l ) -network-decompositions with d = l = exp ⁡ O ( log ⁡ n log ⁡ log ⁡ n ) can be computed in distributed deterministic time O ( d ) . Even more importantly, they demonstrated that network-decompositions can be used for a great variety of applications in the message-passing model of distributed computing. The result of was improved by Panconesi and Srinivasan in 1992: in the latter result d = l = exp ⁡ O ( log ⁡ n ) , and the running time is O ( d ) as well. In another remarkable breakthrough Linial and Saks (in 1992) showed that weak ( O ( log ⁡ n ) , O ( log ⁡ n ) ) -network-decompositions can be computed in distributed randomized time O ( log 2 ⁡ n ) . Much more recently Barenboim (2012) devised a distributed randomized constant-time algorithm for computing strong network decompositions with d = O ( 1 ) . However, the parameter l in his result is O ( n 1 2 + ϵ ) . In this paper we drastically improve the result of Barenboim and devise a distributed randomized constant-time algorithm for computing strong ( O ( 1 ) , O ( n ϵ ) ) -network-decompositions. As a corollary we derive a constant-time randomized O ( n ϵ ) -approximation algorithm for the distributed minimum coloring problem, improving the previously best-known O ( n 1 2 + ϵ ) approximation guarantee. We also derive other improved distributed algorithms for a variety of problems. Most notably, for the extremely well-studied distributed minimum dominating set problem currently there is no known deterministic polylogarithmic-time algorithm. We devise a deterministic polylogarithmic-time approximation algorithm for this problem, addressing an open problem of Lenzen and Wattenhofer (2010).