Papers for

network reliability teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Graph clustering method improves distributed algorithms for edge coloring and cuts

Introvert Clustering for Distributed Graph Algorithms

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].

Wed 9 SeptDistributed, Parallel, and Cluster ComputingData Structures and Algorithms
The gist
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.
Open 2609.10044v1