Introvert Clustering for Distributed Graph Algorithms

1.1 List Edge Coloring

• eO(log^2 n) deterministic rounds suffice for list (3/2+ε)Δ-edge coloring when Δ≥Δ0(ε), and for all Δ on bipartite graphs.The algorithm also runs in O(log^2 n) randomized rounds with high probability; unlike prior same-round-complexity results for ordinary edge coloring, it handles per-edge lists.Source: §1.1 · p. 4

1.2 Locally Balanced Cut

• eO(log^2 n) deterministic rounds compute a (1/4−ε)-locally balanced cut for every constant 0<ε<1/4, independently of Δ.The randomized complexity is O(log^2 n) rounds with high probability; relaxing the exact locally maximum cut guarantee from 1/2 removes the polynomial dependence on Δ.Source: §1.2 · pp. 5–6

1.3 Our Technique: Introvert Clustering

• Introvert clustering combines at most β|E| inter-cluster edges and weak diameter at most D with a local guarantee that each clustered vertex retains at least a (1/2−ε)-fraction of its relevant neighbors.Unlike standard low-diameter clustering, this rules out a clustered vertex having nearly all its incident edges leave its cluster.Source: §1.3 · pp. 6–7
• For every constant ε∈(0,1/2), an (ε, O(log n), O(log n))-layered introvert network decomposition can be constructed in O(log² n) randomized rounds with high probability or eO(log² n) rounds deterministically.Source: §1.3 · pp. 7–8
• The applications process layers in reverse order for edge coloring and forward order for cuts, coloring each cluster or computing a locally maximum cut within it.The introvert guarantee supplies slack beyond the usual greedy regime; for cuts, retaining roughly half of relevant neighbors and splitting at least half of those yields the 1/4 guarantee.Source: §1.3 · pp. 8–9
• The 1/2 threshold is essentially tight: in the layered complete-bipartite example, any nonempty cluster whose vertices retain more than half their neighbors must intersect every layer.Source: §1.3 · p. 9
• A nonempty cluster satisfying the strict 1/2 introvert condition has weak diameter Omega(t) = Omega(n/Delta).Source: §1.3 · p. 9
• Any clustering with the strict 1/2 introvert guarantee must leave every vertex unclustered or contain a cluster of diameter Omega(n/Delta).Source: §1.3 · p. 9

1.4 Roadmap

• Sections 2 and 3 present the list edge coloring and locally balanced cut algorithms, followed by the randomized decomposition construction in Section 4.Source: §1.4 · p. 9
• The deterministic layered introvert network decomposition, adapting Ghaffari and Grunau [GG24], is deferred to Appendices A and B.Source: §1.4 · p. 9

2.1 List Edge Coloring Inside a Cluster

• Known existential list-coloring results supply proper colorings inside clusters; for bipartite clusters, neither a minimum-degree assumption nor multiplicative slack is needed.The general-graph result uses a corollary that removes the minimum-degree assumption at the cost of an absolute lower bound on list sizes.Source: §2.1 · p. 10

2.2 The Distributed Coloring Algorithm

• List (3/2 + ε)Δ-edge coloring takes O(log^2 n) randomized rounds or eO(log^2 n) deterministic rounds; bipartite graphs are covered for all Δ.For general graphs, the result requires Δ ≥ Δ0(ε).Source: §2.2 · p. 11
• The algorithm processes layers in reverse order, coloring each cluster’s edges in parallel with the other clusters in that layer.Previously colored edges are in later layers, and their colors are removed from the cluster’s residual lists.Source: §2.2 · p. 11
• With layer diameter D, processing takes O(D) rounds per layer, yielding O(log^2 n) rounds for the randomized or deterministic decomposition.The randomized construction gives O(log^2 n) rounds, while the deterministic construction gives eO(log^2 n) rounds.Source: §2.2 · p. 12

3 Locally Balanced Cut

• O(log^2 n) randomized rounds with high probability and eO(log^2 n) deterministic rounds suffice for the stated locally balanced cut, for each constant 0 < ε < 1/4.The theorem’s cut-fraction text is incomplete in the supplied passages.Source: §3 · p. 13
• Clusters in each layer maximize crossing edges in Gi[C] subject to earlier assignments, which remain fixed; clusters in the same layer are processed in parallel.A vertex’s side is never changed after its first assignment.Source: §3 · p. 13
• A newly assigned vertex has at least half of its neighbors in Gi[C] on the opposite side, and that guarantee persists in the final cut.The argument uses that switching the vertex alone cannot improve the cluster cut.Source: §3 · p. 13
• The first cluster containing a vertex has all its incident edges in that layer or later, allowing the introvert guarantee to relate its cluster neighbors to its original degree.Earlier-layer incident edges would have made the vertex clustered earlier.Source: §3 · p. 13

