arXiv CSopen access

Introvert Clustering for Distributed Graph Algorithms

Introvert Clustering for Distributed Graph Algorithms Yi-Jun Chang∗

Nima Dolatabadi†

Abstract

arXiv:2609.10044v1 [cs.DC] 9 Sep 2026

We introduce a new graph decomposition primitive that we call introvert clustering. It strengthens standard low-diameter clustering with an additional local guarantee: every clustered
vertex keeps at least a 21 − ε -fraction of its relevant neighbors inside its own cluster—hence the name introvert. Repeatedly applying this primitive to the remaining edges yields a layered introvert network decomposition with O(log n) layers and weak diameter O(log n). We give two applications of this decomposition in the LOCAL model. First, for
every constant 2 e ε > 0, we obtain a O(log n)-round deterministic algorithm for list 23 + ε ∆-edge coloring on graphs of maximum degree ∆ ≥ ∆0 (ε). For bipartite graphs, the result holds for all ∆. 2 e Second, for every constant 0 < ε < 1/4, we obtain a O(log n)-round deterministic algorithm for

computing a 14 − ε -locally balanced cut, in which every vertex has at least a 41 − ε -fraction of its neighbors on the opposite side. The algorithms resulting from the decomposition are remarkably simple. For edge coloring, we process the layers in reverse order and color each cluster; for locally balanced cut, we process them in forward order and compute a locally maximum cut inside each cluster. The introvert guarantee is what makes these simple procedures work beyond the usual greedy regime of network decomposition. We construct the layered decomposition in O(log2 n) randomized rounds by combining the Miller–Peng–Xu low-diameter clustering with a simple trimming procedure. We also give a 2 e deterministic O(log n)-round construction through a white-box adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [FOCS 2024].

∗

National University of Singapore. ORCID: 0000-0002-0109-2432. Email: [email protected] University of Copenhagen. Supported by VILLUM Foundation grant 54451, Basic Algorithms Research Copenhagen (BARC). Most of this work was completed while the author was at the National University of Singapore. ORCID: 0009-0000-0928-7499. Email: [email protected] †

Contents 1 Introduction 1.1 List Edge Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Locally Balanced Cut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Our Technique: Introvert Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Roadmap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 3 4 7

2 List Edge Coloring 2.1 List Edge Coloring Inside a Cluster . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 The Distributed Coloring Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 9

3 Locally Balanced Cut

11

4 Randomized Construction of Introvert Decomposition 12 4.1 Trimming Low-Diameter Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 Constructing the Layered Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 14 5 Conclusions and Open Problems

14

A Deterministic Construction of Introvert Decomposition A.1 High-Level Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Head Starts and Badness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Small-Loss Clustering at the Base Case . . . . . . . . . . . . . . . . . . . . . . . . . A.4 The Interface for Recursive Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 The Base Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.6 The Recursive Step . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.7 Completing the Deterministic Construction . . . . . . . . . . . . . . . . . . . . . . .

18 18 19 21 22 23 24 26

B Proof of the Small-Loss Clustering Lemma B.1 From Small Badness to Small Frontiers . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Reducing the Frontier Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 From Small Frontiers to Low-Diameter Clusters . . . . . . . . . . . . . . . . . . . . . B.4 Iterative Small-Boundary Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . .

27 27 28 29 30

1

Introduction

We work in the standard LOCAL model of distributed computing [Lin92]. The communication network is a simple, undirected, n-vertex connected graph G = (V, E). Each vertex hosts a processor with a unique identifier of O(log n) bits. Computation proceeds in synchronous rounds. In each round, every vertex may perform arbitrary local computation and exchange messages of unbounded size with each of its neighbors. Initially, each vertex knows its own identifier and its incident edges, together with the input associated with them; for example, in the list edge coloring problem, the endpoints of an edge know its list of available colors. The round complexity of an algorithm is the number of communication rounds until all vertices have produced their outputs. We consider both deterministic and randomized algorithms. In a randomized algorithm, vertices have access to private random bits, and unless stated otherwise, the algorithm is required to succeed with high probability, meaning with probability at least 1 − 1/ poly(n). Throughout the paper, n e suppresses poly(log log n) factors. denotes the number of vertices of the underlying graph, and O(·)

1.1

List Edge Coloring

