In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an n-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in Õ(n) space a proper O(Δ²)-coloring w.h.p. (here Δ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] showed that it is possible to deterministically compute an O(Δ²/s)-coloring in O(ns) space. However, none of the improvements succeeded in reducing the number of colors to O(Δ^{2-ε}) while keeping the same space bound of Õ(n). In particular, no progress was made on the question of whether computing an O(Δ)-coloring is possible with roughly O(n) space, which was stated in [Behnezhad et al., 2019] to be an interesting open problem. In this paper we bypass the quadratic bound by presenting a new randomized Õ(n)-space algorithm that uses Õ(Δ^{1.5}) colors.

We improve the time complexity of the single-source shortest path problem for weighted directed graphs (with non-negative integer weights) in the Broadcast CONGEST model of distributed computing. For polynomially bounded edge weights, the state-of-the-art algorithm for this problem requires [EQUATION] rounds [Forster and Nanongkai, FOCS 2018], which is quite far from the known lower bound of [EQUATION] rounds [Elkin, STOC 2014]; here D is the diameter of the underlying network and n is the number of vertices in it. For the approximate version of this problem, Forster and Nanongkai [FOCS 2018] obtained an upper bound of [EQUATION], and stated that achieving the same bound for the exact case remains a major open problem.

In this paper, we consider distributed coloring for planar graphs with a small number of colors. Our main result is an optimal (up to a constant factor) O(log n) time algorithm for 6-coloring planar graphs. Our algorithm is based on a novel technique that in a nutshell detects small structures that can be easily colored given a proper coloring of the rest of the vertices and removes them from the graph until the graph contains a small enough number of edges. We believe this technique might be of independent interest. In addition, we present a lower bound for 4-coloring planar graphs that essentially shows that any algorithm (deterministic or randomized) for 4-coloring planar graphs requires Ω(n) rounds. We therefore completely resolve the problems of 4-coloring and 6-coloring for planar graphs in the LOCAL model.

In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CONGEST model. We focus on the case where the diameter D of the underlying network is constant. We show that for the case where D = 1 there is, quite surprisingly, a very simple algorithm that solves the reachability problem in 1(!) round. In contrast, for networks with D = 2, we show that any distributed algorithm (possibly randomized) for this problem requires Omega(sqrt{n/ log{n}}) rounds. Our results therefore completely resolve (up to a small polylog factor) the complexity of the single-source reachability problem for a wide range of diameters. Furthermore, we show that when D = 1, it is even possible to get an almost 3 - approximation for the all-pairs shortest path problem (for directed unweighted graphs) in just 2 rounds. We also prove a stronger lower bound of Omega(sqrt{n}) for the single-source shortest path problem for unweighted directed graphs that holds even when the diameter of the underlying network is 2. As far as we know this is the first lower bound that achieves Omega(sqrt{n}) for this problem.