Network Decomposition

In this lecture we shall study a graph partitioning problem known as network decomposition. This notion was introduced by Awerbuch et al. in order to find fast deterministic algorithms for the MIS and related problems [7]. The definition is somewhat involved and is as follows.

A cluster decomposition of a graph G is a partition of G into connected components C_i. Given a graph G and a cluster decomposition, the cluster graph of G, denoted by C(G), is a graph whose vertices are the clusters C_i and where (C_i,C_j) is an edge if and only if $i \neq j$ and there is an edge (u,v) of G such that $u \in C_i$ and $v \in C_j$.A (c(n),d(n))- network decomposition or, more simply, a (c(n),d(n))-decomposition of G is a cluster decomposition such that

1.

Each cluster has diameter at most d(n) (the diameter of a cluster is a the maximum distance between any two nodes in the cluster);

2.

The chromatic number of the cluster graph is at most c(n).

We shall refer to (f(n),f(n))-decompositions simply as f(n)-decompositions.

Several graph structures, including MIS and certain vertex and edge colorings, can be solved in $O(c(n) \; d(n))$ rounds given a (c(n),d(n))-decomposition (see exercises). Therefore, in order to compute a MIS and these other problems deterministically in polylogarithmically many rounds, it suffices to compute an $O(\mbox{\sl polylog}(n))$-decomposition in $O(\mbox{\sl polylog}(n))$ rounds deterministically. In this sense then network decomposition is a complete problem in the message passing model for a reasonably large class of graph problems. Network decomposition has also other interesting applications, mainly, but not exclusively, to distributed computing [5,7,21].

We shall now focus on the problem of computing $O(\log n))$-decompositions. All results discussed in this lecture (and the next) are from a beautiful paper by Linial and Saks [25]. The first question to ask is whether such nice decompositions exist at all. The next theorem answers in the affirmative.

Theorem 13201

Let G be a graph with n vertices. Then, G has a $(2 \log_2 n)$-decomposition. Moreover, such a decomposition can be computed sequentially in polynomial time.

Proof. For a vertex u define

$$B_i(u) = \{v: d(u,v) \le i\}.$$

and

$$\delta(B_i(u)) = \{v: d(u,v) = i+1 \},$$

i.e. B_i(u) is the ball centered at u of radius i and $\delta(B_i(u))$ is its boundary.

We now describe a polynomial-time algorithm to compute the decomposition. The algorithm repeats a sequence of stages, with each stage consisting of a sequence of growing phases. Initially the graph is connected but later it can be made of scattered connected components as a result of vertex removals. A growing phase is as follows. Pick any vertex u₁ and keep growing a ball around it as long as the volume doubles each time the radius is incremented by one, or the whole connected component of u₁ is contained inside the ball. Let k₁ be the first index such that either  

$$\vert B_{k_1}(u_1)\vert \gt \vert\delta(B_{k_1}(u_1))\vert$$ (16)

or B_k1(u₁) contains the whole connected component of u₁. Notice that in both cases B_k1(u₁) has diameter at most $2 \log_2 n$.At The end of the growing phase the vertices of B_k1(u₁) are colored red, while those in $\delta(B_{k_1}(u_1))$ green (the latter might be empty).

A new growing phase is then repeated with the graph induced by the uncolored vertices, until all vertices are colored either red or green. When this happen a stage ends.

At the end of the stage the graph is partitioned into red balls B_ki(u_i)'s and (possibly empty) green boundaries $\delta(B_{k_i}(u_i))$'s. The B_ki(u_i)'s are then declared to be clusters and given color s, where s is the current stage.

Then the red part is removed and a new stage is executed with the remaining green part, until there are no vertices left.

Notice that:

1.

the B_ki(u_i)'s are legitimate clusters and their diameter is at most $2 \log_2 n$;

2.

there are at most $\log_2 n$ color classes for the clusters.

The first assertion follows trivially from the way the clusters are computed. For the second, notice that the stopping condition for the growth of a cluster implies that at the end of a stage there are at least as many red vertices as there are green ones, so that the leftover graph has size at most half that of its predecessor. $\Box$

Now that we know that $O(\log n)$-decompositions exist we ask how fast they can be computed in the message-passing model. The best deterministic result to date is the following [29] (see also [7]).

Theorem 13232

$O(\log n)$-decompositions can be computed deterministically in the synchronous, message-passing model in $O(n^{\epsilon(n)})$rounds, where $\epsilon(n)= O( 1/\sqrt{\log n})$.

