  Network decomposition is a central tool in distributed graph algorithms. We
present two improvements on the state of the art for network decomposition,
which thus lead to improvements in the (deterministic and randomized)
complexity of several well-studied graph problems.
  - We provide a deterministic distributed network decomposition algorithm with
$O(\log^5 n)$ round complexity, using $O(\log n)$-bit messages. This improves
on the $O(\log^7 n)$-round algorithm of Rozho\v{n} and Ghaffari [STOC'20],
which used large messages, and their $O(\log^8 n)$-round algorithm with $O(\log
n)$-bit messages. This directly leads to similar improvements for a wide range
of deterministic and randomized distributed algorithms, whose solution relies
on network decomposition, including the general distributed derandomization of
Ghaffari, Kuhn, and Harris [FOCS'18].
  - One drawback of the algorithm of Rozho\v{n} and Ghaffari, in the
$\mathsf{CONGEST}$ model, was its dependence on the length of the identifiers.
Because of this, for instance, the algorithm could not be used in the
shattering framework in the $\mathsf{CONGEST}$ model. Thus, the state of the
art randomized complexity of several problems in this model remained with an
additive $2^{O(\sqrt{\log\log n})}$ term, which was a clear leftover of the
older network decomposition complexity [Panconesi and Srinivasan STOC'92]. We
present a modified version that remedies this, constructing a decomposition
whose quality does not depend on the identifiers, and thus improves the
randomized round complexity for various problems.