Edge coloring is one of the classic local symmetry-breaking problems in distributed computing, alongside maximal independent set, maximal matching, and vertex coloring. Given a graph G = (V, E) of maximum degree ∆, the goal is to assign colors to the edges so that any two edges sharing an endpoint receive different colors. Vizing’s celebrated theorem [Viz64] guarantees that every simple graph admits a proper edge coloring with at most ∆ + 1 colors. In the distributed setting, however, the complexity of edge coloring depends crucially on how many colors are available. We study the more general list version of the problem. In list k-edge coloring, every edge e is given a list L(e) of at least k available colors, and the goal is to compute a proper edge coloring in which each edge receives a color from its own list. Ordinary k-edge coloring is the special case in which all edges have the same list of k colors. The greedy threshold. The palette size 2∆−1 forms a natural threshold for distributed edge coloring. Indeed, in any partial edge coloring, an uncolored edge is adjacent to at most 2∆ − 2 already colored edges and hence can always be colored greedily if 2∆−1 colors are available. This regime has been studied extensively [PS97, PR01, EPS15, GS17, GHK+ 17, FGK17, GHK18, Har19, Kuh20, BKO20, BBKO22]. A major breakthrough was the work of Fischer, Ghaffari, and Kuhn [FGK17], which gave the first deterministic poly(log n)-round algorithm using exactly 2∆−1 colors; moreover, their algorithm already works for list edge coloring. A recent line of work progressively improved the dependence on ∆ [Kuh20, BKO20, BBKO22], culminating in the poly(log ∆) + O(log∗ n)-round deterministic algorithm of Balliu, Brandt, Kuhn, and Olivetti [BBKO22]. Below the greedy threshold. The picture changes fundamentally below 2∆ − 1. Chang, He, Li, Pettie, and Uitto [CHL+ 20] showed that even (2∆ − 2)-edge coloring requires Ω(log∆ n) deterministic rounds, even on trees. The first deterministic polylogarithmic-round algorithms substantially below this threshold were given by Ghaffari, Kuhn, Maus, and Uitto [GKMU18]. They obtained a 3∆/2-edge coloring in poly(∆, log n) rounds. The 3∆/2 regime has since received considerable attention. Brandt, Maus, Narayanan, Schager, and Uitto [BMN+ 25] substantially improved the complexity using new local algorithms based on Hall’s theorem, obtaining a 3∆/2-edge coloring in O(∆2 log n) rounds e −2 log2 ∆ log n) rounds. More recently, Maus, Nolin, and and a ( 23 + ε)∆-edge coloring in O(ε Schager [MNS26] improved the latter bound to O(ε−1 log2 ∆ log n + ε−2 log n) rounds. 1

There has also been substantial progress with palettes smaller than 3∆/2. Ghaffari, Kuhn, Maus, and Uitto [GKMU18] gave an (1 + ε)∆-edge coloring in poly(ε−1 , log n) rounds when ∆ = Ω(ε−1 log(1/ε) log n). A major step toward Vizing’s bound was made by Su and Vu [SV19], who gave a randomized (∆ + 2)-edge coloring in poly(∆, log n) rounds. Bernshteyn [Ber22] subsequently obtained the first deterministic poly(∆, log n)-round algorithm using the optimal ∆ + 1 colors. The dependence on n was later improved [Chr23, BD25]. Very recently, √ de Vos, Maus, and Blikstad [dVMB26] obtained deterministic LOCAL algorithms 2 e for (1 + ε)∆ + O( log n)-edge coloring, including an O(log n)-round algorithm. List edge coloring. The situation is different for the more general list edge coloring problem. At the greedy threshold 2∆ − 1, many deterministic algorithms already work for list edge coloring; see, e.g., [FGK17, GHK18, Har19, Kuh20, BKO20]. Below the greedy threshold, however, much less is known. On the existential side, Kahn [Kah96] proved that, for every ε > 0, there exists a constant ∆0 (ε) such that every graph of maximum degree ∆ ≥ ∆0 (ε) admits a list (1 + ε)∆-edge coloring. More recently, Bonamy, Delcourt, Lang, and Postle [BDLP24] proved a local strengthening: if the minimum degree is at least ln25 ∆, then lists of size (1 + ε) max{deg(u), deg(v)} suffice for every edge {u, v}. This local form will be an important ingredient in our algorithm. Randomized distributed list edge coloring below the greedy threshold is also known. For every fixed ε > 0, Elkin, Pettie, and Su [EPS15]lgave amrandomized  list (1 + ε)∆-edge coloring algorithm log n ∗ for ∆ ≥ ∆0 (ε) with round complexity O ∆1−γ + log ∆ for any fixed constant γ > 0. Chang, He, Li, Pettie, and Uitto [CHL+ 20] further obtained randomized (1 + ε)∆-edge coloring algorithms for non-constant ε, but for ordinary rather than list edge coloring. Our main result is a new deterministic list edge coloring algorithm below the greedy threshold. Theorem 1 (List edge coloring). For every constant ε > 0, there exists a constant ∆0 = ∆0 (ε) such that list ( 32 + ε)∆-edge coloring on graphs of maximum degree ∆ ≥ ∆0 can be solved in O(log2 n) 2 e randomized rounds with high probability and in O(log n) deterministic rounds in the LOCAL model. For bipartite graphs, the result holds for all ∆. For comparison, combining the recent results of de Vos, Maus, and Blikstad [dVMB26] and Maus, Nolin, and Schager [MNS26] gives a deterministic ( 32 + ε)∆-edge coloring algorithm in 2 e O(log n) rounds. Their results, however, concern ordinary edge coloring, where all edges share a common palette. Our result achieves the same round complexity for the strictly more general list edge coloring problem, where each edge has its own list of available colors. To the best of our knowledge, no previous work gives a dedicated deterministic distributed algorithm for list edge coloring below the greedy threshold. One can obtain such an algorithm indirectly by derandomizing the randomized algorithm of Elkin, Pettie, and Su [EPS15] l using m deterministic  log n 2 e network decompositions [GG24]. For any fixed constant γ > 0, this gives O log n rounds. ∆1−γ 2 3 e e While this is O(log n) when ∆ ≥ (log n)1/(1−γ) , it becomes O(log n) for constant ∆. 2 3 e By allowing lists of size ( 2 + ε)∆, we obtain O(log n) rounds uniformly throughout the entire 2 e range ∆ ≥ ∆0 (ε). Thus, at this palette size, list edge coloring matches the O(log n) deterministic complexity currently achievable for ordinary edge coloring. Refer to Table 1 for a comparison with prior work.

2

Table 1: Comparison with prior work on edge coloring. Colors

Type

Rounds

Reference

Ordinary edge coloring √ (1 + ε)∆ + O( log n) √ (1 + ε)∆ + O( log n)

Deterministic

2 e O(log2 n) + O(log ∆ log n)

[dVMB26]

3∆/2

Deterministic

3∆/2

e 4 log6 n) Deterministic O(∆

3∆/2

Deterministic

O(∆2 log n)

[BMN+ 25]

( 23 + ε)∆

Deterministic

e −2 log2 ∆ log n) O(ε

[BMN+ 25]

( 23 + ε)∆

Deterministic

O(ε−1 log2 ∆ log n + ε−2 log n)

[MNS26]

( 23 + ε)∆

Deterministic

2 e O(log n)

[MNS26] + [dVMB26]

2 e Deterministic O(log n)

O(∆9 polylog n)

List edge coloring (ε > 0 and γ > 0 are any constants, ∆ ≥ ∆0 (ε)) m  l n + log∗ ∆ (1 + ε)∆ Randomized O ∆log 1−γ l m  2 log n e (1 + ε)∆ Deterministic O ∆1−γ log n

1.2

[dVMB26] [GKMU18] [Har19]

[EPS15] [EPS15, GG24]

( 32 + ε)∆

Randomized

O(log2 n)

Theorem 1

( 32 + ε)∆

Deterministic

2 e O(log n)

Theorem 1

Locally Balanced Cut

Our techniques also give a new result for the locally balanced cut problem. A cut is locally maximum if moving any single vertex to the other side cannot increase the number of crossing edges, or equivalently, if every vertex has at least half of its neighbors on the opposite side. The problem is naturally amenable to local search: starting from an arbitrary cut, repeatedly moving any vertex that improves the cut eventually reaches a locally maximum cut. It has been studied extensively in local search and algorithmic game theory [SY91, ABPW17]. Perhaps surprisingly for such a fundamental problem, its distributed complexity was largely open until very recently. Balliu, Boudier, d’Amore, Kuhn, Olivetti, Schmid, and Suomela [BBd+ 26] gave the first nontrivial distributed upper bound: an O(∆2 log6 n)-round randomized algorithm 8 e and an O(∆2 ) · O(log n)-round deterministic algorithm via derandomization. They also proved an √ Ω(min{∆, n}) lower bound, even in the quantum LOCAL model. Thus, a polynomial dependence on ∆ is inherent for finding an exact locally maximum cut. We show that this dependence can be avoided if we relax the local optimality requirement. For 0 < α ≤ 1/2, we call a cut α-locally balanced if every vertex v has at least α deg(v) neighbors on the opposite side. Thus, a 1/2-locally balanced cut is precisely a locally maximum cut. Unlike a global approximation to maximum cut, this relaxation provides a guarantee at every individual vertex.
Theorem 2 (Locally balanced cut). For every constant 0 < ε < 1/4, a 14 − ε -locally balanced cut 2 e can be computed in O(log2 n) randomized rounds with high probability and in O(log n) deterministic rounds in the LOCAL model.

3

Thus, relaxing the local guarantee from 1/2 to 14 − ε changes the complexity substantially: the polynomial dependence on ∆ inherent for locally maximum cut disappears, and the problem becomes solvable in polylogarithmic time independently of ∆. At the same time, the relaxed problem remains nontrivial. A closely related problem is kpartial 2-coloring, in which the vertices are colored with two colors so that every vertex has at least k neighbors of the opposite color. Balliu, Hirvonen, Lenzen, Olivetti, and Suomela [BHL+ 19] showed that 2-partial 2-coloring requires Ω(log n) deterministic rounds and Ω(log log n) randomized rounds on d-regular trees, for every constant d ≥ 2. These bounds imply the same lower bounds for every constant α > 0: choosing a sufficiently large constant d with αd > 1, every α-locally balanced cut on a d-regular graph is also a 2-partial 2-coloring.
Consequently, for every constant 0 < ε < 1/4, the deterministic complexity of 14 − ε -locally 2 e balanced cut lies between Ω(log n) and O(log n). See Table 2 for a comparison with prior work. Table 2: Comparison of our results with prior work on locally balanced cuts.

1.3

Local guarantee

Type

Rounds

Reference

Any constant α > 0 Any constant α > 0

Randomized lower bound Deterministic lower bound

[BHL+ 19] [BHL+ 19]

α = 1/2 α = 1/2 α = 1/2

Quantum lower bound Randomized upper bound Deterministic upper bound

Ω(log log n) Ω(log n) √ Ω(min{∆, n}) O(∆2 log6 n) 8 e O(∆2 ) · O(log n)

α = 1/4 − ε α = 1/4 − ε

Randomized upper bound Deterministic upper bound

O(log2 n) 2 e O(log n)

Theorem 2 Theorem 2

[BBd+ 26] [BBd+ 26] [BBd+ 26]

Our Technique: Introvert Clustering

The common ingredient behind both of our results is a new clustering primitive that we call introvert clustering. The main idea is to strengthen low-diameter clustering with a local guarantee: every clustered vertex keeps almost half of its incident edges inside its own cluster. We first describe this primitive and its randomized and deterministic constructions, and then explain its applications to list edge coloring and locally balanced cuts. Clustering terminology. Let G = (V, E) be a graph. For S ⊆ V , we write G[S] for the subgraph of G induced by S, NG (v) for the set of neighbors of v in G, and degG (v) = |NG (v)|. A clustering of G is a collection C of pairwise disjoint nonempty subsets of V , which we call clusters. A vertex belonging to some cluster is clustered, and all other vertices are unclustered. An edge is intra-cluster if its two endpoints belong to the same cluster; all other edges are called inter-cluster. Thus, edges incident to unclustered vertices are also inter-cluster. For a cluster C ⊆ V , its weak diameter is maxu,v∈C distG (u, v), whereas its strong diameter is maxu,v∈C distG[C] (u, v). Thus, paths witnessing weak diameter may leave the cluster, while paths witnessing strong diameter must stay inside the cluster. Throughout this paper, we only require weak diameter. Definition 1 (Introvert clustering). Let G = (V, E) be a graph. Let ε > 0, β ∈ (0, 1), and D ≥ 1. A clustering C of G is an (ε, β, D)-introvert clustering if it satisfies the following properties.

4

Few inter-cluster edges. At most β|E| edges are inter-cluster. Low diameter. Every cluster C ∈ C has weak diameter at most D. Introvert property. For every C ∈ C and every v ∈ C, |NG (v) ∩ C| ≥

1 2 −ε

degG (v).

If we drop the introvert property, the remaining two conditions are the standard type of lowdiameter clustering guarantee provided by the Miller–Peng–Xu decomposition [MPX13]: the clusters have small diameter and only a small fraction of the edges are inter-cluster. The new requirement is local. A standard low-diameter clustering may have few inter-cluster edges overall while a particular vertex has almost all of its incident edges leaving its cluster. Introvert clustering rules out this behavior for every clustered vertex. A single introvert clustering does not assign every edge to a cluster. To cover all edges, we repeatedly apply introvert clustering to the edges that remain after the previous layers. Definition 2 (Layered introvert network decomposition). An (ε, ℓ, D)-layered introvert network decomposition of a graph G = (V, E) consists of a partition of E into ℓ disjoint edge sets E = E1 ∪ · · · ∪ Eℓ . For each i ∈ [ℓ], define Gi = (V, Ei ∪ Ei+1 ∪ · · · ∪ Eℓ ). The decomposition also specifies a clustering Ci of Gi for each i ∈ [ℓ] satisfying the following properties. Layer assignment. Ei is exactly the set of intra-cluster edges of Ci in Gi . Low diameter. Every cluster C ∈ Ci has weak diameter at most D in G. Introvert property. For every C ∈ Ci and every v ∈ C, |NGi (v) ∩ C| ≥

1 2 −ε

degGi (v).

Intuitively, Gi consists of the edges that remain at the beginning of layer i. Every edge is assigned to exactly one layer, whereas a vertex may belong to clusters in several different layers. The introvert property at layer i is measured with respect to Gi , rather than the original graph G. Randomized construction. The randomized construction is simple. We start with the lowdiameter clustering of Miller, Peng, and Xu [MPX13], choosing its parameter so that the expected number of inter-cluster edges is at
most 2εβ|E|. We then repeatedly remove from each cluster any vertex that has fewer than 21 − ε of its neighbors inside the cluster. A counting argument shows that this trimming increases the number of inter-cluster edges by a factor of at most 1/(2ε). Hence, after trimming, at most β|E| edges are inter-cluster in expectation. Taking any constant β ∈ (0, 1) and repeating on the remaining edges gives O(log n) layers with high probability. Since each clustering takes O(log n) rounds and has weak diameter O(log n), we obtain the following result. Theorem 3 (Randomized layered introvert decomposition). For every constant ε ∈ (0, 1/2), an (ε, O(log n), O(log n))-layered introvert network decomposition can be constructed in O(log2 n) rounds with high probability. Deterministic construction. We next explain the main idea behind our deterministic construction. A standard network decomposition partitions the vertices into low-diameter clusters and assigns colors to the clusters so that adjacent clusters receive different colors. Ghaffari and Grunau [GG24] recently gave a deterministic algorithm that constructs such a decomposition with 2 e O(log n) colors and O(log n) cluster diameter in O(log n) rounds. Their result does not directly give what we need. Our decomposition assigns edges to layers rather than vertices to colors, and every clustered vertex must additionally satisfy the introvert property. We therefore adapt their recursive algorithm in a white-box manner. 5

At the base case, we strengthen their low-diameter clustering procedure so that an arbitrarily small constant fraction of the edges under consideration remain inter-cluster. This gives enough slack to apply our trimming procedure while still making constant-factor progress. A second modification is needed because our introvert condition is defined with respect to all edges that remain when a layer is formed. In an ordinary network decomposition, once some vertices are deferred to a later recursive call, they do not affect whether the clusters formed by the current call are valid. Here, however, an edge deferred to a later recursive call is still present and can contribute to the degree of a vertex in a cluster formed earlier. We therefore keep track of all active edges, namely, edges that have not yet been assigned to any layer, and require every introvert condition to hold with respect to the full active edge set. Accordingly, we strengthen the invariant of the recursive calls to also bound the number of active edges lying outside the set currently handled by the recursion. We show that the recursive construction can be carried out while preserving this strengthened invariant. Finally, since the objects handled by the recursive algorithm are vertices whereas our layers consist of edges, we run the recursion on the line graph. A clustering of the line graph into pairwise non-adjacent clusters translates naturally into a clustering of the vertices of G, with essentially the same diameter, while every inter-cluster edge corresponds to an unclustered vertex in the line graph. Theorem 4 (Deterministic layered introvert decomposition). For every constant ε ∈ (0, 1/2), 2 e an (ε, O(log n), O(log n))-layered introvert network decomposition can be constructed in O(log n) rounds deterministically. Why being introvert helps. A standard network decomposition is particularly useful for turning sequential local algorithms into distributed ones. Roughly speaking, one processes the color classes of the decomposition one at a time; within each color class, the low-diameter clusters can be processed independently and in parallel. For example, this immediately parallelizes the familiar greedy algorithms for maximal independent set, maximal matching, (∆ + 1)-vertex coloring, and (2∆ − 1)-edge coloring. More generally, Ghaffari, Kuhn, and Maus [GKM17] formalized this connection through the SLOCAL model, which captures algorithms that process the vertices sequentially while making each decision using only a local neighborhood. Network decomposition provides a general mechanism for translating such sequential locality into distributed locality, and has consequently become a central tool for obtaining efficient deterministic distributed algorithms [GKM17, RG20]. Introvert decomposition gives us something extra: its clusters not only have low diameter, but also keep many of their neighbors close. This seemingly modest additional guarantee turns out to make a surprisingly large difference. The introvert guarantee allows us to process clusters even in settings where an arbitrary partial solution may leave too little room to extend the solution greedily. List edge coloring below the 2∆ − 1 greedy threshold is one example. An arbitrary partial coloring may leave an uncolored edge with no available color. With introvert clustering, however, roughly half of the relevant edges at each vertex remain inside
the current cluster. This leaves pre3 cisely the additional slack needed to make lists of size 2 + ε ∆ sufficient. For locally balanced cut, the same phenomenon appears in a different form: roughly half of each vertex’s relevant neighbors remain inside its cluster, and computing a locally maximum cut within the cluster guarantees that at least half of those neighbors lie on the opposite side. The two factors of 1/2 lead directly to the 1/4 guarantee. A particularly appealing aspect of our framework is its simplicity. Once the layered introvert 6

network decomposition from Theorems 3 and 4 is available, both applications admit remarkably simple algorithms: the edge coloring algorithm processes the layers in reverse order and colors each cluster, while the cut algorithm processes them in forward order and computes a locally maximum cut inside each cluster. Thus, beyond the new quantitative bounds in Theorems 1 and 2, these applications illustrate the extra algorithmic power provided by the introvert guarantee, opening up new opportunities for using network decomposition beyond the usual greedy regime. The 1/2 barrier. The threshold 1/2 in the introvert property is essentially tight. Consider the graph in Figure 1, consisting of t = 2n/∆ consecutive layers L1 , . . . , Lt , each with ∆/2 vertices, where every pair of consecutive layers induces a complete bipartite graph. Thus, every vertex in an internal layer has degree ∆. Suppose that a nonempty cluster C satisfies |N (v) ∩ C| > deg(v)/2 for every v ∈ C. Let Li be the first layer intersecting C. If i > 1, then any v ∈ C ∩ Li has no neighbor in C in Li−1 , and hence at most its ∆/2 neighbors in Li+1 can belong to C. Thus |N (v) ∩ C| ≤ ∆/2 = deg(v)/2, a contradiction. Therefore C must intersect L1 . By the same argument from the other end, C must also intersect Lt ; in fact, it must intersect every layer. Hence every nonempty cluster satisfying the strict 1/2 introvert condition has weak diameter Ω(t) = Ω(n/∆). In particular, any clustering with this stronger guarantee must either leave every vertex unclustered or contain a cluster of diameter Ω(n/∆). t = 2n ∆ layers

···

∆/2 vertices .. .

.. .

.. .

.. .

.. .

L1

L2

L3

Lt−1

Lt

Figure 1: A graph illustrating the 1/2 barrier for introvert clustering.

1.4

Roadmap

The remainder of the paper is organized as follows. In Section 2, we present our list edge coloring algorithm. In Section 3, we give our algorithm for locally balanced cut. We then present the randomized construction of layered introvert network decomposition in Section 4. We conclude with a discussion of open questions and future directions in Section 5. The deterministic construction of layered introvert network decomposition, based on an adaptation of the recursive network decomposition algorithm of Ghaffari and Grunau [GG24], is deferred to Appendices A and B.

7

2

List Edge Coloring

In this section, we show how a layered introvert network decomposition gives our list edge coloring algorithms. Once the decomposition is available, the algorithm is simple: we process the layers in reverse order and color all clusters of the current layer in parallel. The main point is to show that the introvert property leaves sufficiently many colors available when a cluster is processed.

2.1

List Edge Coloring Inside a Cluster

We begin by reviewing the known existential list edge coloring results that we use to color the edges within each cluster. A list assignment L assigns to each edge e a set L(e) of available colors. A proper L-edge coloring assigns to each edge e a color from L(e) such that any two edges sharing an endpoint receive distinct colors. The first result gives a local list size condition for general graphs. Theorem 5 (Bonamy, Delcourt, Lang, and Postle [BDLP24]). For every constant γ > 0, there exists a constant ∆0 (γ) such that the following holds. Let H be a graph with maximum degree ∆(H) ≥ ∆0 (γ) and minimum degree δ(H) ≥ ln25 ∆(H). If L is a list assignment satisfying |L({u, v})| ≥ (1 + γ) max{degH (u), degH (v)} for every edge {u, v} ∈ E(H), then H admits a proper L-edge coloring. For bipartite graphs, neither the minimum degree assumption nor the multiplicative slack is needed. Theorem 6 (Borodin, Kostochka, and Woodall [BKW97]). Let H be a bipartite graph with a list assignment L. If |L({u, v})| ≥ max{degH (u), degH (v)} for every edge {u, v} ∈ E(H), then H admits a proper L-edge coloring. For general graphs, the minimum degree assumption in Theorem 5 is inconvenient for our application, since the subgraph induced by a cluster may contain vertices of small degree. The following simple corollary removes this assumption at the cost of requiring an absolute lower bound on the list sizes. Corollary 1. For every constant γ > 0, there exists a constant ∆0 (γ) such that the following holds for every integer ∆ ≥ ∆0 (γ). Let H be a graph with maximum degree at most ∆. If L is a list assignment satisfying |L({u, v})| ≥ (1 + γ) max{degH (u), degH (v), ⌈ln25 ∆⌉} for every edge {u, v} ∈ E(H), then H admits a proper L-edge coloring. Proof. We may assume that ∆ is sufficiently large that ⌈ln25 ∆⌉ < ∆. Set d0 = ⌈ln25 ∆⌉. We augment H to a graph H + with minimum degree at least d0 , while preserving the degrees of vertices of H that already have degree at least d0 . For each vertex v with degH (v) < d0 , take a fresh copy Qv of a (d0 + 1)-clique and connect v to exactly d0 − degH (v) distinct vertices of Qv . Then v has degree exactly d0 in H + , while every vertex of Qv has degree either d0 or d0 + 1. Vertices of degree at least d0 in H are left unchanged.

8

Finally, add a disjoint copy of a (∆ + 1)-clique. Since d0 + 1 ≤ ∆, the resulting graph satisfies ∆(H + ) = ∆

δ(H + ) ≥ d0 ≥ ln25 ∆.

and

Moreover, every original vertex v ∈ V (H) satisfies degH + (v) = max{degH (v), d0 }. Hence, for every original edge {u, v} ∈ E(H), |L({u, v})| ≥ (1 + γ) max{degH (u), degH (v), d0 } = (1 + γ) max{degH + (u), degH + (v)}. Extend L to the newly added edges by assigning them sufficiently large lists of colors. The resulting list assignment on H + satisfies the conditions of Theorem 5, so H + has a proper list edge coloring. Restricting this coloring to the original edges of H yields a proper L-edge coloring of H.

2.2

The Distributed Coloring Algorithm

We now prove our list edge coloring theorem. Theorem 1 (List edge coloring). For every constant ε > 0, there exists a constant ∆0 = ∆0 (ε) such that list ( 32 + ε)∆-edge coloring on graphs of maximum degree ∆ ≥ ∆0 can be solved in O(log2 n) 2 e randomized rounds with high probability and in O(log n) deterministic rounds in the LOCAL model. For bipartite graphs, the result holds for all ∆. Proof. Fix the constant ε > 0 from the theorem. It suffices to consider 0 < ε ≤ 1/2, since a result for a smaller value of ε also implies the result for any larger one. Set η = ε/2 and γ = ε/2. The algorithm. We first construct an (η, ℓ, D)-layered introvert network decomposition E = E1 ∪ · · · ∪ Eℓ , with clusterings C1 , . . . , Cℓ , where ℓ = O(log n) and D = O(log n). Recall that Gi = (V, Ei ∪ Ei+1 ∪ · · · ∪ Eℓ ). We process the layers in reverse order, Eℓ , Eℓ−1 , . . . , E1 . Suppose that all edges in Ei+1 ∪· · ·∪Eℓ have already been colored. For each cluster C ∈ Ci , we color the edges of Gi [C], which are precisely the edges of Ei with both endpoints in C. All clusters in the same layer are processed in parallel. How many colors remain? Fix a cluster C ∈ Ci . For every vertex v ∈ C, the introvert property gives degGi [C] (v) ≥ ( 21 − η) degGi (v). It follows that  degGi (v) − degGi [C] (v) ≤

   1 1 + η degGi (v) ≤ + η ∆. 2 2

(1)

The left-hand side is exactly the number of edges incident to v that belong to later layers and have therefore already been colored. Now consider an edge e = {u, v} ∈ E(Gi [C]). Without loss of generality, we assume that degGi [C] (u) ≥ degGi [C] (v). Let Li (e) denote its residual list after removing all colors already used by colored edges incident to u or v. The number of colors removed from L(e) is at most

degGi (u) − degGi [C] (u) + degGi (v) − degGi [C] (v) . 9

Therefore, 

  
3 1 |Li (e)| ≥ + ε ∆ − degGi (u) − degGi [C] (u) − +η ∆ 2 2
= degGi [C] (u) + ∆ − degGi (u) + (ε − η)∆

by (1)

≥ degGi [C] (u) + (ε − η)∆

as degGi (u) ≤ ∆

≥ (1 + ε − η) degGi [C] (u)

as degGi [C] (u) ≤ ∆.

Since γ = ε − η = ε/2 and degGi [C] (u) = max{degGi [C] (u), degGi [C] (v)}, we obtain |Li ({u, v})| ≥ (1 + γ) max{degGi [C] (u), degGi [C] (v)}.

(2)

Handling small degrees. For general graphs, we also need the absolute list size guarantee required by Corollary 1. Applying (1) to both endpoints of an edge e ∈ E(Gi [C]) gives     1 ∆ 3 + ε ∆ − (1 + 2η)∆ = + ε − 2η ∆ = . |Li (e)| ≥ 2 2 2 For sufficiently large ∆, depending only on ε, ∆ ≥ (1 + γ)⌈ln25 ∆⌉. 2 Together with (2), this implies that every edge {u, v} ∈ E(Gi [C]) satisfies o n |Li ({u, v})| ≥ (1 + γ) max degGi [C] (u), degGi [C] (v), ⌈ln25 ∆⌉ . Therefore, by Corollary 1, Gi [C] admits a proper list edge coloring from the residual lists. Since each residual list excludes all colors already used by incident edges in later layers, this coloring extends the existing partial coloring without introducing any conflict. Distributed implementation. The clusters in Ci are vertex-disjoint, so all clusters of the same layer can be processed simultaneously. Each cluster has weak diameter at most D in G. Since messages in the LOCAL model have unbounded size, all information about Gi [C] and its residual lists can be gathered in O(D) rounds. Local computation is unrestricted, so a proper list edge coloring whose existence is guaranteed above can then be computed locally, and the resulting colors can be communicated in another O(D) rounds. Thus, given the layered decomposition, each layer can be processed in O(D) rounds, and all layers can be colored in O(ℓD) = O(log2 n) rounds. Using Theorem 3, we obtain an O(log2 n)-round randomized algorithm with high probability. 2 e Using Theorem 4, we obtain a O(log n)-round deterministic algorithm. Bipartite graphs.

Suppose now G is bipartite, so every graph Gi [C] is also bipartite. By (2), |Li ({u, v})| ≥ max{degGi [C] (u), degGi [C] (v)}

for every edge {u, v} ∈ E(Gi [C]). Thus, by Theorem 6, every cluster can be colored without any lower bound on ∆. The same algorithm and round complexity bounds therefore apply for all ∆ in the bipartite case. 10

3

Locally Balanced Cut

In this section, we show how a layered introvert network decomposition gives our locally balanced cut algorithm. As in the edge coloring algorithm, we process the decomposition one layer at a time, but here we process the layers in forward order. When a vertex first appears in a cluster, we assign it to one side of the cut, and its assignment is never changed afterward.
Theorem 2 (Locally balanced cut). For every constant 0 < ε < 1/4, a 14 − ε -locally balanced cut 2 e can be computed in O(log2 n) randomized rounds with high probability and in O(log n) deterministic rounds in the LOCAL model. Proof. Fix the constant 0 < ε < 1/4 from the theorem and set η = 2ε. We construct an (η, ℓ, D)layered introvert network decomposition E = E1 ∪ · · · ∪ Eℓ , with clusterings C1 , . . . , Cℓ , where ℓ = O(log n) and D = O(log n). Recall that Gi = (V, Ei ∪ Ei+1 ∪ · · · ∪ Eℓ ). The algorithm. Initially, no vertex has been assigned to either side of the cut. We process the layers in forward order, E1 , E2 , . . . , Eℓ . Consider a cluster C ∈ Ci . Some vertices of C may already have been assigned to a side of the cut because they belonged to a cluster in an earlier layer. We keep these assignments fixed and assign the remaining vertices of C so as to maximize the number of crossing edges in Gi [C], subject to the fixed assignments. Once a vertex is assigned, its assignment is never changed. All clusters in the same layer are processed in parallel. Since every edge belongs to some layer, every vertex belongs to a cluster in some layer and is therefore eventually assigned. The guarantee for a newly assigned vertex. Suppose that v is assigned for the first time while processing a cluster C ∈ Ci . By the choice of the cut inside C, switching only v to the other side cannot increase the number of crossing edges in Gi [C]. Therefore, at least half of the neighbors of v in Gi [C] are assigned to the opposite side; otherwise, switching v would strictly increase the number of crossing edges. Thus, v has at least 12 degGi [C] (v) neighbors in C on the opposite side. Relating to the original degree. Fix a vertex v, and let i be the first layer in which v belongs to a cluster. Let C ∈ Ci be the cluster containing v. None of the edges incident to v belongs to an earlier layer. Indeed, if an incident edge belonged to Ej for some j < i, then it would be an intra-cluster edge of Cj , implying that v already belonged to a cluster in layer j. Consequently, degGi (v) = degG (v).

(3)

By the introvert property and (3),  degGi [C] (v) ≥

 1 − η degG (v). 2

Since v is assigned for the first time when C is processed, the argument above shows that it has at least     1 1 1 1 degGi [C] (v) ≥ − η degG (v) = − ε degG (v) 2 2 2 4 neighbors on the opposite side. These assignments are never changed afterward, so the same guarantee
holds in the final cut. Since this argument applies to every vertex, the resulting cut is 1 4 − ε -locally balanced. 11

Distributed implementation. As in the edge coloring algorithm, the clusters of each layer can be processed in parallel, and the weak diameter bound allows each cluster to gather all information needed to compute its cut in O(D) rounds. Thus, given the layered decomposition, all layers can be processed in O(ℓD) = O(log2 n) rounds. Using Theorem 3, we obtain an O(log2 n)-round random2 e ized algorithm with high probability. Using Theorem 4, we obtain a O(log n)-round deterministic algorithm.

4

Randomized Construction of Introvert Decomposition

In this section, we prove Theorem 3. The construction starts from the standard low-diameter clustering of Miller, Peng, and Xu [MPX13]. Such a clustering guarantees that few edges cross between clusters, but this is only a global guarantee: an individual vertex may still have most of its neighbors outside its own cluster. We enforce the introvert property by a simple trimming procedure.

4.1

Trimming Low-Diameter Clusters

We first show that any clustering with few inter-cluster edges can be trimmed so that every remaining clustered vertex satisfies the introvert property, while increasing the number of inter-cluster edges by only a constant factor. Lemma 1 (Trimming). Let C be a clustering of a graph G = (V, E), and let U be the number of inter-cluster edges with respect to C. For every 0 < ε < 1/2, there is a clustering C ′ obtained by removing vertices from the clusters of C. The clustering C ′ has the following properties.
• Every v ∈ C ∈ C ′ satisfies |NG (v) ∩ C| ≥ 21 − ε degG (v). • The number of inter-cluster edges with respect to C ′ is at most U/(2ε).
Proof. Starting from C, repeatedly remove any clustered vertex v with fewer than 12 − ε degG (v) neighbors in its current cluster. When the process terminates, every remaining clustered vertex satisfies the first property. It remains to bound the number of inter-cluster edges created by the trimming process. For every vertex v that is removed, consider the clustering immediately before v is removed. Let din (v) be the number of neighbors of v that are still in the same cluster as v at this point, and let
dout (v) = degG (v) − din (v). Since v is removed, din (v) < 21 − ε degG (v), and therefore dout (v) >

1 + 2ε din (v). 1 − 2ε

(4)

Let Din and Dout denote the sums of din (v) and dout (v), respectively, over all vertices removed during the process. We bound Dout − Din by considering the contribution of each edge. First consider an edge that is initially intra-cluster. If neither endpoint is removed, it contributes nothing. If exactly one endpoint is removed, the edge is internal immediately before that endpoint is removed, and hence contributes −1 to Dout − Din . If both endpoints are removed, the edge is internal when the first endpoint is removed and external when the second endpoint is removed, so its two contributions cancel. Thus, every initially intra-cluster edge contributes at most 0. Now consider an edge that is initially inter-cluster. Since clusters only lose vertices, its endpoints can never enter the same cluster. Hence it contributes at most 1 to Dout from each endpoint, and therefore at most 2 to Dout − Din . Since there are U initially inter-cluster edges, we obtain Dout − Din ≤ 2U. 12

(5)

1+2ε Din . Together with (5), this yields Summing (4) over all removed vertices gives Dout > 1−2ε

4ε Din < Dout − Din ≤ 2U, 1 − 2ε and hence

1 − 2ε U. 2ε Every initially intra-cluster edge that becomes inter-cluster is counted once in Din , namely when its first endpoint is removed. Thus, the number of newly created inter-cluster edges is Din . The final number of inter-cluster edges is therefore at most Din <

U + Din < U +

1 − 2ε U U= , 2ε 2ε

proving the second property. Since trimming only removes vertices from clusters, it cannot increase their weak diameter. More precisely, in Lemma 1, if every cluster of the original clustering C has weak diameter at most D, then the same is true for the trimmed clustering C ′ , since every cluster of C ′ is a subset of some cluster of C. We use the low-diameter clustering algorithm of Miller, Peng, and Xu [MPX13]. Although originally presented in the PRAM model, it is well known that the algorithm admits an implementation in the LOCAL model with the following guarantee; see, e.g., [FGdV22]. Theorem 7 (MPX clustering). For every λ ∈ (0, 1), there is a randomized O(λ−1 log n)-round LOCAL algorithm that computes a clustering C of a graph G = (V, E) such that every cluster has strong diameter O(λ−1 log n) and the expected number of inter-cluster edges is at most λ|E|. Combining MPX low-diameter clustering with Lemma 1 yields an introvert clustering. More precisely, we obtain exactly the guarantees of an (ε, β, O(log n))-introvert clustering, except that the bound on the number of inter-cluster edges holds only in expectation. To construct the layered decomposition, we therefore run this procedure for a fixed O(log n) number of iterations and show that all edges have been assigned with high probability. Lemma 2 (Randomized introvert clustering). For all constants 0 < ε < 1/2 and β ∈ (0, 1), there is a randomized O(log n)-round LOCAL algorithm that computes a clustering C of a graph G = (V, E). The clustering C satisfies the following properties. • Every cluster has weak diameter O(log n). • Every v ∈ C ∈ C satisfies |NG (v) ∩ C| ≥

1 2 −ε

degG (v).

• If U is the number of inter-cluster edges with respect to C, then E[U ] ≤ β|E|. Proof. Apply Theorem 7 with λ = 2εβ. Let U0 be the number of inter-cluster edges in the resulting clustering. Then E[U0 ] ≤ 2εβ|E|. We now apply Lemma 1. The resulting clustering satisfies the introvert property, and if U denotes its number of inter-cluster edges, then U ≤ U0 /(2ε). Therefore, E[U ] ≤ E[U0 ]/(2ε) ≤ β|E|. Since ε and β are constants, the MPX clustering takes O(log n) rounds. The trimming can also be implemented in O(log n) rounds. Indeed, each MPX cluster has strong diameter O(log n) before trimming, so one vertex can gather the induced subgraph of the cluster, together with the degrees in G of all its vertices, in O(log n) rounds. It can then simulate the trimming process locally and communicate the resulting cluster membership back to the vertices. Finally, by the observation following Lemma 1, trimming preserves the O(log n) weak-diameter bound. 13

4.2

Constructing the Layered Decomposition

We now repeatedly apply Lemma 2 to the edges that remain to obtain the desired layered introvert decomposition. Theorem 3 (Randomized layered introvert decomposition). For every constant ε ∈ (0, 1/2), an (ε, O(log n), O(log n))-layered introvert network decomposition can be constructed in O(log2 n) rounds with high probability. Proof. Let G = (V, E), and fix any constant β ∈ (0, 1), say β = 1/2. We construct the decomposition one layer at a time. Initially, let G1 = G. At layer i, apply Lemma 2 to Gi and let Ci be the resulting clustering. We define Ei to be the set of intra-cluster edges of Ci in Gi , and let Gi+1 consist of the remaining inter-cluster edges. We do this for ℓ = ⌈c log n⌉ iterations, for a sufficiently large constant c, to construct E1 , . . . , Eℓ and C1 , . . . , Cℓ . By construction, every cluster of Ci has weak diameter O(log
n). Moreover, the introvert condition holds: every v ∈ C ∈ Ci satisfies |NGi (v) ∩ C| ≥ 21 − ε degGi (v). Thus, to show that the resulting edge partition and clusterings form an (ε, ℓ, O(log n))-layered introvert network decomposition, it suffices to show that E1 ∪ · · · ∪ Eℓ = E, which is equivalent to E(Gℓ+1 ) = ∅. Let Mi = |E(Gi )|. By Lemma 2, conditioned on Gi , E[Mi+1 | Gi ] ≤ βMi .

(6)

Taking expectations and iterating (6) gives E[Mi ] ≤ β i−1 |E|. Since |E| < n2 , E[Mℓ+1 ] ≤ β ℓ n2 ≤ n2−c log(1/β) . As Mℓ+1 is a nonnegative integer, Markov’s inequality gives Pr[E1 ∪ · · · ∪ Eℓ ̸= E] = Pr[Mℓ+1 > 0] ≤ n2−c log(1/β) . Since c can be chosen to be an arbitrarily large constant, E1 ∪ · · · ∪ Eℓ = E with high probability, as desired. Each layer takes O(log n) rounds by Lemma 2. Therefore, the entire layered decomposition can be constructed in O(log2 n) randomized rounds with high probability.

5

Conclusions and Open Problems

We introduced introvert clustering, a low-diameter clustering in which every clustered vertex keeps almost half of its neighbors inside its own cluster. This extra local guarantee allows network decompositions to be useful beyond their standard role of parallelizing sequential local algorithms: it gives enough structure to process clusters even when an arbitrary partial solution may not be extendable greedily. Using this idea, we obtained new algorithms for list edge coloring and locally balanced cut. For list edge coloring, Elkin, Pettie, and Su [EPS15] gave a randomized list (1+ε)∆-edge coloring algorithm, which can also be derandomized using general network decomposition techniques. Our 2 e algorithm uses more colors, but achieves O(log n) deterministic rounds throughout the entire range ∆ ≥ ∆0 (ε), improving the resulting round complexity when ∆ is small. Can one achieve the same 2 e O(log n) round complexity with (1 + ε)∆
colors? For locally balanced cut, our 14 − ε guarantee can be obtained in poly(log n) rounds indepen√ dently of ∆, whereas the optimal guarantee 1/2 requires Ω(min{∆, n}) rounds [BBd+ 26]. What 14

happens between these two regimes? Can one compute a 12 − ε -locally balanced cut in poly(log n) rounds independently of ∆, or is there an intermediate threshold beyond which a dependence on ∆ is unavoidable? Finally, list edge coloring and locally balanced cut exploit the introvert property in quite different ways, suggesting that its usefulness may extend well beyond these two applications. Finding further applications of introvert clustering, and more broadly developing network decompositions with other useful local guarantees, is an exciting direction for future work.

AI Disclosure We used OpenAI’s ChatGPT to assist with proofreading and improving the clarity of the exposition, and to help identify potential issues in proofs and citations throughout the manuscript. The authors independently verified all mathematical arguments, corrections, and references and take full responsibility for the content of the paper.

References [ABPW17] Omer Angel, Sébastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 429–437. ACM, 2017. [BBd+ 26] Alkida Balliu, Thomas Boudier, Francesco d’Amore, Fabian Kuhn, Dennis Olivetti, Gustav Schmid, and Jukka Suomela. Distributed algorithms for potential problems. In Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC), pages 154–165. ACM, 2026. [BBKO22] Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time polylogarithmic in ∆. In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing (PODC), pages 15–25. ACM, 2022. [BD25] Anton Bernshteyn and Abhishek Dhawan. Fast algorithms for Vizing’s theorem on bounded degree graphs. Journal of Combinatorial Theory, Series B, 175:69–125, 2025. [BDLP24] Marthe Bonamy, Michelle Delcourt, Richard Lang, and Luke Postle. Edge-colouring graphs with local list sizes. Journal of Combinatorial Theory, Series B, 165:68–96, 2024. [Ber22] Anton Bernshteyn. A fast distributed algorithm for (∆ + 1)-edge-coloring. Journal of Combinatorial Theory, Series B, 152:319–352, 2022. [BHL+ 19] Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela. Locality of not-so-weak coloring. In Proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 11639 of Lecture Notes in Computer Science, pages 37–51. Springer, 2019. [BKO20] Alkida Balliu, Fabian Kuhn, and Dennis Olivetti. Distributed edge coloring in time quasi-polylogarithmic in ∆. In Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), pages 289–298. ACM, 2020.

