  Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and
Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph
algorithms. We present an improved deterministic distributed algorithm for
constructing network decompositions of power graphs using small messages, which
improves upon the algorithm of Ghaffari and Kuhn [DISC'18]. In addition, we
provide a randomized distributed network decomposition algorithm, based on our
deterministic algorithm, with failure probability exponentially small in the
input size that works with small messages as well. Compared to the previous
algorithm of Elkin and Neiman [PODC'16], our algorithm achieves a better
success probability at the expense of its round complexity, while giving a
network decomposition of the same quality. As a consequence of the randomized
algorithm for network decomposition, we get a faster randomized algorithm for
computing a Maximal Independent Set, improving on a result of Ghaffari
[SODA'19]. Other implications of our improved deterministic network
decomposition algorithm are: a faster deterministic distributed algorithms for
constructing spanners and approximations of distributed set cover, improving
results of Ghaffari, and Kuhn [DISC'18] and Deurer, Kuhn, and Maus [PODC'19];
and faster a deterministic distributed algorithm for constructing neighborhood
covers, resolving an open question of Elkin [SODA'04].
