Reminder: This post contains 2557 words
· 8 min read
· by Xianbin
This post will show another algorithm of network decomposition.
\(\textbf{Theorem}[1]\). There is a deterministic LOCAL algorithm that computes a \((\ell,D)\)-strong network decomposition of \(G\) in \(L\) rounds where \(\ell, D = O(\log n)\) and \(L = O(\log^8 n)\).
To make it easier to understand this beautiful algorithm, we look at a weaker version.
\(\textbf{Theorem}\). There is a deterministic LOCAL algorithm that computes a \((\ell,D)\)-strong network decomposition of \(G\) in \(L\) rounds where \(\ell = O(\log n), D = O(\log^3 n)\) and \(L = O(\log^7 n)\).
The process of the algorithm
The algorithm proceeds in iterations. More concretely, it runs the clustering Lemma’s algorithm for \(O(\log n)\) iterations. In the following, we only need to show the process of one phase. Let \(b = O(\log n)\) be the number of phases.
We use \(b\)-bit string to label each living node (initially, all nodes are living). At the beginning of the first phase, the label of each node is its ID. For each \(b\)-bit label \(L \in \{0,1\}^b\), we define its cluster \(S'_i(L) \subseteq S'_i\) in phase \(i\) to be the set of all living nodes \(v\in S'_i\) such that the label of \(v\) is \(L\).
The Process of a Phase
- We divide all nodes (with a label \(i\)-bit suffix \(X\)) into two groups, \((*,\cdots,*, 0X)\)(blue nodes) and \((*,\cdots,*,1X)\)(red nodes).
- Each red node sends a request of joining an arbitrary blue cluster \(A\).
- If there the number of adjacent red nodes that request to join \(A\) is not at most \(\lvert A \rvert / 2b\), \(A\) refuses requests. Red nodes die. \(A\) stops for this whole phase.
- Otherwise, \(A\) accepts the requests and each of the red nodes requesting joining \(A\) becomes red.
The Clustering Lemma
\(\textbf{Lemma}\). Given an arbitrary \(n\)-node graph \(G = (V, E)\), there is a deterministic algorithm that in the LOCAL model using \(O(\log^6 n)\)rounds finds a subset \(S' \subseteq S\) of living vertices where \(\lvert S' \lvert \geq \lvert S \rvert /2\), such that the subgraph \(G[S']\) is partitioned into non-adjacent disjoint clusters, each of weak-diameter \(O(\log^3 n)\) in graph \(G\).
Proof of the Clustering Lemma
To prove the above lemma, we only need to show the following properties (1) (2) (3).
- (1). For each \(i\)-bit string \(X\), the set \(S'_i(X)\) is a union of some connected components of \(G[S'_i]\).
- (2). For each label, the corresponding cluster \(S'_i(L)\) has weak-radius at most \(O(i\cdot \log^2 n)\).
- (3). \(\lvert S'_{i+1} \lvert \geq \lvert S'_i \rvert (1-1/2b)\).
By (1), at the end of \(b\) phases, different clusters are non-adjacent. By (2), each cluster has weak-radius \(O(\log^3 n)\). By (3), for the final set of living nodes \(S'\) with \(\lvert S' \rvert \geq (1-1/2b)^b \lvert S \vert \geq \lvert S \rvert /2\).
Reference
[1]. Rozhoň, V. and Ghaffari, M., 2020, June. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 350-363).