15

[BKW97] Oleg V. Borodin, Alexandr V. Kostochka, and Douglas R. Woodall. List edge and list total colourings of multigraphs. Journal of Combinatorial Theory, Series B, 71(2):184– 204, 1997. [BMN+ 25] Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, and Jara Uitto. On the locality of Hall’s theorem. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4198–4226. SIAM, 2025. [CHL+ 20] Yi-Jun Chang, Qizheng He, Wenzheng Li, Seth Pettie, and Jara Uitto. Distributed edge coloring and a special case of the constructive Lovász local lemma. ACM Transactions on Algorithms, 16(1):8:1–8:51, 2020. [Chr23] Aleksander Bjørn Grodt Christiansen. The power of multi-step Vizing chains. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1013–1026. ACM, 2023. [CL23] Yi-Jun Chang and Zeyong Li. The complexity of distributed approximation of packing and covering integer linear programs. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC), pages 32–43. ACM, 2023. [dVMB26] Tijn de Vos, Yannic Maus, and Joakim Blikstad. Brief announcement: Deterministic edge coloring with few colors in CONGEST. In Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC), pages 40–43. ACM, 2026. [EN16] Michael Elkin and Ofer Neiman. Distributed strong diameter network decomposition. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 211–216. ACM, 2016. [EPS15] Michael Elkin, Seth Pettie, and Hsin-Hao Su. (2∆−1)-edge-coloring is much easier than maximal matching in the distributed setting. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 355–370. SIAM, 2015. [FGdV22] Sebastian Forster, Martin Grösbacher, and Tijn de Vos. An improved random shift algorithm for spanners and low diameter decompositions. In Proceedings of the 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022. [FGK17] Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. Deterministic distributed edgecoloring via hypergraph maximal matching. In Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 180–191. IEEE Computer Society, 2017. [GG24] Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 2148–2179. IEEE, 2024. [GGH+ 23] Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and Václav Rozhoň. Improved distributed network decomposition, hitting sets, and spanners, via derandomization. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2532–2566. SIAM, 2023.

