We show that the (degree + 1)-list coloring problem can be solved deterministically in O(D · log n · log2 Δ) rounds in the CONGEST model, where D is the diameter of the graph, n the number of nodes, and Δ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [49], this implies the first efficient (i.e., poly log n-time) deterministic CONGEST algorithm for the (Δ + 1)-coloring and the (degree + 1)-list coloring problem. Previously the best known algorithm required [EQUATION] rounds and was not based on network decompositions.

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(logn) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective `old` neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds.

One of the fundamental open problems in the area of distributed graph algorithms is whether randomization is needed for efficient symmetry breaking. While there are poly log n-time randomized algorithms for all the classic symmetry breaking problems, for many of them, the best deterministic algorithms are almost exponentially slower. The following basic local splitting problem, which is known as weak splitting, takes a central role in this context: Each node of a graph G=(V,E) has to be colored red or blue such that each node of sufficiently large degree has at least one neighbor of each color. Ghaffari, Kuhn, and Maus [STOC '17] showed that this seemingly simple problem is complete w.r.t. the above fundamental open question in the following sense: If there is an efficient poly log n-time determinstic distributed algorithm for weak splitting, then there is such an algorithm for all locally checkable graph problems for which an efficient randomized algorithm exists. We investigate the distributed complexity of weak splitting and some closely related problems and we in particular obtain the following results:

We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. We require two properties from our algorithms: (1) They should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and they coincide with the definition of the static graph problem if no topological change appeared recently. (2) If a constant neighborhood around some part of the graph is stable during an interval, the algorithms quickly converge to a solution for this part of the graph that remains unchanged throughout the interval. We demonstrate our generic framework with two classic distributed graph, namely (degree+1)-vertex coloring and maximal independent set (MIS).