BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1358
ENTRY:: 1993-10-14
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: On the Complexity of Distributed Network Decomposition
AUTHOR:: Panconesi, Alessandro 
AUTHOR:: Srinivasan, Aravind
DATE:: June 1993
PAGES:: 15
ABSTRACT::
In this paper, we improve the bounds for computing a network decomposition, 
which is a basic notion in distributed graph algorithms, distributively and 
deterministically. Our algorithm computes an 
$(n^{\epsilon(n)},(n^{\epsilon(n)})$-decomposition in $O(n^{\epsilon(n)})$ 
time, where $\epsilon(n)=O(1/ \sqrt{\log n})$.

As a corollary we obtain improved deterministic bounds for distributively 
computing several graph structures such as maximal independent sets and 
$\Delta$-vertex colorings.

We also show that the class of graphs $\cal G$ whose maximum degree is 
$O(n^{\delta(n)})$, where $\delta(n)=O(1/\log \log n)$, is complete for the 
task of computing a near-optimal decomposition, i.e., a 
$(\log n \log n)$-decomposition, in $O($polylog$(n))$ time. This is a 
corollary of a more general characterization, which pinpoints the weak points 
of existing network decomposition algorithms. Completeness is to be intended 
in the following sense: if we have an algorithm $\cal A$ that computes an 
optimal decomposition in $O($polylog$(n))$ time for graphs in $\cal G$, then 
we can compute an optimal decomposition in $O($polylog $(n))$ time for all 
graphs.
END:: CORNELLCS//TR93-1358
BODY::
On The Complexity of
Distributed Network Decomposition*
Alessandro Panconesi
Aravind Srinivasan
IR 93-1358
June1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
*A preliminary version of this paper appeared as a part of the paper `?lmproved
Distributed Algorithms for Coloring and Network Decomposition Problems", in the
Proceedings of the ACM Symposium on Theory of Computmg, pages 581-592,
1992.
This research was supported in part by NSF PYl award CCR-89-96272 with matching
support from UPS and Sun Microsystems.
On the Complexity of Distributed Network
Decomposition*t
Alessandro Panconesi & Aravind Srinivasan
Department of Computer Science
Cornell University, Ithaca NY 14853
Email: ?ap, srinJ?cs.coriie11.edu
May 3, 1993
Abstract
In this paper, we improve the bounds for computing a network decomposition, which is a
basic notion in distributed graph algorithms, distributively and deterministically. Our algo-
rithm computes an (nC(fl), n?(fl))?decomposition in o(n?n)) time, where c(n) =
As a corollary we obtain improved deterministic bounds for distributively computing
several graph structures such as maximal independent sets and A--Hvertex colorings.
We also show that the class of graphs g whose maximum degree is O(n6(?)), where
6(n) = 0(1/ log log n), is complete for the task of computing a near-optimal decomposition,
a (logn, logn)-decomposition, in O(polylog(n)) time. This is a corollary of a more
general characterization, which pinpoints the weak points of existing network decomposition
algorithms. Completeness is to be intended in the following sense: if we have an algorithm
A that computes an optimal decomposition in O(polylog(n)) time for graphs in g, then we
can compute an optimal decomposition in O(poi5rlog(n)) time for all graphs.
1			Introduction
In a distributed model of computation in which processors are connected by a given network
without any global memory, one of the central notions in studying the question of whether a
particular function can be computed efficiently is that of locality. Can each processor compute
its part of the output while communicating with only a small neighborhood of itself? Or is
it optimal to use the trivial algorithm in which an elected leader collects information about
the whole input, and then distributes the output in time proportional to the diameter of the
network? Linial has formalized these questions, and has proved tight lower bounds for some
graph problems [16].
Two important and inter--Hrelated problems in the distributed model are to compute a max-
imal independent set (MIS) and to compute a good vertex coloring of a network G, say a
(A + 1)--Hcoloring (A is the maximum degree of any vertex in G). An MIS delines a set of proces-
sors which can compute in parallel without interference, and a coloring is a partition of V into
A preliminary version of this paper appeared as a part of the paper Improved Distributed Algorithms
for Coloring and Network Decomposition Problems", in the Proceedings of the A CM Symposium on Theory of
Computing, pages 551--H592,1992.
tTliis research was supported in part by NSF PYl award CCR--H89--H96272 with matching support from UPS
and Sun Microsystems.
independent sets, thus defining a schedule for the processors to compute in parallel, without
interfering with their neighbors.
The reason for studying these problems is twofold. On one hand, they seem to be useful in
the context of synclironization and resource allocation problems. For example, vertex and edge
colorings are used to solve classical problems like the Dining Philosophers Problem of Dijkstra
[7, 20, 24], and computing a maximal independent set is an important primitive in many parallel
algoritlims [11, 10, 13, 12, 14, 15, 18]. On the other hand, studying these problems in the PRAM
model has proven extremely fruitful because it initiated the development of theoretical tools of
wide applicability e.g., the derandomization technique of conditional probabilities and the
theory of small probability spaces [6,18, 19, 21]
There are very simple distributed randomized algorithms of Alon, Babai & Itai and Luby
that compute an MIS and a (A + 1)--Hcoloring in O(logn) expected time [1, 18, 19]. While these
papers also show how to derandomize these algorithms in NC, it is an outstanding open question
whether the derandomization can be carried out in the distributed model.
In order to solve the MIS and related problems in the distributed model, Awerbuch, Gold-
berg, Luby & Plotkin introduced the notion of network decomposition (sometimes also called
cluster decomposition) [3]. Given a network C (V, E) and a partition of V into a set of clusters
C = tOil, the cluster graph 0c induced by C is the graph with vertex set V(Cc) = C and edge
set
E(Cc) = t(Oi, 0j) : i ? j, ?u E Ci ?v E Cj (u, v) ?
A (d(n), c(n))--Hdecomposition of 0 is a partition of V into a set of clusters C such that
o+ every 0[Ci], the subgraph induced by vertices in Ci, is connected and of O(d(n)) diameter,
and
o+ the cluster graph is vertex colored with O(c(n)) colors.
Problems like MIS and (A + 1)--Hcoloring can be solved in O(d(n) . c(n)) time, given a (d(n), c(n))-
decomposition of 0. The generic algorithm for such problems, given a cluster decomposition,
will iterate through the color classes, clusters of color 1 being processed first in parallel, clusters
of color 2 being processed next, and so on. Inside each cluster the trivial algorithm can be used:
the leader of the cluster (say the processor with highest ID) collects complete information on the
topology of the cluster, internally computes a solution, and sends the answer back to all vertices
in the cluster1. The bounds on the cluster diameter and the number of colors used, yield the
bound on the time complexity of this generic algorithm.
Network decomposition has also other interesting applications, mainly, but not exclusively,
in distributed computing [2, 3, 4, 5].
A decomposition with O(c(n)) = O(d(n)) = O(log n) is called near-optimal, since Linial &
Saks have exhibited families of graphs for which c(n)+d(n) > ?(1Jg01??g?) and c(n)d(n) > ?(log n)
for any (d(n), c(n))--Hdecomposition [17]. Linial & Saks showed how to compute a near-optimal
1This solution is mainly of theoretical interest because it might involve large message size and significant
internal computation.
2
decomposition in O(log2 n) expected time by using randomization, although they relax the
requirement that the G[Ci]'s be connected [17].
In this paper, we improve the bounds of Awerbuch, Goldberg, Luby & Plotkin for comput-
ing a network decomposition distributively and deterministically. We show how to compute a
(n?(n), n?(?))--Hdecomposition in 0(n?(?)) time, where e(n) = 0(1/?ogn) (as opposed to their
e(n) = 0(?gn/Vmogn)).
As a corollary of this improved network decomposition result we obtain improved determin-
istic bounds for computing an MIS, (A + 1)-coloring, and other graph problems.
We also show that the class of graphs q whose maximum degree is A --H 0(n?(?)), where
= 0(1/log log n), is complete for the task of computing an optimal decomposition in
O(polylog(n)) time. This is actually a corollary of a more general characterization. Complete-
ness is to be intended in the following sense: if we have an algorithm A that computes an
optimal decomposition in O(polylog(n)) time for graphs in ? then we can compute an optimal
decomposition in O(polylog(n)) time for all graphs. This completeness result characterizes the
class of graphs that are difficult to handle, and pinpoints the weak points of existing network
decomposition algorithms.
2 Definitions
A message-passing distributed network is an undirected graph G = (V, E) where vertices, or
nodes, correspond to processors and edges to bi--Hdirectional communication llnks. Each processor
has its unique ID. The network is synchronous, ?.e., computation takes place in a sequence of
rounds; in each round, each processor reads messages sent to it by its neighbors in the graph,
does any amount of local computation, and sends messages back to all of its neighbors. The
time complexity of a distributed algorithm, or protocol, is given by the number of rounds needed
to compute a given function.
The absence of a shared memory imposes a locality constraint in the following sense: if we
want a protocol to terminate within t rounds, every vertex can communicate with only the
vertices which are at a distance of at most t from it. This model is hence suited for studying the
complexity of a problem when communication is the bottleneck. In this model we do not charge
for local computation; in one round each processor is allowed to compute any function of its
current data. In our algorithms however, each processor will perform very simple computations.
In particular, each step can be simulated in 0(A) by a single processor or in constant time with
A processors, where A denotes the maximum degree of any vertex in the network.
Given a graph G = (V, E) and a set 3 C V, C[S] denotes the subgraph induced by 5. By
V(G) and E(G) we denote the set of vertices of G and the set of edges of & respectively. The
degree of a vertex v in a graph 0 is denoted by deg?(v). The distance between two vertices
tt and v in a graph 0, i.e., the length of a shortest path connecting them in 0, is denoted by
dc(tt,v).
Given a graph 0 = (V, E) and a set 5 C V we denote by 0[k, 5] the graph whose vertex
set is V(0[k, 5]) = 5 and whose edge set is
3
E(G[k, 5]) = [(u, v)			u, v E 5, 1 ? dG(n, v) <
We denote by [n] the set [1, 2,.. ., nJ. A vertex coloring of a graph & = (V, E) with n vertices
is a mapping x V [n] such that if (u, v) E E then x(u) # x(v). A P?donng of & (i.e.,
a coloring that uses at most (3 colors) is trivially an (a, (3)--Hdecomposition of &, for any a > 0.
Given a graph & of maximum degree A, it is possible to compute a A + 1 coloring of & in
O(A logn) time in the distributed model of computation [9].
The following definition was introduced by Cole & Vishkin [8]: an (a, (3)-ruling set 5 with
respect to & = (V, ) and P c V is a set of vertices such that:
o+ 5 c p
o+ any two vertices of 5 are at distance at least a from each other;
o+ every vertex u E P is at distance at most (3 from some vertex of 5
The notion of (a, (3)--Hruling set was generalized by Awerbuch, Goldberg, Luby & Plotkin [3]
as follows: an (a, (3)-ruling forest with respect to & = (V, E) and P c V is a forest of rooted
trees ? = [TjJ, where each tree is a subgraph of &, with the following properties:
o+ For all i, the root of Ti, called the leader of Tj and denoted by l(Tj), is in P,
o+ every vertex in P belongs to a unique tree,
o+ trees are vertex-disjoint,
o+ inter-root distance is at least a, and
o+ tree depth is at most (3.
Notice that trees of an (a, (3)--Hruling forest can contain non-P vertices. In the distributed model
of computation, a (k, klog n)--Hruling set can be computed in O(klog n) time deterministically
[3]. Given an (a, (3)--Hruling set, an (a, (3)--Hruling forest can be computed in 0(P) time determin-
istically, so that a (k, klog n)--Hruling forest can be computed in O(klog n) time distributively
[3].
Suppose we have a graph & with a partition of V(&) into A and B where the degree of
each vertex in B is at most (3 1, and are also given an (a, (3)--Hdecomposition of &[A] and a
(3--Hcoloring of &[B]. Then, we can compute an (a, (3)-decomposition of & in 0(P) time. We call
this the merging of the two decompositions (recall that a (3-coloring is an (1, (3)-decomposition).
The merging can be computed as follows. Let C be the cluster set of the decomposition of &[A];
the cluster set of the new decomposition is C u B. Colors of clusters in C remain the same, while
colors of vertices in B are updated according to the following procedure: for c = 1,2,..., (3,
in parallel each vertex with color c chooses a color in [(3] not chosen by any of its neighbors.
This procedure is correct because the set of vertices with color c is an independent set, and
neighboring vertices will choose different colors.
4
We 110W introduce a notation in the spirit of the 6(.) notation used in Computational Ge-
ometry. We say that y(n) = O(f(n)) if there exists c > 0 such that g(n) = o(f(n)c). This
convention is introduced to simplify notation.
3 Improved Network Decomposition
In this section we present our improved network decomposition algorithm. From now on, G =
(V, E) will denote the original input graph with n vertices, while H will denote a generic graph
with i vertices. Also, p = p(n) will denote a parameter to be fixed later; the performance
0 the algorithm will depend on the choice of p. The algorithm uses two mutually recursive
procedures CD(H) to compute an (n?(?), n?(?))--Hdecomposftion 0 H with E(n) = O($mogn)
and ??(P, il), to compute a (3, 4)--Hruling forest with respect to P and H. The running time of
CD(.) is 6(n?(?)). The intuition behind CD(H), as in [3], is the following: "small" degree vertices
(i.e., vertices of degree less than p) can be handled easily by making them trivial clusters and by
pcolon'ng the graph induced by them in O(plogn) time. "High" degree vertices (i.e., vertices
of degree at least p) can be used to shrink the graph by collapsing their neighborhood into one
super-vertex; the resulting graph will shrink (in terms of the number of vertices) by a factor
of at least p. After the shrinking, a network decomposition of the collapsed graph is computed
with a recursive call to CD(.), and if the shrinking factor p is high enough the recursion will
terminate fast. Finally, the two decompositions, the one of the collapsed graph and the trivial
decomposition given by the p-coloring of the small degree vertices, are merged together to give
a decomposition of the whole graph.
A symmetry-breaking problem arises when any two high degree vertices want to collapse
and their neighborhoods intersect. This problem is handled by computing a (3, 4)--Hruling forest
with respect to the set P of high degree vertices and the graph H. In a (3,4)--Hruling forest,
each vertex in P belongs to a unique tree, so that each tree can collapse onto its root without
interference from other collapsing trees. Since roots are "high" degree vertices (i. e., have degree
at least p) and are at distance at least 3 apart, the shrinking factor is at least p.
An important difference between our algorithm and that of [3] is that we compute a (3,4)--H
ruling forest with respect to the set of high degree vertices, while they compute a (3,3 log n)--H
ruling forest. Computing a (3,4)--Hruling forest gives much better performance for the following
reason. Once the ruling forest is computed, each tree is collapsed into a super-vertex: if each tree
has O(log n) diameter, as in the (3, 3 log n)--Hruling forest, then by the end of the recursion we will
have super-vertices with O((6logn)(i) diameter, where d is the depth of the recursion. On the
other hand, with (3,4)--Hruling forests the final diameter will be 0(8d), which will greatly improve
the performance of the simulation of a super-vertex. Any (3, k)--Hruling forest, for k constant, will
do but the smaller the k the better' k --H 4 is what we could achieve, The problem is that it is
not known how to compute a (3,4)--Hruling forest distributively in polylogarithmic time, whereas
this is possible for (3, 3 log n)--Hrullng forests. We solve this problem by a mutually recursive call
to CD(.). Roughly speaking, the problem is solved by considering the graph induced by vertices
at distance at most two from a vertex in P and by computing a maximal independent set in this
graph. The maximal independent set is computed by partitioning P into roughly balanced sets,
5
each of size O(?/p), and by making (mutually) recursive calls in parallel to CD(.) on graphs of
smaller size, namely 0(1 V(H) I/?)
We now give CD(H).
PRoCEDURE CD(H)
o+ IN PUT: a graph If with e vertices.
o+ OUTPUT: an ??(e), n?(?))--Hnetwork decomposition of If
1. Let P			deg?(v) > pJ. Compute a (3,4)--Hrullng forest with respect to P and If
with a call to 1??(P, If). Let ?			fTil be the resulting forest, and let If? be the graph
induced by ?,			i.e., V(1I?) (Ti			Tj E ?Y and
E(If?)			f(Ti,Tj)			i # j,?u E Tj,v E T5 : (u,v) ? E(If)J.
Let S be the set of vertices not covered by the forest, i.e., 5 u ? UiV(T?)?.
2. Compute a network decomposition of If? by a recursive call to CD(If?).
3. Compute a ?coloring of If[5], the subgraph induced by 5, and merge it with the network
decomposition computed by CD(If?) (see Section 2).
First of all, observe that
IV(If?I < IV(If)I
p
because H? is formed by collapsing the trees of f around their leaders, which are vertices of
degree at least p. Hence, the depth of the recursion is at most d = log? .
We now argue by induction that the diameter and the colors used by the network decom-
position are, respectively, 0(81o?p?) and p. We first prove the claim for the diameter. For the
base case, observe that when the recurrence stops each tree has diameter at most 8. For the
inductive step, assume that the diameter of clusters returned by CD(G?) is 8Iog? V(G?) . Each
vertex of &? is a super-vertex obtained by collapsing a tree and has diameter at most 8. Hence,
the diameter bound for CD(If) is
8 8log? V(If?) < 8 8Iog? ?? --H 8log??
To prove that p is the maximum number of colors used by CD(H) assume inductively that
CD(If?) uses at most p colors. By definition of 5 the graph H[S] can be pcolored and the
merging of If[5] and CD(If?) also uses p colors. To complete the induction, observe that the
base case is when the collapsing process ends, in which case there are no more vertices of degree
at least p, which means that the graph is p??colorable.
To analyze the time complexity of CD(H), let Tcv(?) and T?F(?) be the worst?case com-
plexity of CD(H) and 9Z?(P, If) respectively. The complexity of Tcv() on input If is given by
the formula
6
Tcv(?) ? T??() + 8 Tcv			+ O(plogn),
where T??(?) is the time spent by the recursive call to ??(P, H), 8 Tcv(/p) is the time spent
by a recursive call to CD(H?) observing that each super-vertex of H? has diameter at most 8'
and O(plog n) is the time necessary for ?colonng H[S] and the merging.
We now give ??(P, il); an outline is as follows. Recall that P C V(H) is a set of vertices of
degree at least p. The main step of ??(P, H) is a mutually recursive call to CD(.); before this,
we partition P into p-many roughly balanced disjoint subsets Pi to make calls to CD(.) in each
of these groups. The "obvious solution" of partitioning P using the last logp bits of the ID, say,
will not work, since the ID's of V(H) may be an arbitrary subset of the ID's of V(G), which is
the original set of ID's. The second step of the algorithm is to "filter" each set Pi by computing
sets Qi C Pi. The resulting sets have the property that if u E Qi and v E Q?, i # j, then
the distance between u and v in H is at least three. In the third step, for each Qi we consider
the graph H[2, Qi] and compute a maximal independent set I? of it. Each I? is computed via
a call to CD(H[2, Qi]). Recall that given an (o?, /3)--Hdecomposition of a graph G it is possible
to compute a maximal independent set of G in O(o?/3) time. Because of the filtering process,
?.e., by construction of the Qi's, any two graphs H[2, Qi] and H[2, Q?] are non--Hintersecting, and
can be called in parallel on each H[2,Qi]. The set I Uli is a (3,4)-ruling set w.r.t. P
and H and can be used to compute a (3, 4)-ruling forest in constant time.
PROCEDURE J??(P,H)
o+			INPUT: a graph H with  vertices, and a set P C
o+			OUTPUT: a (3,4)--Hruling forest with respect to P and H.
1.
Partition P into disjoint sets Pj, i C [p], as follows. Compute a (3, 3logn)--Hruling forest
= fTkl with respect to P and H, using the procedure of [3]. Within each tree Tk of
?, the leader 1(Tk) will assign numbers 1,2,.. .,p cyclically to the vertices in Tk A P; the
number assigned to a vertex is the index of the group into which it will go.
2. From each Pi, we obtain a new set Qi C Pj by marking some elements of 14; Qi is the
set of unmarked vertices in 14. For p phases repeat the following: in phase i, any vertex
u ? 14 such that dH(u,v) < 2 for some vertex v ? Uj<iQj will be marked (i.e., a vertex
in 14 is marked if it is at distance at most 2 from some unmarked vertex in an already
processed group 14).
3. Consider H[2,Qi]. In parallel, for all i, we invoke CD(H[2,Qi]) to compute a network
decomposition, and use it to get an MIS I? in H[2,Qi]. I = UiIi is a (3,4)--Hruling set
w.r.t. P and H. Given I, we construct a (3,4)--Hruling forest w.r.t. P and H in 0(1) time.
First, we show that, for all i e [p], I Pi I < 2/p There are at most C/(p + 1) trees T&, and
any j E [p]is assigned to at most
7
vertices, in tree Tk. Hence,
[I;kIl < 1T71 +1
Ii?I< ?Z???(I?kI +i) < f
for any group Pj. Next, we show that the set I = Ui 1i computed at step 3 is indeed a (3,4)--H
ruling set w.r.t. P and H. Each I? is a (3,2)--Hruling set w.r.t. Q? and H[Qj]. The set I = UiIi
is a (3,2)--Hruling set w.r.t. Q = Ui Qi and H and, by construction of the Qi's, a (3,4)--Hruling set
w.r,t. P and H.
The time complexity of ??(P? H) is given by the recurrence
< O(log n) t O(p) t 2 Tcv
where O(log n) is the time necessary for Step 1, O(p) is the time necessary for step 2 (there are
p phases), and where 2 Tcv(2/p) is the time needed for the recursive call to CD(.), which is
called on a square graph (each edge of H[2, Q?] can be simulated in 2 steps), and O(p) is the
time needed to compute each I?.
We now determine the best choice for the parameter p. Our goal is to minimize the running
time of CD(.). By substituting T??(?) into the equation of Tcv() we get (in what follows let
q = pI2 and assume p > log n)
Tcv(?) < O(logn)+O(p)+2Tcv (;) t8Tcv(--H?)+O(p logn)
p
<			6(plogn)+ lOTcv
<			O(p logn) 10logq?
By computing the first and second derivatives of the function log f(n, p) with respect to p (recall
q = p/2), we can see that the minimum of f(n,p) is attained when p = 2o(Th??) --H
with e(n) = 1IW?n. For this choice of p we get Tcv(n) = 6(n?(?)). The following theorem
summarizes the whole discussion.
Theorem 1 Given a graph G with n vertices, procedure CD(G) computes an (n?(n), nt(n))
network decomposition of G in b(n?(?)) time, where e(n) = ilmj.
We now present a simple scheme to construct a (log n, log n)--Hdecomposition, given an algo-
rithm to compute a (d(n), c(n))--Hdecomposition. This is inspired by ideas from [4, 5].
For this, we first need the sequential algoritlim of [4] to compute a (log n, log n)--Hdecomposition,
which works as follows on a graph G = (V, E) with lVj = n. Start with any vertex v. Now,
either there exists an index i 0 < i < [log2 ni --H 1, such that
8
Ifu: dG(u,v) ? ill> I?n: dG(u,v) i+ 111,
or not. If there exists no such index, then G has O(log n) diameter and hence a trivial
(log n, log n)-decomposition. Otherwise, let ? < log n be the smallest such index; let Cv
?uld?(u, v) < vJ be the cluster "centered" at v and Bv --H? fuld?(u, v) v + 1? its "border"
Note, crucially, that
IBvI ? Cvi.			(1)
Remove the vertices Cv U Bv and the edges incident at them, and repeat this process on the
remaining graph. We then get a sequence of vertices v v0,v1,v2,... with corresponding
clusters Cv0, Cv1Each set Cvi now becomes a cluster and gets color 1; note that since each
v is O(log n), the diameter of each cluster Cvi is O(log n). Also, no two clusters Cvi and Cv,,
? v,, have an edge going from one of them to the other. Hence, these are valid clusters
indeed.
Now by removing the set U?Cvi from G and repeating this on the remaining graph G[UiBvj]
to assign color classes 2, 3,...' we compute a network decomposition. The crucial property is
that the number of vertices in the new graph C[UiBvi] is at most half that of C, by (1); thus,
the number of color classes is at most [log2 n?. Hence, this yields a (log n, log n)--Hdecomposition.
The next theorem shows that, given a (c(n), d(n))-decomposition, the above linear-time
algorithm can be efficiently simulated in the distributed model of computation.
Theorem 2 Suppose we are given a distnbuted algorithm A with running time O(t(n)), to com-
pute a (d(n), c(n))--Hdecomposition. Then, given any network G (V, E) with n vertices, we can
compute a (log n, log n)-decomposition of C in O(t(n) log n + c(n)d(n) log2 n) time distributively.
PRooF. For this, we rely heavily upon the above-seen sequential scheme; we proceed as
follows.
1. Use algorithm A to compute a (log n, log n)-decomposition of G[2 log n, V].
2. For newcolor --H 1 2,..., log n do:
o+ For c 1,2,..., O(c(n)) do: in parallel, each cluster C of color c computes a maximal
collection of sets Cv, for v E C, and assigns color newcolor to them.
The crucial observation is that if u and v belong to two different clusters C1 and C2 of
color c, then Cv and Cv generated in the body of the loop do not interefere because, by step 1,
d?(u, v) > 2 log n + 1 and the radius of Cv and Cv is at most log n.
Step 1 takes O(t(n) log n) time, since it takes O(log n) time to simulate each edge of C[2 log n, V].
The simulation of the body of the nested loop in step 2 takes O(d(n)logn) time. Thus, step 2
takes O(c(n)d(n) log2 n) time.
As mentioned in the introduction, several problems are reducible to network decomposition.
9
Corollary 1 Given a network G with n vertices, the following functions can be computed in
6(nE(fl)) time in the distributed model of computation, with e(n) = 1/yiThgn:
o+ maximal independent set,
o+ (2A --H 1)--Hedge coloring,
o+ maximal matching,
o+ A--Hvertex coloring [22, 23],
o+ (log n, log n)--Hnetwork decomposition.
The first three statements are a straighforward application of the general algoritlim discussed
in the introduction. The proof of claim 4 can be found in the references, and the last claim
follows from Theorems 1 and 2.
4 Completeness
In the previous section we gave an algorithm for computing a network decomposition of a graph
in time 6(g(n)), where g(n) = 2?gn In this section we characterize a class of graphs q that
is complete for the task of computing a network decomposition. Here, completeness is to be
interpreted in the following sense: if we have an algorithm for computing a decomposition for
graphs in g in 6(t(n)) time, then we can compute a decomposition for all graphs in 6(t(n))
time.
More precisely, let h(n) be any non--Hdecreasing function and let p(n) = g(n)l/h(n), and
q(n) --H g(n)h(n). Suppose we have an algorithm A that computes a (p(n),p(n))--Hdecomposition of
graphs with maximum degree A < q(n) in time 6(p(n)). Then, we can compute a
decomposition in time 6(p(n)) for all graphs. This means that we need to concentrate our
efforts on graphs with maximum degree at most q(n); these are the difficult graphs to handle.
For example, in order to have a (polylog(n), polylog(n))--Hdecomposition algorithm running in
6(log n) time we just need to look at graphs of maximum degree less than q(n) --H nO(1/loglogn),
a quantity smaller than n? for any E.
We may further add that since it is possible to (A + 1)--Hvertex color graphs in time O(A log n)
[9], where A denotes the maximum degree of the graphs, the class of graphs that is complete for
decomposition is that of graphs with A E [?(p(n)), 6(q(n))j. For example, for p(n) = polylog(n)
the value of h(n) is 4mogn/loglogn, and the range becomes [?(pojyJog(n)),6(nS(n))], where
6(n) = 1/loglogn.
These results tell us what the bottleneck is for the method used in [3] and in this paper. The
method's basic idea is to expand clusters as long as their degree is high enough, and to color
clusters when their degree is not high enough. This approach is successful if the final diameter
of the resulting clusters is not too high, i.e., if the recursion terminates fast. For this to happen
the expansion rate of the clusters has to be high enough. But if the maximum degree is in the
range (?(poIyThg(n)), 6(nS(n))), corresponding to p(n) = polylog(n), then the maximum degree
of clusters is too low and the diameter too high for the shrinking to terminate in poly-logarithmic
10
time. This is an indication that a completely different approach is needed to solve the network
decomposition problem in O(polylog(n)) time.
We now turn to the task of showing the completeness result. The idea is to use the supposed
algorithm A as a subroutine in conjunction with a modified version of the procedures CD(.)
and ?f(.). As before, the two procedures will call each other in a mutually recursive fashion.
The initial input is a graph G with n vertices; the values p(n) and q(n) remain constant in the
following analysis.
As before, procedure CD(Jr) splits vertices into "high" and "low" degree vertices. Here,
high degree means at least q(n). But, instead of coloring the graph induced by the low degree
vertices as before, algorithm A is invoked. Another difference is that procedure ??(P, H)
returns a (3, 6)--Hruling forest w.r.t. P and H, instead of a (3, 4)--Hruling forest. On input graph
il, procedure CD(H) is as follows:
PRoCEDURE CD(H)
o+ IN PUT: a graph H with  vertices.
o+ OUTPUT: a (p(?),p(n))--Hnetwork decomposition of H
1. Let P deg11(v) > q(n)J. Compute a (3,6)--Hruling forest with respect toP and H
with a call to ??f(P? H). Let ? = ?TiJ be the res4ting forest, and 1I? be the cluster
graph induced by ?. Let S be the set of vertices not covered by the forest, i.e., S =
fl ? UiV(Ti)J. (Comment: all this is the same as before).
2 . Compute a network decomposition of HF by a recursive call to CD(H?).
3. Compute a (p(n),p(n))--Hdecomposition of H[S], the subgraph induced by 5, by using
algorithm A, and merge it with the network decomposition computed by CD(H?).
The time complexity of CD(H) is given by the following recurrence
Tcv() < T?y(?) t 12 Tcv (q$)) +
O(p(n)) is the time needed to merge the decomposition computed by A on H[S] and the one
computed by CD(H?).
The modified version of 3??(P, H) is trickier to design. Intuitively, q(n) is defined in such
a way that if we partition P into groups of size O(/q(n)), and call CD(.) in parallel on such
groups, then the recursion will terminate in t)(p(n)) time. The problem is that the requirements
of a (3,6)--Hruling forest can be satisfied locally in each group, but might be violated by vertices
belonging to different groups. This problem was eliminated in the old algorithm by a "filtering"
process of cycling through the groups. This is not possible now because there are q(n) groups
and we cannot afford to run a loop for that long. The problem is solved by invoking algorithm
A on a suitable interference graph whose maximum degree is at most q(n).
PRoCEDURE 1?f(P,H)
11
o+ IN PUT: a graph H with  vertices, and a set P c
o+ OUTPUT: a (3, 6)--Hruling forest with respect to P and H.
1. Partition P into disjoint sets Pi, i E [q(n)], as before, by computing a (3,3 log n)--Hruling
forest and by assigning numbers 1,2,.. ., q(n) cycllcally inside each tree.
2. Let Hi = H[4,Pi], i E [q(n)]. In parallel, for all i e [q(m)], compute an MIS I? of Hi by
means of a call to CD(Hi). Let I = UiIi.
3. Let F = H[2, I]. (Comment: we will show that the maximum degree ofF is A(F) <
Invoke algoritlim A to compute an MIS J of F. The set J is a (3, 6)-rullng set w.r.t. P
and H. From J a (3, 6)--Hruling forest is computed.
We first show correctness of the algorithm and then that it achieves the desired time bounds.
The set P is partitioned in step 1 with the same method employed in the old algorithm; it
follows that Pi I < 2?/q(n), i ? [q(n)]. The correctness of step 2 follows from the general fact
that given an (a, ,6)--Hdecomposition an MIS can be computed in O(aP). For step 3, we have to
show that A(F) < q(n) and that J is a MIS. Consider any vertex v E Ii C I = V(F). First
notice that v cannot have a neighbor v E Ii because if v, v ? I? then, by definition of Hi and
Ii, dH(v, v) > 5 and hence (v, v) ? E(F). We will show that any v E Ii can have at most
one neighbor v E Ij, for I? ? I?; since there are q(n) groups the claim on the degree follows.
Suppose for a contradiction that v has two neighbors v1 and v2 in the same group 1). From the
definition ofF it follows that dH(v1, v2) < 4, an impossibility because then, by definition of Hj,
(v1, v2) E E(H5), and v1 and v2 cannot both belong to i?j.
In order to show that J is a (3, 6)--Hruling forest w.r.t. P and H we need to show that: i) any
vertex v E P is at distance at most 6 from some v C J, and ii) for any two vertices vi, v2 E J,
dH(vi,v2) > 3. Let Pi be the group v belongs to; by definition of I? and Hi, vertex v is at
distance at most 4 from some vertex v ? I?. If v also belongs to the final MIS J then we are
done, otherwise v must be adjacent to a vertex w ? J in H[2, I], because J is an MIS of H
From the definition of F, d?(v, w) < 2, which implies dH(n, w) ? 6. Finally, we show that any
two vertices in J are at distance at least 3 from each other. Let v1, v2 be any two vertices in J
if they come from the same I? then they are at distance at least 5 apart (by definition of Hi),
otherwise they are at distance at least 3 (by the definition of F and J).
We now come to the complexity analysis. Step 1 is O(log v). Step 2 takes 4 Tcv(2?/q(n))
because we need 4 time units to simulate one edge of any `I?, and each Hi has size at most
2/q(n). The complexity of Step 3 is dominated by the complexity of algorithm A, which is
b(p(n)). Hence, we get the following recurrence
< O(log v) +4 T??			+
By substituting in the expression for Tcv() we get
Tcv() < 16 Tcv			+
12
< 6(p(n)) ??7??gIqO?????
= 6 (p(n) exp (ilog?
ogq(n)
= 6(p(n)ex?(?log
(n) logg(n)
= 6 p(n) exp
= 6(p(n)). h(n)
We have thus shown the following theorem.
Theorem 3 Let h(n) be any non--Hdecreasing function and let p(n) = g(n)lIh(n), and q(n) =
g(n)h(n). Suppose we have an algorithm A that computes a (p(n),p(n))-decomposition of graphs
with maximum degree A ? q(n) in time 6(p(n)). Then, we can compute a
decomposition in time 6(p(n)) for all graphs.
Conclusion
We have presented an improved distributed algoritlim for network decomposition and some
ideas about where the weakness of existing algorithms for this problem lies. It is a challeng-
ing open question whether a (log n, log n)--Hdecomposition can be found in O(polylog(n)) time
distributively.
Acknowledgments
Our sincere thanks go to David Shmoys, for his generous advice, support and suggestions. We
also thank Serge Plotkin for interesting discussions.
References
[1] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the
maximal independent set problem. Journal of Algorithms, 7:567--H583, 1986.
[2] B. Awerbuch. Complexity of network synchronization. J. Assoc. Comput. Mach., 32:804--H
823, 1985.
[3] B. Awerbuch, A. V. Goldberg, M. Luby, and 5. A. Plotkin. Network decomposition and
locallty in distributed computation. In Proc. IFEE Symposium on Foundations of Computer
Science, pages 364--H369, 1989.
[4] B. Awerbuch and D. Peleg. Routing with polynomial communication-space trade-off. SlAM
on Discrete Mathematics, 5(2):151--H162, 1992.
[5] B. Berger and L. Cowen. Fast deterministic constructions of low-diameter network decom-
positions. MIT-LCS Technical Memo #460, April 1991.
13
[6] B. Berger and J. Rompel. Simulating (logc n)-wise independence in NC. J. Assoc. Comput.
Mach., 38(4):1026--H1046, 1991.
[7] M. Choy and A.K. Singh. Efficient fault tolerant algoritlims for resource allocation in
distributed systems. In Proc. ACM Symposium on Theory of Computing, pages 593--H602,
1992.
[8] R. Cole and U. Vishkin. Deterministic coin tossing with appllcations to optimal parallel
hst ranking. Information and Control, 70:32--H53, 1986.
[9] A. V. Goldberg, 5. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse
graphs. SIAM J. Disc. Math., 1:434--H446, 1989.
[10] M. Karchmer and J. Naor. A fast parallel algorithm to color a graph with A colors. Journal
of Algorithms, 9:83--H91, 1988.
[11] H. Karloff and J. Boyar. Coloring planar graphs in parallel. Journal of Algorithms, 8:470--H
479, 1987.
[12] H. J. Karloff. A Las Vegas RNC algorithm for maximum matching. Combinatorica,
6(4):387--H391, 1986.
[13] II. J. Karloff. An NC algoritlim for Brooks' theorem. Theoretical Computer Science,
68(1):89--H103, 1989.
[14] H. J. Karloff and D. B. Shmoys. Efficient parallel algorithms for edge coloring problems.
Journal of Algorithms, 8:39--H52,1987.
[15] R. M. Karp and A. Wigderson. A fast parallel algorithm for the maximal independent set
problem. J. Assoc. Comput. Mach., 32:762--H773,1985.
[16] N. Linial. Distributive algorithms--H global solutions from local data. In Proc. IEEE Sym-
posium on Foundations of Computer Science, pages 331--H335, 1987.
[17] N. Linial and M. Saks. Decomposing graphs into regions of small diameter. In Proc.
ACM/SIAM Symposium on Discrete Algorithms, pages 320--H330, 1991.
[18] M. Luby. A fast parallel algorithm for the maximal independent set problem. SIAM J.
Comput., 15(4):1036--H1053, 1986.
[19] M. Luby. Removing randomness in parallel computation without a processor penalty. In
Proc. IEEE Symposium on Foundations of Computer Science, pages 162--H173, 1988.
[20] N. A. Lynch. Upper bounds for static resource allocation in a distributed system. Journal
of Computer and System Sciences, 23:254--H278, 1981.
[21] R. Motwani, J. Naor, and M. Naor. The probabillstic method yields deterministic parallel
algorithms. In Proc. lEEF Symposium on Foundations of Computer Science, pages 8--H13,
1989.
14
[22] A. Panconesi. Locality in Distributed Computation. PhD thesis, Cornell University, August
1993.
[23]
A. Panconesi and A. Srinivasan. The local nature of A--Hcolorings and its algorithmic applica-
tions. Technical Report TR 92-1303, Department of Computer Science, Cornell University,
September 1992. Submitted for publication to COMBINATORICA.
[24] E. Styer and G. L. Peterson. Improved algorithms for distributed resource allocation. In
Proc. ACM Symposium on PrincipThs of Distributed Computing, pages 105--H116, 1988.
15