16

[GHK+ 17] Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto. Improved distributed degree splitting and edge coloring. In Proceedings of the 31st International Symposium on Distributed Computing (DISC), volume 91 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. [GHK18] Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. On derandomizing local distributed algorithms. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 662–673. IEEE Computer Society, 2018. [GKM17] Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 784–797. ACM, 2017. [GKMU18] Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto. Deterministic distributed edge-coloring with fewer colors. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 418–430. ACM, 2018. [GS17] Mohsen Ghaffari and Hsin-Hao Su. Distributed degree splitting, edge coloring, and orientations. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2505–2523. SIAM, 2017. [Har19] David G. Harris. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 700–724. IEEE Computer Society, 2019. [Kah96] Jeff Kahn. Asymptotically good list-colorings. Journal of Combinatorial Theory, Series A, 73(1):1–59, 1996. [Kuh20] Fabian Kuhn. Faster deterministic distributed coloring through recursive list coloring. In Proceedings of the 2020 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1244–1259. SIAM, 2020. [Lin92] Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on Computing, 21(1):193–201, 1992. [MNS26] Yannic Maus, Alexandre Nolin, and Florian Schager. Brief announcement: Fast deterministic distributed degree splitting. In Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC), pages 329–332. ACM, 2026. [MPX13] Gary L. Miller, Richard Peng, and Shen Chen Xu. Parallel graph decompositions using random shifts. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 196–203. ACM, 2013. [PR01] Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed Computing, 14(2):97–100, 2001. [PS97] Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM Journal on Computing, 26(2):350–368, 1997.