4.1 Trimming Low-Diameter Clusters

• Trimming removes vertices that fail the introvert condition; the resulting clustering has at most U/(2ε) inter-cluster edges when the original clustering had U.Because trimming only removes vertices from clusters, it cannot increase weak diameter.Source: §4.1 · pp. 14–15
• MPX clustering followed by trimming yields an O(log n)-round randomized introvert clustering with weak diameter O(log n) and expected inter-cluster edge count at most β|E|.The bound is in expectation because the initial MPX edge-count guarantee is in expectation.Source: §4.1 · p. 15

4.2 Constructing the Layered Decomposition

• Repeatedly clustering the remaining edges yields an (ε, O(log n), O(log n))-layered introvert decomposition in O(log^2 n) randomized rounds with high probability.The construction runs O(log n) layers, each taking O(log n) rounds.Source: §4.2 · p. 16

5 Conclusions and Open Problems

• Introvert clustering adds a local guarantee to low-diameter clustering, requiring every clustered vertex to retain almost half its incident edges inside its cluster.The conclusion says this structure supports applications beyond the standard role of network decomposition.Source: §5 · p. 16
• The authors ask whether list edge coloring can achieve eO(log^2 n) rounds with (1 + ε)Δ colors, compared with their result’s larger palette and improved round complexity when Δ is small.Their stated deterministic result uses eO(log^2 n) rounds throughout Δ ≥ Δ0(ε).Source: §5 · p. 16
• Further applications of introvert clustering and network decompositions with other useful local guarantees are identified as future work.Source: §5 · p. 17

A.1 High-Level Overview

• The deterministic construction adapts Ghaffari and Grunau’s recursive network decomposition algorithm [GG24] to avoid the extra logarithmic factor incurred by separately derandomizing each clustering step.The adaptation makes the base case introvert, tracks active edges, and translates vertex clustering to edge clustering through the line graph.Source: §A.1 · p. 20
• The adaptation uses the line graph to translate clustered edges into disjoint vertex clusters in the original graph, with weak diameter increasing by at most one.The cited correspondence also relates unclustered line-graph vertices to inter-cluster edges.Source: §A.1 · p. 21

Roadmap.

• The roadmap first strengthens the base clustering so few edges remain inter-cluster, then inserts it into the recursion while measuring introvert guarantees against all unassigned edges.Source: Roadmap · p. 21

A.2 Head Starts and Badness

• Head starts make a vertex join the center minimizing its distance minus that center’s head start; deterministic algorithms construct these values deterministically.The framework views each center’s BFS tree as starting at time −h(v).Source: §A.2 · p. 22
• Badness measures the largest number of centers tied for earliest arrival at a vertex over distances up to a prescribed radius.When badness is small, few vertices need to be uncl clustered to make clusters pairwise non-adjacent.Source: §A.2 · p. 22
• One deterministic sampling step reduces the badness bound from B to B′ for all but at most NU/B^3 vertices, in eO(log N log B) rounds.The recursive algorithm continues with the smaller parameter and switches to a base case once B is polylogarithmic in N.Source: §A.2 · pp. 22–23

A.3 Small-Loss Clustering at the Base Case

• Taking ρ sufficiently small compensates for trimming loss: with ρ = ε/2, at most 1/4 of the relevant edges remain inter-cluster afterward.The trimming bound is ρ/(2ε) of the relevant edges.Source: §A.3 · p. 23
• The strengthened clustering lemma leaves at most a ρ-fraction of U unclustered, rather than allowing up to half of U to remain unclustered.This is the substantive change to [GG24, Theorem A.1].Source: §A.3 · p. 23
• Viewing U as vertices of Line(G), the lemma yields a clustering with at most ρ|U| edges of U inter-cluster.Source: §A.3 · p. 23

A.4 The Interface for Recursive Calls

• A valid block assigns each layer’s active intra-cluster edges, while requiring low diameter and the introvert property; appending blocks partitions E into layers.The definition updates the active edge set by removing the edges assigned to each layer.Source: §A.4 · pp. 24–25

A.5 The Base Case

• For 0 < ε < 1/2, the base case constructs O(log log N) valid layers in deterministic eO(log N) rounds, leaving at most NU/B² edges of U active.The call has B ∈ [log⁵ N, log¹⁰ N] and max_v h(v) ≤ log N.Source: §A.5 · p. 25
• Each iteration clusters the handled active edges, then trims so clustered vertices satisfy the (1/2 − ε)-introvert condition without increasing weak diameter.The layer receives exactly the active intra-cluster edges.Source: §A.5 · p. 25
• The O(log log N) iterations each take eO(log N) rounds, yielding total deterministic complexity eO(log N).Source: §A.5 · p. 26

A.6 The Recursive Step