Notice that this complexity is asymptotically better than any fixed root of n, for $\epsilon(n)$ goes to 0 as n grows, but it is asymptotically worse than any polylog. Notice also that $\epsilon(n)$ goes to zero extremely slowly- in practice it is never going to be less than 1/10, for this would imply n>2¹⁰⁰- quite a huge network! In fact, things are worse because of the hidden constants in the $O(\cdot)$ term.

In contrast to this, we now give a randomized algorithm that computes an $O(\log n)$-decomposition in $O(\log^2 n)$ rounds. In order to do so, however, we need to relax the requirements somewhat. Let G be a graph and $C \subset V(G)$ be a cluster (i.e. a connected component). The strong diameter of a cluster C is the maximum distance between any two vertices in C when the distance is computed in G[C]. The weak diameter of C is the maximum distance between any two vertices in C when the distance is computed in G. In other words, when computing the strong diameter we are not allowed to use vertices outside of C, whereas with the weak diameter we can take shortcuts outside of C (see Figure 12.1).

  

Figure 12.1: Weak and strong diameters

Theorem 13255

There is a randomized protocol to compute network decompositions with weak diameter at most $2 \log n$ and $O(\log n)$ color classes. The expected number of rounds is $O(\log^2 n)$.

To prove the theorem we shall first describe the algorithm and then prove two lemmas which together imply the statement of the theorem.

The algorithm is divided into stages. During a stage each vertex decides whether to enter a set S. We shall show that the connected components S have weak diameter at most $2 \log n$ and that the expected size of S is a constant fraction of that of the graph. Therefore, if the cluster forming S are given a new colour and removed from the graph, and the procedure is repeated, the whole graph will be partitioned into $O(\log n)$ expected color classes in expected $O(\log n)$ stages.

We now describe a stage. First, each vertex u, in parallel, selects a radius at random as follows:

$$r_u = \left\{ \begin{array} {ll} k & \mbox{with probability... ...\log n & \mbox{with probability $p^{\log n}$}\end{array}\right.$$

where

$$p := \frac 12.$$

Notice that vertices must know n. After r_u is determined, each vertex, in parallel, broadcasts the pair (u,r_u) to everybody within distance r_u. Here u denotes the vertex as well as its ID.

Then, each vertex, collects all pairs of the form (u,r_u). This takes $\log n$ rounds, since pairs are broadcast at distance at most $\log n$.Among all pairs, the one with highest ID is selected. Let C(u)--the center of u--denote the ID of the pair selected by u. Now, u enters S if and only if

d(u,C(u)) < r_C(u).

Each stage takes $O(\log n)$ rounds so that the overall expected running time is $O(\log^2 n)$.

We now show the two lemmas about this protocol.

Lemma 13284

The weak diameter of any connected component of S is at most $2 \log n$

Proof. The lemma follows if we show that every vertex in a connected component has the same center. For a contradiction, assume that this is not the case. Then, there must be two adjacent vertices x and y in the component who selected different centers. Assume without loss of generality that C(y)>C(x). Now, since $x \in S$ it must be r_C(x) > d(x,C(x)) and, since x and y are neighbours, $d(x,C(x)) \le 1 + d(x,C(x)) \le r(C(x))$.But this means that y has received the pair (C(x),r_C(x)) and must have selected C(x) as a center instead of C(y).$\Box$

Lemma 13299

$$\Pr[u \in S] \ge \frac{1}{2e}.$$

Proof. It is enough to consider the neighborhood of radius $\log n$ around u, since no other message can reach u. Let H_u be the set of vertices whose ID is greater than or equal to that of u which lie at distance strictly less than $\log n$.Thus, $u \in H_u$. And let $\delta H_u$ be the set of vertices whose ID is greater than u and have distance from u exactly $\log n$.We say that a vertex v reaches u if $r_v \ge d(u,v)$ and that it swallows u if r_v > d(u,v). Then, by the independence of the coin tosses,
$$\begin{align*} \Pr[u \in S] &= \Pr[\mbox{some $v \in H_u$\space swallows $u$\spa... ...\space swallows $u$}] \Pr[\mbox{no $w \in H_u$\space reaches $u$}]. \end{align*}$$
We bound the two probabilities separately. Consider the set A of vertices of H_u who reach u. The set is nonempty since it includes u. Let m(A) be the vertex of A with highest ID. Then,

$$\Pr[\mbox{some $v \in H_u$ swallows $u$}] = \Pr[\mbox{$m(A)$ swallows $u$}] = p = \frac 12.$$

Finally, we can bound the second term as follows,

$$\Pr[\mbox{no $w \in H_u$ reaches $u$}] \ge (1 - p^{\log n})^n = \left(1 - \frac 1n \right)^n \approx \frac 1e.$$

$\Box$