17

[RG20] Václav Rozhoň and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 350–363. ACM, 2020. [SV19] Hsin-Hao Su and Hoa T. Vu. Towards the locality of Vizing’s theorem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 355–364. ACM, 2019. [SY91] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM Journal on Computing, 20(1):56–87, 1991. [Viz64] Vadim G. Vizing. On an estimate of the chromatic class of a p-graph. Diskret. Analiz, 3:25–30, 1964.

A

Deterministic Construction of Introvert Decomposition

In this appendix, we prove the deterministic construction of layered introvert decompositions (Theorem 4). Our proof is a white-box adaptation of the deterministic network decomposition algorithm of Ghaffari and Grunau [GG24]. We first develop the adaptation and prove the resulting deterministic decomposition theorem. The proof of a technical lemma needed in the base case is deferred to Appendix B. When referring to numbered lemmas, theorems, and corollaries of Ghaffari and Grunau, we use the numbering from arXiv:2410.19516v1.

A.1

High-Level Overview

We begin with a high-level overview of the deterministic construction and explain how it adapts the recursive network decomposition algorithm of Ghaffari and Grunau [GG24]. The main challenge is that a direct derandomization of our randomized construction incurs an extra logarithmic factor, while the recursive structure of their network decomposition algorithm allows us to avoid this loss. Our adaptation requires three additional ingredients: making the base case introvert, keeping track of the active edges throughout the recursion, and translating their vertex-based clustering framework to our edge-based setting through the line graph. Why a white-box adaptation is needed. Recall that our randomized construction (Theorem 3) repeatedly applies an MPX low-diameter clustering to the remaining edges and then trims the resulting clusters. Each application removes a constant fraction of the remaining edges, so O(log n) applications suffice. The known deterministic derandomizations of a single MPX-style 2 e clustering require O(log n) rounds [GGH+ 23, GG24]. Thus, derandomizing these O(log n) appli3 e cations separately would give only a O(log n)-round algorithm. Ghaffari and Grunau [GG24] overcome this extra logarithmic factor for standard network decomposition. Recall that a network decomposition partitions the vertices into O(log n) color classes such that every connected component induced by one color class has diameter O(log n). Rather than constructing the O(log n) color classes using independent deterministic low-diameter clustering steps, their algorithm constructs them together through a recursive procedure. This reduces 3 2 e e the overall complexity from O(log n) to O(log n). We adapt this recursive procedure directly.

18

1. Making the base case introvert. The clusters produced by the original construction need not satisfy our introvert condition. We modify the clustering procedure used at the base case so that each clustering step leaves only an arbitrarily small constant fraction of the edges under consideration inter-cluster. This gives enough slack to apply trimming (Lemma 1). 2. Keeping track of active edges. During the recursive algorithm, some edges are deferred to later recursive calls. Nevertheless, until an edge is assigned to a layer, it must still count toward the degree appearing in the introvert condition. We therefore maintain throughout the recursion a set of active edges, consisting of all edges that have not yet been assigned to a layer, and ensure that every introvert guarantee is measured with respect to this active edge set. This bookkeeping is needed to translate the recursive construction into the layered decomposition of Theorem 4. 3. From vertex clustering to edge clustering. The algorithm of Ghaffari and Grunau decomposes vertices, whereas our layered decomposition assigns edges to layers. We bridge this difference using the line graph. Throughout this appendix, let Line(G) denote the line graph of G: its vertices are the edges of G, and two vertices are adjacent if and only if the corresponding edges of G share an endpoint. Algorithms on Line(G) can be simulated on G with only a constant-factor overhead in the LOCAL model. We make the correspondence precise. Consider a clustering F = {F1 , . . . , Fk } of Line(G) such that distinct clusters are non-adjacent. Viewing each Fj as a subset of E(G), let Cj ⊆ V (G) be the set of endpoints of the edges in Fj , and define C = {C1 , . . . , Ck }. Since Fj and Fj ′ are non-adjacent in the line graph for j ̸= j ′ , no edge in Fj shares an endpoint with an edge in Fj ′ . Hence the sets C1 , . . . , Ck are pairwise disjoint, and C is a clustering of G. Furthermore, if every cluster Fj has weak diameter at most D in Line(G), then every cluster Cj has weak diameter at most D + 1 in G. The correspondence also gives exactly the edge counting guarantee that we need. Let A ⊆ E(G) be any set of edges, viewed equivalently as a set of vertices of Line(G). Suppose that at most η|A| vertices of A are not contained in any of the clusters F1 , . . . , Fk . If the line-graph vertex corresponding to an edge e ∈ A belongs to some cluster Fj , then both endpoints of e belong to Cj . Hence e is intra-cluster with respect to C. Therefore, every inter-cluster edge in A must correspond to an unclustered vertex of Line(G), and thus #{inter-cluster edges in A} ≤ #{unclustered vertices of A in Line(G)} ≤ η|A|. Thus, a low-diameter clustering that covers almost all vertices of the line graph translates into a low-diameter clustering of G with few inter-cluster edges. Roadmap. We first strengthen the base clustering procedure of Ghaffari and Grunau so that the fraction of vertices left unclustered can be made an arbitrarily small constant. Via the line graph correspondence above, this gives a clustering of G with an arbitrarily small fraction of inter-cluster edges, to which we can apply Lemma 1. We then insert this modified base case into their recursive framework and verify that, whenever a layer is formed, its introvert condition is measured with respect to all edges that have not yet been assigned to earlier layers. This completes the proof of Theorem 4.

A.2

Head Starts and Badness

We review the basic ingredients of the recursive framework of Ghaffari and Grunau [GG24].

19

Head starts. The clustering procedures underlying the framework are based on the same idea as MPX clustering. One way to view MPX clustering is to imagine that every vertex v ∈ V (H) grows a BFS tree, with different vertices given different head starts. If h(v) is the head start of v, we may think of the BFS tree rooted at v as starting at time −h(v). Each vertex u joins the cluster of a center whose BFS tree reaches u first, with ties broken arbitrarily. Equivalently, u chooses a center v minimizing distH (u, v) − h(v). In the original randomized MPX clustering algorithm [MPX13], the head starts are chosen randomly; in the deterministic framework of Ghaffari and Grunau, they are constructed deterministically. Badness. For a fixed vertex u, several BFS trees may reach u at the same earliest time. Controlling the number of such ties is useful because the clustering described above can then be made pairwise non-adjacent by unclustering only a small number of vertices. The notion of badness measures, for each vertex u, the maximum number of centers that can tie for the largest head start at any distance up to a prescribed radius. Formally, let h : V (H) → N≥0 be a head start function. For u ∈ V (H) and an integer r ≥ 0, let SrH (u) = {v ∈ V (H) : distH (u, v) = r}. For an integer d ≥ 0, the badness of u with respect to h and d is   H H v ∈ Sr (u) : h(v) = max h(w) . badh,d (u) = max r:

