Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS

This paper improves and in two cases nearly settles, up to logarithmically lower order factors, the deterministic complexity of some of the most central problems in distributed graph algorithms, which have been studied for over three decades: • Near-Optimal Network Decomposition: We present a deterministic distributed algorithm that computes a network decomposition in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(\log^{2}n)$</tex> rounds with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> diameter and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log n)$</tex> colors. This round complexity is near-optimal in the following sense: even given an ideal network decomposition, using it (in the standard way) requires round complexity equal to the product of diameter and number of colors, and that is known to be <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde \Omega(\log^{2}n)$</tex>. We find this near-optimality remarkable, considering the rarity of optimal deterministic distributed algorithms and that for network decomposition, even the first polylogarithmic round algorithm was achieved only recently, by Rozhon and Ghaffari [STOC 2020], after three decades. • Near-Optimal Ruling Set: We present a deterministic distributed algorithm that computes an O(log log n) ruling set—i.e., an independent set such that each node is within its O(log log n) distance—in O(log n) rounds. This is an exponential improvement on the O(log n) ruling set of Awerbuch, Goldberg, Luby, and Plotkin [FOCS'89], while almost matching their O(log n) round complexity. Our result's round complexity nearly matches the (log n) lower bound of Balliu, Brandt, Kuhn, and Olivetti [STOC 2022] that holds for any poly(log log n) ruling set. • Improved Maximal Independent Set (MIS): We present a deterministic distributed algorithm for computing an MIS in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(\log^{5/3}n)$</tex> rounds. This improves on the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(\log^{2}n)$</tex> complexity achieved by Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary for any method based on network decomposition. By known reductions, the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(\log^{5/3}n)$</tex> round complexity also applies to deterministic algorithms for maximal matching, <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta+1$</tex> vertex coloring, and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(2\Delta-1)$</tex> edge coloring. Also, via the shattering technique, the improvement spreads also to randomized complexities of these problems, e.g., the new state-of-the-art randomized complexity of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta+1$</tex> vertex coloring is now <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}$</tex> ((log log <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> )5/3).