• Sampling reduces the badness bound to B′ for all but at most NU/B³ edges, after which two calls handle the improved set and its surviving active subset.The decrease from B to roughly B′ creates slack for preserving the active-set invariant in the second call.Source: §A.6 · p. 27
• For 0 < ε < 1/2, the recursive step constructs O(log B) valid layers in deterministic eO(log N log B) rounds, leaving at most NU/B² edges of U active.The lemma applies for B ∈ [log⁵ N, N] with the stated head-start bound.Source: §A.6 · p. 27
• The recursion has O(log B / log log N) base-case calls, giving O(log B) total layers and eO(log N log B) total rounds.Source: §A.6 · p. 28

A.7 Completing the Deterministic Construction

• For every constant ε ∈ (0, 1/2), a deterministic (ε, O(log n), O(log n))-layered introvert network decomposition is constructed in eO(log² n) rounds.Source: §A.7 · pp. 28–29
• Taking N = poly(n) gives log N = O(log n), so the recursive lemma’s round bound becomes eO(log² n).Source: §A.7 · pp. 28–29
• The initial call starts with A = E and yields a valid block with O(log N) layers; the residual edge bound is below one, so no active edges remain.Its layer edge sets partition E, and each layer meets the required diameter and introvert conditions.Source: §A.7 · p. 29

• Appendix B proves the small-loss clustering lemma used in the base case of Appendix A.Both appendices adapt Ghaffari and Grunau [GG24], but in different ways.Source: B Proof of the Small-Loss Clustering… · p. 29
• Appendix A’s adaptation instead changes recursive invariants to account for all active edges, including edges outside a recursive call.That need prompted an essentially complete proof of the recursive construction.Source: B Proof of the Small-Loss Clustering… · p. 29
• The base-case modification reduces the fraction left unclustered from one half to any desired constant ρ > 0.The proof checks each step responsible for the loss and shows it can be made arbitrarily small.Source: B Proof of the Small-Loss Clustering… · p. 29

• An r-hop frontier contains vertices whose shifted distance dist_H(u, v) − h(v) is within r of its minimum over H.The proof uses the log^10 log N-hop frontier.Source: §B.1 · pp. 29–30
• For every constant ρ > 0, a deterministic eO(log N)-round algorithm leaves at most a ρ-fraction of U unclustered and gives H[U′] components of strong diameter O(log N).The lemma assumes logarithmically bounded head starts and frontiers of size at most log^100 N for vertices in U.Source: §B.1 · p. 30
• The frontier-size check bounds each distance layer by log^10 N, yielding a total frontier size at most log^100 N.The proof first bounds the distance to each frontier vertex and then uses maximum head start at that distance.Source: §B.1 · p. 30
• Scaling the head-start function lets the proof apply the small-loss version of [GG24, Theorem A.1] to obtain U′ with both required properties.The proof verifies the scaled function’s assumptions, including the frontier bound.Source: §B.1 · p. 30

B.2 Reducing the Frontier Size

• The first stage reduces each retained vertex’s log^2 log N-hop frontier to at most (log log N)^c vertices.It discards at most a ρ/2-fraction of U.Source: §B.2 · pp. 30–31
• The two-stage construction leaves at most a ρ-fraction of U unclustered and gives H[U′] components of strong diameter O(log N).Both stages take eO(log N) rounds.Source: §B.2 · p. 31

B.3 From Small Frontiers to Low-Diameter Clusters

• Small frontiers bound the s-hop degree of the head-start clustering, enabling conversion to clusters with strong diameter O(log N).The proof relates nearby cluster centers to vertices in the log^2 log N-hop frontier.Source: §B.3 · p. 32
• The conversion yields a 2-separated clustering with strong diameter O(log N), retaining at least (1 − ρ)|R| vertices.It applies a small-loss clustering result to the clustering restricted to U.Source: §B.3 · p. 32

• For the clustering, every cluster of D has weak diameter eO(log N), and at most δ|X| vertices of R \ X have a neighbor in X.The only modification from the proof of [GG24, Lemma A.14] replaces its fixed growth factor by 1+δ; all other steps are unchanged.Source: §B.4 · p. 33
• Iteratively extracting clusters and removing their neighbors keeps clusters from different iterations non-adjacent.The procedure removes newly clustered vertices and their neighbors before the next iteration.Source: §B.4 · p. 34
• After O(DEG) iterations, the procedure obtains a 2-separated clustering of weak diameter eO(log N) covering at least (1 − ρ/2) of R.The result follows after bounding the vertices discarded next to extracted clusters.Source: §B.4 · p. 34
• Decomposing each cluster locally yields strong diameter O(log N) while retaining at least (1 − ρ)|R| vertices.The clusters can be processed in parallel in eO(log N) rounds, and the total round complexity remains eO(log N).Source: §B.4 · p. 34