w∈SrH (u)

0≤r≤d SrH (u)̸=∅

When H is clear from context, we omit the superscript. To interpret this definition, fix a distance r from u. All vertices in SrH (u) are equally far from u, so among centers at distance r, those with the largest head start are exactly those whose BFS trees reach u first. Thus, badH h,d (u) measures the largest number of such tied centers over all distances up to d. When this quantity is small, the clustering described above can be made pairwise non-adjacent by unclustering only a small fraction of the vertices. Recursively reducing the badness. The recursive algorithm repeatedly replaces the current head start function by one with substantially smaller badness for almost all vertices. The following sampling lemma is the main tool for this reduction. Throughout Appendices A and B, we write H = Line(G), where G is the original input graph, and let N be a known polynomial upper bound on |V (H)|. We assume throughout that N is at least a sufficiently large absolute constant. This is without loss of generality, since we may replace N by max{N, N0 } for any fixed constant N0 . Lemma 3 (Ghaffari–Grunau sampling lemma [GG24, Corollary 5.2]). There is an absolute constant c for which the following holds. Let U ⊆ V (H), and consider the parameters NU ≥ |U |,

d = ⌈log N · (log log N )c ⌉ ,

B ∈ [log5 N, N ],

2

B ′ = B 1/2+1/ log log B .

Let h : V (H) → N≥0 be a head start function satisfying badH h,d (u) ≤ B for every u ∈ U . e There is a deterministic distributed algorithm that, in O(log N log B) rounds, computes a new head start function h′ : V (H) → N≥0 with the following properties. • maxv∈V (H) h′ (v) ≤ 2 maxv∈V (H) h(v) + 1.

20

′ • All but at most NU /B 3 vertices u ∈ U satisfy badH h′ ,d (u) ≤ B . 3 Thus, except for at most √ NU /B vertices, one application of Lemma 3 reduces the badness bound from B to roughly B. The recursive algorithm uses this reduction whenever B is large, recursing with the smaller parameter B ′ . Once B becomes polylogarithmic in N , the algorithm switches to a base case procedure.

Distributed knowledge. In Lemma 3, we assume that N , NU , and B are known to all vertices, and that each vertex v knows whether it belongs to U and knows its own head start h(v). We make the analogous assumptions throughout the rest of these appendices: whenever a lemma or algorithm is given subsets of V (H), numerical parameters, or a head start function, every vertex v knows the relevant parameters, its membership in the relevant subsets, and its own head start. We will omit these standard knowledge assumptions from subsequent lemma statements.

A.3

Small-Loss Clustering at the Base Case

In the base case of the recursion, where the badness is at most log10 N , Ghaffari and Grunau [GG24, Lemma 5.3] repeatedly invoke a low-diameter clustering procedure and eventually leave only a polylogarithmically small fraction of the vertices unresolved. For our construction, we will use the same repetition. However, each individual clustering step needs a stronger guarantee: before we apply trimming, the fraction of edges left inter-cluster must be an arbitrarily small constant. The reason is the loss incurred by trimming. Suppose that, after translating a clustering of Line(G) back to G, at most a ρ-fraction of some edge set is inter-cluster. By Lemma 1, if at most a ρ-fraction of the relevant edges are inter-cluster before trimming, then at most a ρ/(2ε)-fraction remain afterward. Thus, by taking ρ to be a sufficiently small constant, we obtain constant-factor progress. In the proof for the introvert base case below, we use ρ = ε/2, which leaves at most 1/4 of these edges. The following lemma gives the one-shot clustering primitive that we need. Lemma 4 (Small-loss clustering). There is an absolute constant c for which the following holds. Let H be a graph, let U ⊆ V (H), and let d = ⌈log N · (log log N )c ⌉ . Let h : V (H) → N≥0 be a head start function satisfying max h(v) ≤ log N v∈V (H)

and

10 badH h,d (u) ≤ log N

for every u ∈ U.

e For every constant ρ > 0, there is a deterministic O(log N )-round algorithm that computes a subset ′ U ⊆ U satisfying the following properties. • At most a ρ-fraction of U is left unclustered: |U \ U ′ | ≤ ρ|U |. • Every connected component of H[U ′ ] has strong diameter O(log N ). We defer the proof of Lemma 4 to Appendix B. Lemma 4 is a strengthened version of [GG24, Theorem A.1]. Our only substantive change is to strengthen the guarantee on the unclustered vertices of U : instead of allowing up to half of U to remain unclustered, we ensure that at most a ρ-fraction remains unclustered, for any constant ρ > 0. The remaining differences in the statement simply match the interface used in [GG24, Lemma 5.3]. When U ⊆ E(G) is viewed as a vertex set of Line(G), the lemma therefore gives a clustering of G in which at most ρ|U | edges of U are inter-cluster. This is the one-shot guarantee that we will use in the base case. 21

A.4

The Interface for Recursive Calls

Before describing the recursive algorithm, we first formalize the input to a recursive call and the invariants maintained throughout the recursion. This allows us to state both the base case and the recursive step more compactly. The input to a recursive call. Since H = Line(G), we identify the vertices of H with the edges of G. Every recursive call in our construction is specified by a tuple (A, U, NU , B, h), with the following interpretation. • A ⊆ E is the set of active edges: the edges that have not yet been assigned to any earlier layer of the layered introvert network decomposition. • U ⊆ A is the set of edges currently handled by the recursive call. • NU is an upper bound on |U |. • B is the current badness bound. • h : V (H) → N≥0 is the current head start function. We freely view A and U either as sets of edges of G or, equivalently, as sets of vertices of H = Line(G), without explicitly distinguishing between the two interpretations. Throughout the recursion, we maintain the following two invariants. Active set invariant. The number of active edges outside the set currently handled by the reU cursive call satisfies |A \ U | ≤ N . B3 Badness invariant. Every edge in U satisfies badH h,d (e) ≤ B. The badness invariant applies only to the edges in U . However, the edges in A\ U are still active, so they must also be included when we check the introvert condition for any layer constructed by the current call. In addition to these two invariants, we will impose an upper bound on maxv∈V (H) h(v); the appropriate bound differs between the base case and the recursive step and will be stated separately for the two cases. Appending layers. It will be convenient to formalize the output produced by a recursive call in a way that directly matches the definition of a layered introvert network decomposition. Let A be the active edge set at the beginning of the call. For t ≥ 1, an (ε, D)-valid block of t layers starting from A consists of clusterings C1 , . . . , Ct and edge sets F1 , . . . , Ft defined as follows. Set A1 = A, and for each i ∈ [t], require the following. Low diameter. Ci is a clustering of (V, Ai ), and every cluster of Ci has weak diameter at most D in G = (V, E).
Introvert property. Every v ∈ C ∈ Ci satisfies |N(V,Ai ) (v) ∩ C| ≥ 21 − ε deg(V,Ai ) (v). Layer assignment. Fi is exactly the set of intra-cluster edges of Ci in (V, Ai ), and Ai+1 = Ai \ Fi .

22

Thus, Ai is precisely the set of edges that are active at the beginning of the ith new layer, Fi is the set of edges assigned to that layer, and At+1 is the active edge set after the block has been constructed. These are exactly the three requirements in the definition of a layered introvert network decomposition, restricted to a consecutive block of layers. Valid blocks can therefore be appended one after another: if one block ends with active edge set A′ , the next block simply starts from A′ . Consequently, if we start with A = E and keep appending valid blocks until no active edge remains, then the resulting layer edge sets partition E and, together with their clusterings, form an (ε, ℓ, D)-layered introvert network decomposition, where ℓ is the total number of layers constructed.

A.5

The Base Case

With the interface for recursive calls in place, we now turn to the base case. We combine Lemma 4 with trimming to obtain the base case of our recursive construction. This plays the same role as [GG24, Lemma 5.3] in the recursion of Ghaffari and Grunau. Lemma 5 (Base case). There is an absolute constant c for which the following holds. Consider a recursive call (A, U, NU , B, h) with d = ⌈log N · (log log N )c ⌉ ,

B ∈ [log5 N, log10 N ],

max h(v) ≤ log N. v∈V (H)

e For every constant 0 < ε < 1/2, there is a deterministic O(log N )-round algorithm that constructs U an (ε, O(log N ))-valid block of O(log log N ) layers starting from A. After this block, at most N B2 edges of U remain active. Proof. Let A1 = A and U1 = U . At the beginning of iteration i, let Ai be the current active edge 10 set and let Ui = U ∩ Ai . Since Ui ⊆ U , we still have badH h,d (e) ≤ B ≤ log N for every e ∈ Ui . One iteration. Apply Lemma 4 to Ui with ρ = ε/2. Translate the resulting connected components in the line graph into a clustering Ci of G. By Lemma 4, every cluster of Ci has weak diameter O(log N ) in G. An active edge can be inter-cluster with respect to Ci only if it lies outside Ui , or if it belongs to Ui but is among the at most (ε/2)|Ui | edges left unclustered by Lemma 4. Since Ai \ Ui ⊆ A \ U , the current number of active inter-cluster edges is at most ε |A \ U | + |Ui |. 2 Now we do the trimming step. Apply Lemma 1 to Ci in the active graph (V, Ai ), and let Cbi be the resulting clustering. Every clustered vertex now satisfies the (1/2 − ε)-introvert condition with respect to Ai , and trimming does not increase the weak diameter. Let Fi be the set of intra-cluster edges of Cbi in (V, Ai ), assign Fi to the current layer, and set Ai+1 = Ai \ Fi . Thus, Ai+1 is exactly the set of active inter-cluster edges after trimming. By Lemma 1,  |A \ U | 1 1  ε |A \ U | + |Ui | = + |Ui |. |Ai+1 | ≤ 2ε 2 2ε 4 Since Ui+1 ⊆ Ai+1 , we obtain the recurrence |Ui+1 | ≤

|A \ U | 1 + |Ui |. 2ε 4 23

Residual active edges.

Iterating the recurrence for t = ⌈log4 (2B 2 )⌉ = O(log log N ) iterations: t−1

|A \ U | X −j |Ut+1 | ≤ 4 |U | + 4 2ε −t

by repeatedly applying the recurrence

j=0

2 ≤ 4 |U | + |A \ U | 3ε −t

2NU 3εB 3 2NU NU + ≤ 2 2B 3εB 3 NU NU ≤ + 2B 2 2B 2 NU = 2. B ≤ 4−t NU +

since

t−1 X

4−j ≤ 4/3

j=0

by |U | ≤ NU and the active set invariant |A \ U | ≤ NU /B 3 since t = ⌈log4 (2B 2 )⌉ since B ≥ log5 N = ω(1)

U Therefore, after this block, at most N edges of U remain active. B2

Validity and round complexity. By construction, each iteration produces one layer satisfying the three conditions of an (ε, O(log N ))-valid block: the clusters have weak diameter O(log N ), the introvert property is measured with respect to the active edge set Ai , and exactly the active intracluster edges are assigned to the layer. Therefore, the t = O(log log N ) layers form an (ε, O(log N ))valid block starting from A. e Each iteration applies Lemma 4 followed by the trimming step of Lemma 1, and takes O(log N) e rounds. Since there are O(log log N ) iterations, the total round complexity is O(log N ).

A.6

The Recursive Step

We now describe the recursive step of our construction. It enhances [GG24, Lemma 5.4] by incorU introduced above. porating the invariant about active edges |A \ U | ≤ N B3 For convenience, define    2 log B 100 log N Φ(B) = 4.5 − 1+ . log N log log B log B This is the upper bound on the maximum head start maintained in Algorithm 1 and the proof of Lemma 5.4 of Ghaffari and Grunau. Its precise form will not be important to us. For 2

B ′ = B 1/2+1/ log log B , their analysis gives 2Φ(B) + 1 ≤ Φ(B ′ )

(7) 5

whenever B is larger than a universal constant. Since throughout our recursion B ≥ log N = ω(1), the condition holds. This inequality is verified in the proof of [GG24, Lemma 5.4]; we will use it without repeating the calculation.

24

Structure of the recursive step. When B is larger than the range handled by the base case, 2 the sampling lemma first reduces the badness bound from B to B ′ = B 1/2+1/ log log B for all but at most NU /B 3 edges of U . We then make two recursive calls with parameter B ′ . The first call handles the edges satisfying this improved badness bound, and the second call handles the subset of these edges that remain active after the first call, using a smaller value of NU . U At first sight, the active set invariant |A \ U | ≤ N may seem difficult to preserve in the second B3 call: its value of NU is smaller, while we cannot rely on the number of active edges outside the set U handled by the call to decrease. The key point is that B also decreases, from B to roughly 2 B ′ = B 1/2+1/ log log B . Since the active set invariant allows NU /B 3 such edges, this decrease in B creates enough additional slack to compensate for the smaller value of NU . The proof below verifies this formally. Lemma 6 (Recursive layered introvert decomposition). There is an absolute constant c for which the following holds. Consider a recursive call (A, U, NU , B, h) with d = ⌈log N · (log log N )c ⌉ ,

B ∈ [log5 N, N ],

max h(v) ≤ Φ(B). v∈V (H)

e For every constant 0 < ε < 1/2, there is a deterministic O(log N log B)-round algorithm that constructs an (ε, O(log N ))-valid block of O(log B) layers starting from A. After this block, at most NU edges of U remain active. B2 Proof. We follow the recursion of [GG24, Lemma 5.4], while additionally carrying the active edge set A through every recursive call. Base case. Suppose that B ≤ log10 N . Since Φ(B) ≤ log N , the assumptions of Lemma 5 are satisfied, and that lemma directly gives an (ε, O(log N ))-valid block of O(log log N ) layers, leaving at most NU /B 2 edges of U active. Since B ≥ log5 N , we have O(log log N ) = O(log B), as required. 2

Inductive step. Suppose now that B > log10 N . Set B ′ = B 1/2+1/ log log B . Apply Lemma 3 to U . Let h′ be the resulting head start function, and define ′ U (1) = {e ∈ U : badH h′ ,d (e) ≤ B }.

By Lemma 3, |U \ U (1) | ≤

NU . B3

Moreover, by Lemma 3 and (7), max h′ (v) ≤ 2 max h(v) + 1 ≤ 2Φ(B) + 1 ≤ Φ(B ′ ), v∈V (H)

v∈V (H)

Thus h′ satisfies the head start requirement for recursive calls with parameter B ′ . First recursive call. We first recurse on U (1) , keeping the full active edge set A. The active set invariant is preserved because |A \ U (1) | = |A \ U | + |U \ U (1) | ≤

2NU NU ≤ , 3 B (B ′ )3

where the last inequality holds because B ′ = o(B). The badness invariant holds by the definition of U (1) . Hence the induction hypothesis applies to (A, U (1) , NU , B ′ , h′ ). 25

Let A(2) be the active edge set after this first recursive call, and set U (2) = U (1) ∩ A(2) . NU By the induction hypothesis, |U (2) | ≤ (B ′ )2 . We therefore define (2)

NU =

NU . (B ′ )2

Second recursive call. We now recurse on U (2) with active edge set A(2) . An edge of A(2) \ U (2) must already have been outside U (1) before the first recursive call. Therefore, the active set invariant is satisfied: (2) NU NU 2NU (2) (2) (1) ≤ = , |A \ U | ≤ |A \ U | ≤ B3 (B ′ )5 (B ′ )3 NU ′ 5 3 (2) ⊆ U (1) , the badness invariant U where the inequality 2N ≤ (B ′ )5 is due to (B ) ∈ o(B ). Since U B3 (2)

remains valid. Thus the induction hypothesis applies to (A(2) , U (2) , NU , B ′ , h′ ). Residual active edges. We append the valid block produced by the second recursive call to the one produced by the first. By the definition of a valid block, their concatenation is again a valid block starting from A. It remains to bound the number of edges of the original set U that are still active. Such an edge either belongs to U \ U (1) , or belongs to U (2) and survives the second recursive call. Hence their number is at most (2) NU NU NU NU NU + = 3 + < 2, B3 (B ′ )2 B (B ′ )4 B 2

due to the choice of B ′ = B 1/2+1/ log log B . Number of layers and round complexity. As in the proof of [GG24, Lemma 5.4], a standard 2 analysis of the recursion with two subproblems with parameter B 1/2+1/ log log B and B ≤ log10 N being the base case shows that there are O(log B/ log log N ) base case calls. Each base case cone structs O(log log N ) layers in O(log N ) rounds, so the total number of layers is O(log B), and the e total round complexity is O(log N log B).

A.7

Completing the Deterministic Construction

We now apply Lemma 6 to the original graph and complete the proof of Theorem 4. Theorem 4 (Deterministic layered introvert decomposition). For every constant ε ∈ (0, 1/2), 2 e an (ε, O(log n), O(log n))-layered introvert network decomposition can be constructed in O(log n) rounds deterministically. Proof. Let G = (V, E) and let H = Line(G). Choose a common polynomial upper bound N such that |V (H)| = |E| < N and N ≥ 2. Since we may take N = poly(n), we have log N = O(log n). For the initial recursive call, set A = U = E,

NU = N,

26

B = N,

and let h(v) = 0 for every v ∈ V (H). The two invariants are immediate. Indeed, A \ U = ∅, and, for every e ∈ U , badH h,d (e) ≤ |V (H)| < N = B. Moreover, |U | < N = NU and maxv∈V (H) h(v) = 0 ≤ Φ(B). Thus, all assumptions of Lemma 6 are satisfied. Applying Lemma 6 gives an (ε, O(log N ))-valid block of O(log N ) layers starting from A = E. U After this block, the number of edges of U = E that remain active is at most N = N1 < 1. B2 A valid block that starts with active edge set E and ends with no active edge forms a layered introvert network decomposition: its layer edge sets partition E, and every layer satisfies the required diameter and introvert conditions. We therefore obtain an (ε, O(log N ), O(log N ))-layered introvert network decomposition of G. 2 e e Finally, Lemma 6 runs in O(log N log B) = O(log n) rounds. Since log N = O(log n), the resulting decomposition has parameters (ε, O(log n), O(log n)), completing the proof.

B

Proof of the Small-Loss Clustering Lemma

In this appendix, we prove the small-loss clustering lemma (Lemma 4) used in the base case of Appendix A. While both Appendices A and B are based on adapting the algorithm of Ghaffari and Grunau [GG24], the nature of the adaptation is different. In Appendix A, the introvert condition forces us to take into account all active edges, including those outside the set handled by a recursive call. This requires changing the invariants maintained by the recursion and carefully checking that the modified invariants remain valid. For this reason, we gave an essentially complete proof of the recursive construction there. The modification needed here is conceptually simpler. The base case of Ghaffari and Grunau clusters at least half of the relevant vertices, whereas we need the fraction left unclustered to be an arbitrarily small constant ρ > 0. The particular constant 1/2 is not essential to their construction. Rather than reproducing their entire proof, we therefore follow its structure and examine each step that contributes to this constant loss, verifying that each such loss can be made arbitrarily small.

B.1

From Small Badness to Small Frontiers

We first restate the lemma to be proved. Lemma 4 (Small-loss clustering). There is an absolute constant c for which the following holds. Let H be a graph, let U ⊆ V (H), and let d = ⌈log N · (log log N )c ⌉ . Let h : V (H) → N≥0 be a head start function satisfying max h(v) ≤ log N v∈V (H)

and

10 badH h,d (u) ≤ log N

for every u ∈ U.

e For every constant ρ > 0, there is a deterministic O(log N )-round algorithm that computes a subset ′ U ⊆ U satisfying the following properties. • At most a ρ-fraction of U is left unclustered: |U \ U ′ | ≤ ρ|U |. • Every connected component of H[U ′ ] has strong diameter O(log N ). We use the following small-loss version of [GG24, Theorem A.1]. For a head start function h, the r-hop frontier of a vertex u consists of the vertices whose shifted distance distH (u, v) − h(v) is within r of the minimum possible value. Formally, it is the set of vertices v satisfying distH (u, v) − h(v) ≤ min (distH (u, w) − h(w)) + r. w∈V (H)

27

Lemma 7 (Small-loss version of [GG24, Theorem A.1]). Let H be a graph, let U ⊆ V (H), and let e h : V (H) → N≥0 be a head start function satisfying maxv∈V (H) h(v) = O(log N ). Suppose that, for 10 100 every u ∈ U , the log log N -hop frontier of u has size at most log N . Then, for every constant e ρ > 0, there is a deterministic O(log N )-round algorithm that computes a subset U ′ ⊆ U satisfying the following properties. • At most a ρ-fraction of U is left unclustered: |U \ U ′ | ≤ ρ|U |. • Every connected component of H[U ′ ] has strong diameter O(log N ). The proof of Lemma 7 is deferred to Appendix B.2. We first show that it implies Lemma 4. Proof of Lemma 4. Let   q = log20 log N and define the scaled head start function e h(v) = qh(v). We verify that e h satisfies the assumptions of Lemma 7. Fix u ∈ U and consider a vertex v in the log10 log N -hop frontier of u with respect to e h. First, v is at distance at most d from u. Indeed, by taking w = u in the definition of the frontier, distH (u, v) − e h(v) ≤ −e h(u) + log10 log N, and hence distH (u, v) ≤ e h(v) − e h(u) + log10 log N ≤ q log N + log10 log N ≤ d, where the last inequality holds for a sufficiently large choice of the constant c in the definition of d. Next, among all vertices at distance r = distH (u, v) from u, the vertex v must have maximum head start with respect to h. Indeed, if some vertex w at the same distance satisfied h(w) > h(v), then e h(w) − e h(v) ≥ q > log10 log N, which contradicts the assumption that v belongs to the frontier. Consequently, for every distance r ≤ d, the number of frontier vertices at distance r from u is 10 at most badH h,d (u) ≤ log N . Therefore, the entire frontier has size at most (d + 1) log10 N ≤ log100 N. Moreover, e max e h(v) ≤ q log N = O(log N ).

v∈V (H)

Thus e h satisfies all assumptions of Lemma 7. Applying that lemma gives a subset U ′ ⊆ U e satisfying the required two properties in O(log N ) rounds.

B.2

Reducing the Frontier Size

The proof of [GG24, Theorem A.1] consists of two steps, captured by their Theorems A.2 and A.3. We use the following small-loss versions of these two results. Lemma 8 (Small-loss version of [GG24, Theorem A.2]). There is an absolute constant c for which the following holds. Let H be a graph, let U ⊆ V (H), and let h : V (H) → N≥0 be a head start e function satisfying maxv∈V (H) h(v) = O(log N ). Suppose that, for every u ∈ U , the log10 log N -hop frontier of u has size at most log100 N . Then, for every constant ρ > 0, there is a deterministic e O(log N )-round algorithm that computes a subset U ′ ⊆ U and a head start function h′ : V (H) → N≥0 satisfying the following properties. 28

• |U \ U ′ | ≤ ρ|U |. e • maxv∈V (H) h′ (v) = O(log N ). • For all u ∈ U ′ , the log2 log N -hop frontier of u with respect to h′ has size at most (log log N )c . Proof. We use exactly the algorithm and analysis of [GG24, Theorem A.2]. The only difference between Lemma 8 and [GG24, Theorem A.2] is that Ghaffari and Grunau fix ρ =  0.1. In their notation, [GG24, Claim A.7] shows that, after iteration i, the set Ui satisfies |Ui | ≥ 1 − log102ilog N |U |. The algorithm performs O(log2 log N ) iterations. Hence the fraction of vertices discarded is already O(1/ log8 log N ), which is not just at most 0.1 but also at most any constant ρ, as required. Lemma 9 (Small-loss version of [GG24, Theorem A.3]). For every constant c ≥ 1, the following holds. Let H be a graph, let U ⊆ V (H), and let h : V (H) → N≥0 be a head start function satisfying e maxv∈V (H) h(v) = O(log N ). Suppose that, for every u ∈ U , the log2 log N -hop frontier of u has e size at most (log log N )c . Then, for every constant ρ > 0, there is a deterministic O(log N )-round ′ algorithm that computes a subset U ⊆ U satisfying the following properties. • At most a ρ-fraction of U is left unclustered: |U \ U ′ | ≤ ρ|U |. • Every connected component of H[U ′ ] has strong diameter O(log N ). We prove Lemma 9 in Appendix B.3. We can now complete the proof of the small-loss version of [GG24, Theorem A.1]. Proof of Lemma 7. Apply Lemma 8 with parameter ρ/2. This gives a subset U1 ⊆ U and a head start function h′ such that |U \ U1 | ≤ (ρ/2)|U |, and the log2 log N -hop frontier of every u ∈ U1 with respect to h′ has size at most (log log N )c . We can therefore apply Lemma 9 to U1 and h′ , again with parameter ρ/2. Let U ′ ⊆ U1 be the

2 resulting set. Then |U ′ | ≥ 1 − ρ2 |U1 | ≥ 1 − ρ2 |U | ≥ (1 − ρ)|U |. Moreover, every connected e component of H[U ′ ] has strong diameter O(log N ). Both applications take O(log N ) rounds, so the e total round complexity is also O(log N ).

B.3

From Small Frontiers to Low-Diameter Clusters

The proof of [GG24, Theorem A.3] is a direct application of their Theorem A.11. Before stating the small-loss version that we need, we introduce two notions used in that theorem. Clustering terminology.

For a vertex u and a cluster C of H, let distH (u, C) = min distH (u, v). v∈C

For two clusters C and C ′ , let distH (C, C ′ ) =

min

u∈C, v∈C ′

distH (u, v).

A clustering C is s-separated if distH (C, C ′ ) ≥ s for every two distinct clusters C, C ′ ∈ C. For a vertex u, the s-hop degree of u with respect to C is the number of clusters C ∈ C satisfying distH (u, C) ≤ s. The s-hop degree of C is the maximum s-hop degree over all vertices clustered by C. These definitions agree with [GG24, Definition A.2]. We only need Theorem A.11 in the particular parameter regime arising in the proof of Theorem A.3, so we state its small-loss version directly in this regime. 29

Lemma 10 (Small-loss version of [GG24, Theorem A.11]). For every constant c ≥ 1, the following holds. Set   2 log log N and DEG = (log log N )c . s= 3 e Let C be a clustering of a graph H with weak diameter O(log N ) and s-hop degree at most DEG. Let R be the set of vertices clustered by C. For every constant ρ > 0, there is a deterministic e O(log N )-round algorithm that computes a clustering Cout satisfying the following properties. • Every cluster has strong diameter O(log N ). • The clustering is 2-separated. • All vertices clustered by Cout belong to R, and at least (1 − ρ)|R| vertices of R are clustered by Cout . The proof of Lemma 10 is given in Appendix B.4. We first show that it implies Lemma 9. Proof of Lemma 9. We follow the proof of [GG24, Theorem A.3]. Let Ch be the head start clustering obtained by assigning every vertex u ∈ V (H) to a vertex v ∈ V (H) minimizing distH (u, v) − h(v), e e with ties broken consistently. Since maxv∈V (H) h(v) = O(log N ), Ch has strong diameter O(log N ). Set s and DEG as in the statement of Lemma 10. We claim that every vertex u ∈ U has s-hop degree at most DEG with respect to Ch . To see this, consider a cluster of Ch with center v whose distance from u is at most s. Let x be a vertex of this cluster with distH (u, x) ≤ s, and let w minimize distH (u, w) − h(w). Then distH (u, v) − h(v) ≤ distH (u, x) + distH (x, v) − h(v) ≤ distH (u, x) + distH (x, w) − h(w)

by the triangle inequality since x is assigned to v

≤ distH (u, x) + distH (u, w) + distH (u, x) − h(w) by the triangle inequality ≤ 2s + distH (u, w) − h(w)

since distH (u, x) ≤ s.

Thus the center v belongs to the 2s-hop frontier of u. Since 2s ≤ log2 log N , every cluster within distance s of u has a distinct center in the log2 log N -hop frontier of u. By the assumption of Lemma 9, this frontier has size at most (log log N )c = DEG. Hence the s-hop degree of u is at most DEG. Let C be obtained from Ch by retaining only the vertices in U in each cluster. Then C clusters e exactly U , has weak diameter O(log N ), and has s-hop degree at most DEG. We may therefore apply Lemma 10 to C with parameter ρ. Let U ′ ⊆ U be the set of vertices clustered by the resulting clustering Cout . By Lemma 10, |U \ U ′ | ≤ ρ|U |, and Cout is 2-separated, so the connected components of H[U ′ ] are precisely e its clusters and hence have strong diameter O(log N ). The round complexity is O(log N ), as required.

B.4

Iterative Small-Boundary Clustering

We now prove Lemma 10. The proof follows [GG24, Theorem A.11]. The main modification is in [GG24, Lemma A.14], which extracts a reasonably large clustering whose boundary is at most a fixed constant fraction of its size. We show that this constant can be made arbitrarily small. The preceding subsampling step, [GG24, Lemma A.12], is used without any modification.

30

Lemma 11 (Small-loss version of [GG24, Lemma A.14]). For all constants c ≥ 1 and δ > 0, the following holds. Set   2 log log N and DEG = (log log N )c . s= 3 e Let C be a clustering of a graph H with weak diameter O(log N ) and s-hop degree at most DEG, e and let R be the set of vertices clustered by C. There is a deterministic O(log N )-round algorithm that computes a 2-separated clustering D using only vertices of R. Let X ⊆ R be the set of vertices clustered by D. Then the following properties hold. • |X| ≥ |R|/(16DEG). e • Every cluster of D has weak diameter O(log N ). • At most δ|X| vertices of R \ X have a neighbor in X. Proof. We follow the proof of [GG24, Lemma A.14]. First apply [GG24, Lemma A.12]: using e log2 (DEG) log N ) rounds, it computes an s-separated clustering C ′ of weak diameter O(s e log N ) O(s ′ ′ that clusters at least |R|/(8DEG) vertices, all belonging to R. For each C ∈ C and k ≥ 0, define  ′ = v ∈ R : distH (v, C ′ ) ≤ k . C≤k For each C ′ , we look for a radius k ≤ ⌊s/3⌋ satisfying ′ ′ |. | ≤ (1 + δ)|C≤k |C≤k+1

If no such radius exists, then ′ |C≤⌊s/3⌋ | > (1 + δ)⌊s/3⌋ |C ′ |. ′ Since C ′ is s-separated, the sets C≤⌊s/3⌋ are pairwise disjoint. Hence the total number of vertices ′ belonging to clusters C for which no suitable radius exists is at most

(1 + δ)−⌊s/3⌋ |R| ≤

|R| , 16DEG

where the inequality follows from s = Θ(log2 log N ) and DEG = (log log N )c . Since C ′ initially clusters at least |R|/(8DEG) vertices, after discarding the clusters for which no suitable radius exists, at least |R|/(16DEG) vertices remain. For every remaining cluster C ′ , ′ . These output clusters remain 2-separated and have weak choose such a radius k and output C≤k e diameter O(log N ). ′ Finally, every vertex of R outside the output clustering that is adjacent to C≤k belongs to ′ ′ ′ C≤k+1 \ C≤k . By the choice of k, this set has size at most δ|C≤k |. Summing over all output clusters shows that at most δ|X| vertices of R \ X are adjacent to X. The only modification from the proof of [GG24, Lemma A.14] is replacing its fixed growth e log2 (DEG) log N ) factor by 1 + δ; all other steps are unchanged. The call to Lemma A.12 takes O(s e log N ) + O(s) rounds. By the rounds, while the subsequent ball growing and carving take O(s e choice of s and DEG, the total round complexity is O(log N ). Proof of Lemma 10. It suffices to consider 0 < ρ < 1. Set δ = ρ/4. We follow the iterative construction in the proof of [GG24, Theorem A.11].

31

Let C0 = C and let C0out be empty. In iteration i, apply Lemma 11 to Ci , obtaining a 2-separated out . Then obtain C clustering Di . Add the clusters of Di to Ciout to obtain Ci+1 i+1 from Ci by removing all vertices clustered by Di , together with all remaining vertices that have a neighbor in one of these clusters. For a clustering A, write V (A) for the set of vertices clustered by A. By Lemma 11, out |V (Ci+1 )| − |V (Ciout )| ≥

|V (Ci )| . 16DEG

All newly clustered vertices are removed from Ci . Therefore, out |V (Ci )| − |V (Ci+1 )| ≥ |V (Ci+1 )| − |V (Ciout )|,

and hence

 |V (Ci+1 )| ≤

1 1− 16DEG

 |V (Ci )|.

Deleting vertices from the input clustering cannot increase its weak diameter or its s-hop degree, so Lemma 11 remains applicable in every iteration. Also, before proceeding to the next iteration we remove all vertices adjacent to the newly extracted clusters. Thus clusters extracted in different iterations are non-adjacent, and Ciout remains 2-separated. Run the procedure for   4 T = 16DEG ln ρ iterations. Then  |V (CT )| ≤

1 1− 16DEG

T |R| ≤

ρ |R|. 4

Across all iterations, the total number of vertices discarded because they are adjacent to extracted clusters is at most δ|V (CTout )|. Consequently, |R| ≤ (1 + δ)|V (CTout )| + |V (CT )|, and therefore, using δ = ρ/4, |V (CTout )| ≥

 1 − ρ/4 ρ |R| ≥ 1 − |R|. 1 + ρ/4 2

e Thus CTout is a 2-separated clustering of weak diameter O(log N ) that clusters at least a (1 − ρ/2)fraction of R. It remains only to obtain strong diameter. We use the well-known fact that, for every graph on at most N vertices and every β > 0, one can remove at mosta β-fraction of the vertices so that every  log N ; see, e.g., [CL23, EN16]. Apply remaining connected component has strong diameter O β this fact to the subgraph induced by each cluster of CTout , with β = ρ/2. Since these clusters have e weak diameter O(log N ), each induced subgraph can be gathered and the decomposition computed e locally in O(log N ) rounds, with all clusters processed in parallel. The resulting clustering remains

2 2-separated, has strong diameter O(log N ), and clusters at least 1 − ρ2 |V (CTout )| ≥ 1 − ρ2 |R| ≥ (1 − ρ)|R| vertices. e Since T = O(DEG) and DEG = (log log N )c , the total round complexity remains O(log N ).

32