Title: Distributed Strong Diameter Network Decomposition.

Authors: Michael Elkin and Ofer Neiman.

Abstract:

For a pair of positive parameters $D,\chi$, a partition $\cP$ of the vertex set $V$ of an $n$-vertex graph $G = (V,E)$ into disjoint clusters 
of diameter at most $D$ each is called a {\em $(D,\chi)$ network decomposition}, if the supergraph $\cG(\cP)$, obtained by contracting each of 
the clusters of $\cP$, can be properly $\chi$-colored.
The decomposition $\cP$ is said to be {\em strong} (resp., {\em weak}) if each of the clusters has strong (resp., weak) diameter at most $D$, 
i.e., if for every cluster $C \in \cP$ and every two vertices $u,v \in C$, the distance between them in the induced graph $G(C)$ of $C$ 
(resp., in $G$) is at most $D$.

Network decomposition is a powerful construct, very useful in distributed computing and beyond. It was introduced by Awerbuch \etal \cite{AGLP89} 
in the end of the eighties.
These authors showed that strong $(2^{O(\sqrt{\log n\log\log n})},2^{O(\sqrt{\log n\log\log n})})$ network decompositions can be computed in
$2^{O(\sqrt{\log n\log\log n})}$ distributed time.
Their result was improved at the beginning of nineties by Panconesi and Srinivasan \cite{PS92}, who showed that $2^{O(\sqrt{\log n\log\log n})}$ 
in all the three expressions can be replaced  by $2^{O(\sqrt{\log n})}$. Around the same time Linial and Saks \cite{LS93}  devised an ingenious 
randomized algorithm that constructs {\em weak} $(O(\log n),O(\log n))$ network decompositions in $O(\log^2 n)$ time. It was however open till 
now if {\em strong} network decompositions with both parameters $2^{o(\sqrt{\log n})}$ can be constructed in distributed $2^{o(\sqrt{\log n})}$ time.

In this paper we answer this long-standing open question in the affirmative, and show that strong $(O(\log n),O(\log n))$ network decompositions 
can be computed in $O(\log^2 n)$ time. We also present a tradeoff between parameters of our network decomposition.
Our work is inspired by and relies on the ``shifted shortest path approach", due to Blelloch \etal \cite{BGKMPT11}, and Miller \etal \cite{MPX13}. 
These authors developed this approach for PRAM algorithms for padded partitions. We adapt their approach to network decompositions in the distributed 
model of computation.