We study the replacement paths problem in the CONGEST model of distributed computing. Given an s-t shortest path P, the goal is to compute, for every edge e in P, the shortest-path distance from s to t avoiding e. For unweighted directed graphs, we establish the tight randomized round complexity bound for this problem as [EQUATION] by showing matching upper and lower bounds. Our upper bound extends to (1 + ϵ)-approximation for weighted directed graphs. Our lower bound applies even to the second simple shortest path problem, which asks only for the smallest replacement path length. These results improve upon the very recent work of Manoharan and Ramachandran (SIROCCO 2024), who showed a lower bound of [EQUATION] and an upper bound of [EQUATION], where hst is the number of hops in the given s-t shortest path P.

In the context of communication complexity, we explore protocols for graph coloring, focusing on the vertex and edge coloring problems in n-vertex graphs G with a maximum degree Δ. We consider a scenario where the edges of G are partitioned between two players.

Recently, Akbari et al. (ICALP 2023) studied the locality of graph problems in distributed, sequential, dynamic, and online settings from a unified point of view. They designed a novel O(log n)-locality deterministic algorithm for proper 3-coloring bipartite graphs in the Online-LOCAL model. In this work, we establish the optimality of the algorithm by showing a tight deterministic Ω (log n) locality lower bound, which holds even on grids. To complement this result, we have the following additional results: