Graph clustering method improves distributed algorithms for edge coloring and cuts
Introvert Clustering for Distributed Graph Algorithms
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
This work introduces a new way to split networks into clusters called introvert clustering, which keeps most neighbors together in the same cluster. By repeating this process, the authors create a structure that helps solve problems like coloring edges with few colors and finding balanced cuts in the network efficiently. Their methods run in a predictable amount of time and work well even when decisions are made step-by-step within small clusters. The algorithms are simpler than previous ones and rely on this neat clustering property to work effectively.
What this means in practice
- •For distributed systems engineers: Develop distributed algorithms for assigning resources or scheduling tasks by efficiently coloring network edges with fewer conflicts using introvert clustering.
- •For network reliability teams: Use balanced network partitions to improve fault tolerance by ensuring many neighbors lie across partition boundaries for robust communication.
Authors
Yi-Jun Chang, Nima Dolatabadi
Abstract
We introduce a graph decomposition primitive called introvert clustering, which strengthens standard low-diameter clustering by guaranteeing that every clustered vertex keeps at least a $\left(\frac12-\varepsilon\right)$-fraction of its relevant neighbors in its own cluster. Repeatedly applying this primitive yields a layered introvert network decomposition with $O(\log n)$ layers and weak diameter $O(\log n)$. We give two applications in the $\mathsf{LOCAL}$ model. For every constant $\varepsilon>0$, we obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for list $\left(\frac32+\varepsilon\right)Δ$-edge coloring on graphs of maximum degree $Δ\geqΔ_0(\varepsilon)$; for bipartite graphs, the result holds for all $Δ$. For every constant $0<\varepsilon<1/4$, we also obtain a $\widetilde O(\log^2 n)$-round deterministic algorithm for a $\left(\frac14-\varepsilon\right)$-locally balanced cut, where every vertex has at least a $\left(\frac14-\varepsilon\right)$-fraction of its neighbors on the opposite side. The resulting algorithms are remarkably simple: edge coloring processes the layers in reverse order and colors each cluster, while locally balanced cut processes them forward and computes a locally maximum cut within each cluster. The introvert guarantee enables these procedures beyond the usual greedy regime of network decomposition. We construct the decomposition in $O(\log^2 n)$ randomized rounds using Miller--Peng--Xu low-diameter clustering and a simple trimming procedure, and deterministically in $\widetilde O(\log^2 n)$ rounds via a white-box adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [FOCS 2024].