Skip to content
#edge computing Preprint

Introvert Clustering for Distributed Graph Algorithms

Sep 2026 · 0 citations · 37 references
Computer Science

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)\Delta$-edge coloring on graphs of maximum degree $\Delta\geq\Delta_0(\varepsilon)$; for bipartite graphs, the result holds for all $\Delta$. 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].

View source

Similar papers

Preprint Sep 2026

Unbalanced spectral Tur\'an problem for color-critical graphs with prescribed large maximum degree

Let $F$ be a connected color-critical graph with $\chi(F)=r+1\ge4$, let $S_{n,\Delta}^{(r)}=(n-\Delta)K_1\vee T(\Delta,r-1)$. We determine the graph of maximum adjacency spectral radius among all $n$-vertex $F$-free graphs with prescribed maximum degree $\Delta$. There is a constant $s_F\in[0,1)$ such that, for all suf...

Chang Liu · 1 citation
Sep 2026

Spanning Trees with Many Leaves in Graphs of Minimum Degree at Least 7

We give a polynomial-time algorithm that constructs, in every connected $n$-vertex graph of minimum degree at least $7$, a spanning tree with at least $\frac{25200}{46189}n>0.5455\,n$ leaves. No bound specific to minimum degree $7$ was known: the best bound available for this class was $\frac{11}{21}n\approx0.5238\,n$,...

Sogol Jahanbekam · 0 citations
Preprint Aug 2026

A Simple Active-Set Method for PageRank-Based Local Graph Clustering

Local graph clustering aims to find a well-connected cluster near a given seed node without exploring the entire graph. A key step in the classic local clustering algorithm of Andersen, Chung, and Lang (ACL; Internet Math. 2007) is to approximate the PageRank vector from the seed node. Their local push method computes...

Zhewei Wei, Mingji Yang · 1 citation
Preprint Sep 2026

Sparse Approximate Chromatic Profiles of Triangle-Free Graphs

We prove a sparse version of the four-colour theorem of Brandt and Thomass\'{e}, answering a question of Allen, B\"ottcher, Kohayakawa and Roberts. For every fixed $0<\gamma\le1/10$ and every $p=p(n)\in(0,1]$, asymptotically almost surely every spanning triangle-free $H\subseteq G(n,p)$ with $\delta(H)\ge(1/3+\gamma)pn...

Guo-Rong Gao, Jia-Lin He · 0 citations
Preprint Sep 2026

The diameter of recoloring graphs under a maximum average degree bound

For a graph $G$, we write $\mathrm{mad}(G)$ for its maximum average degree and $\mathrm{diam} G$ for its diameter. Let $R_k(G)$ be the graph whose vertices are the proper colorings of $G$ with $k$ colors, where two colorings are adjacent when they differ at one vertex. Feghali (JCTB, 2021) proved that, for fixed intege...

Rui-Lin Zheng, Jun-Ying Lu · 0 citations
Preprint Aug 2026

Distributed Near-Equitable Coloring in the LOCAL Model

For an $n$-vertex graph of maximum degree $\Delta$, an equitable $(\Delta+1)$-coloring is a proper coloring all of whose color classes have size $\sigma = n/(\Delta+1)$ up to rounding. Known algorithms for relaxations of this target aggregate along a spanning structure, at cost scaling with the diameter $D$. We study n...

Amit Nir, David Peleg · 1 citation

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.