Grocery on Distributed Algorithms

C1: Network Decomposition (Low-Diameter Graph Decomposition)

Reminder: This post contains 6524 words · 19 min read · by Xianbin

What is network decompositions?

Definitions

\(\textbf{Definition}\)[Strong Diameter Decomposition]. Given a graph \(G=(V, E)\), and \((\ell,D)\)-strong diameter decomposition of \(G\) is a partition of \(G\) into vertex-disjoint graphs \(G_1, G_2,\ldots,G_\ell\) such that for each \(i\in[\ell]\), we have

Each connected component of \(G_i\) has diameter at most \(D\).

The weak diameter decomposition has a weaker requirement for the diameter, i.e., for any two node \(u,v\in G_i\), there is a path of length at most \(D\) connecting \(u\) and \(v\) (this path can use nodes outside \(G_i\)).

We should notice that in LOCAL model, weak network decomposition is good enough, but in the CONGEST model, we need strong network decomposition.

Applications

The techniques of network decomposition are really useful. There are many many great results obtained by this technique.

Here is a simple example.

\(\textbf{Theorem}\). Given an \((\ell, D)\)-weak decomposition of the input graph \(G\), We can obtain a \((\Delta+1)\)-coloring

The proof is simple. We color each \(G_i\) one by one, which causes the \(\ell\) factor. We only need to prove that in each \(G_i\), \(O(D)\) rounds are enough, which is trivial.

The key is how to obtain such a network decomposition?

Construction of Network Decompositions

Wise men learn from history.

In the following, we consider \((\alpha(n), \beta(n))\) network decomposition, which means that:

  1. Every induced subgraph of a cluster \(C_i\) is connected and its diameter at most \(O(\alpha(n))\).

  2. The cluster graph can be colored with \(O(\beta(n))\) colors.

Cluster graph : Given a input graph \(G = (V, E)\) and a set of clusters \(C = \{C_i\}\), the cluster graph \(G_C\) induced by \(C\) is the graph with vertex set \(V(G_C) = C\) and edge set

\[E(G_C): = \{(C_i,C_j): i \neq j, \exists u\in C_i, v \in C_j, (u, v) \in E\}\]

That is to say, after obtaining a set of clusters, we consider each cluster as a node. Then, we obtain a new graph \(G[C]\), this graph can be colored with \(O(\beta(n))\) colors (Each cluster has the same color).

\(\textbf{Theorem}[3]\). There exists a \((a_1,b_1)\) network decomposition where \(a_1 = b_1 = n^{O(\sqrt{\frac{\log \log n}{\log n}})}=2^{O(\sqrt{\log n \cdot \log \log n})}\).

A Useful Tool: Ruling Sets

Recall that the definition of \((\alpha, \beta)\)-ruling set is as follows. Given a graph \(G=(V, E)\), and a set \(R\subseteq V\) is a \((\alpha, \beta)\)-ruling set if any two nodes \(u_1,u_2 \in R\) have \(dist(u_1,u_2) \geq \alpha\) and for any node \(w\in V\), there exists a node \(u\in R\) such that \(dist(w,u) \leq \beta\).

In the following, we will use ruling sets to construct network decomposition.

The algorithm consists of two phases. The first phase is to divide the graph into clusters of small diameter. The second phase is to color the cluster graph \(G_i\) produced by the first phase using \((\Delta^*+1)\) colors where \(\Delta^*\) is the bounded arboricity in \(G_i\).

Phase 1:

  1. Make each node into a cluster and let \(C\) be the set of these singleton clusters.

  2. Let \(L = \frac{\log n}{\log \Delta^*}\). Repeating the following process for \(L\) times:

\(\textbf{Lemma}\). There exists an algorithm Ruling-Set on input \((G[V],V',k)\) that can produce a \((k,k\log n)\)-ruling set in \(O(k\log n)\) rounds.

\(\textbf{Proof}\). We first show the algorithm. Let \(V_0 (V_1) \subseteq V\) denote the node with last bit 0(1). We divide \(V\) into \(V_0\) and \(V_1\) and recursively execute the algorithm on \(V_0\) and \(V_1\) to obtain \(S_0\) and \(S_1\). Then, for each node \(v\in S_1\), we remove any other nodes in \(S_1\) that has distance to \(v\) at most \(k\). The algorithm ends with returning \(S = S_0\cup S_1\).

Next, we prove the correctness. The first condition that for any two nodes \(u,v\in S\) is at most \(k\) is clear from the process of the algorithm. We need to show that any node \(v\in V\), there is a node \(u\) such that \(dist(u,v) \leq k\log n\). At the bottom of the recursive tree, the distance is at most \(k\). Why? We can prove it can by contradiction. If there is an node \(v\) with \(dist(v, u) > k\) where \(u\in S\), then the algorithm will put it into \(S\). So, there is no such a node. Recall that the recursive tree is at most \(\log n\) depth, so the backtrace will be \(\log n\) times, which means the tree will be merged by \(\log n\) times. Then, the distance will be increased by at most \(\log n\) times (When we merge trees, we will remove nodes in \(S\). That is the reason why the distance may increase). So, the distance is \(k\log n\) at most.

The depth is \(\log n\) and in each level of recursion takes \(O(k)\) rounds, so the round complexity is proved.

Question: How does the distributed algorithm run recursive algorithms?

Actually, it should be hard. But in Ruling-set algorithm, we only need to care about \(k\)-hops. So, we do not need to find all \(S_0\) and \(S_1\) which may take \(O(D)\) rounds in the LOCAL model where \(D\) the diameter of the input graph.

Now, let us talk about the Merge-Clusters algorithm.

The input is a forest in a cluster graph, and the output is a new cluster graph which is built from merging clusters in each one of the trees of the input forest.

That is to say, only the singleton cluster does not merge. According to Phase 1, these singleton clusters will not be in \(C'\). Thus, we obtain a separated cluster \(C_i\).

\(\textbf{Obervation}\). If a cluster has depth at most \(d_1\) and the diameter of each cluster (node) in the new cluster graph is at most \(d_2\), then, the maximum depth of any new cluster is at most \(O(d_1d_2)\).

The above observation applies to merging for one time. If the merging for \(L\) times, then, the maximum depth of the new cluster is \(\prod_{i=1}^L d_i\).

Notice that we obtain the set of clusters \(\{C_i\}\) in the line of 2.4. So, we need to prove that all nodes are in \(\cup C_i\).

\(\textbf{Lemma}\). At the end of Phase 1, each node must belong to some \(C_i\) where \(i\in [L]\).

\(\textbf{Proof}\). Recall that the distance between roots (selected nodes in the 3-ruling set) is at least 3. So, the merging of each tree does not influence each other. And, the degree is at most \(\Delta^*\) in \(G[C]\), so the number of clusters decreases by the ratio of at least \(\Delta^*\). Then, at the end of Phase 1, there is at most one cluster left. Then, a node must be in some \(C_i\).

\(\textbf{Lemma}\). The maximum depth of a cluster by the algorithm is bounded by \((9\log n)^L\), where \(L = \log n/\log \Delta^*\).

Phase 2:

  1. Color \(G[C_i]\) with \(\Delta^*+1\) colors in parallel.
  2. Color clusters sequentially.

By taking \(\Delta^* = n^{O(\sqrt{\frac{\log \log n}{\log n}})}\), we can prove Theorem 1.

Improved one

\(\textbf{Theorem}[2]\). There is a deterministic LOCAL algorithm that computes a \((\ell,D)\)-strong network decomposition of \(G\) in \(L\) rounds where \(L, C, D = 2^{O(\sqrt{\log n})}\).

Reference

[1]. Distributed Graph Algorithms. Mohsen Ghaffari.

[2]. Alessandro Panconesi and Aravind Srinivasan. Improved distributed algorithms for coloring and network decomposition problems. In Proc. of the Symp. on Theory of Comp. (STOC), pages 581–592. ACM, 1992.

[3]. Awerbuch, B., Goldberg, A.V., Luby, M. and Plotkin, S.A., 1989, October. Network decomposition and locality in distributed computation. In FOCS (Vol. 30, pp. 364-369).