Truly Work-efficient Parallel Deterministic $(Δ+1)$-coloring and Maximal Independent Set

TRULY WORK-EFFICIENT PARALLEL DETERMINISTIC (∆ + 1)-COLORING AND MAXIMAL INDEPENDENT SET Chase Hutton∗ chutton6@umd.edu

Adam Melrod† amelrod@math.harvard.edu

Abstract. We give deterministic parallel algorithms that compute a (∆ + 1)-coloring and a maximal independent set for a simple graph with n vertices and m edges in O(n + m) work and O(poly log n) depth.

arXiv:2608.08296v1 [cs.DS] 8 Aug 2026

1. Introduction In the maximal independent set (MIS) problem, we are given a graph G with n vertices and m edges, and the task is to output a setM ⊆ V (G) such that no two vertices of M are neighbors but every vertex outside of M has a neighbor in M . In the (∆ + 1)-coloring problem, the task is to color every vertex by a number in {0, . . . , ∆}, where ∆ is the maximum degree of G, so that no edge is monochromatic. Sequentially, both problems are solved by the same greedy procedure in O(n + m) time: the vertices are processed in an arbitrary order, and the solution is extended at each vertex in accordance with its previously processed neighbors. The question of matching this trivial linear bound in parallel has driven research in parallel computing since the early 1980s [KW85; Lub86; ABI86]. To make the question precise, we adopt the standard work–depth model [JáJ92]. The work of a parallel algorithm is the total number of operations it performs, and its depth is the length of its longest chain of sequentially dependent operations. A parallel algorithm should therefore have small depth and, more importantly, it should not perform substantially more work than its sequential counterpart: an algorithm with superlinear work is slower than the trivial sequential algorithm unless the number of available processors exceeds the work overhead. Accordingly, we call an algorithm for either problem work-efficient if its work is O(n + m), matching the sequential greedy bound, and its depth is polylogarithmic in n. For randomized algorithms the question has largely been resolved. The classical algorithms of Luby [Lub86] and of Alon, Babai, and Itai [ABI86] cost linear work and run in O(log n) rounds. Blelloch, Fineman, and Shun [BFS12] later showed that the sequential greedy algorithm for MIS, applied to a uniformly random vertex order, admits a direct parallelization. Notably, the parallelization performs O(n + m) work regardless of the order, and only its depth guarantee, logarithmic with high probability [FN18], depends on the randomness. For deterministic algorithms, which are the subject of this paper, the question has proved far more resistant. The natural route to a deterministic parallel algorithm is to derandomize a randomized one, and parallel derandomization is a classical subject in its own right. Karp and Wigderson e 3) [KW85] initiated it with a deterministic MIS algorithm of polylogarithmic depth and O(n work. Luby [Lub86] showed that his randomized algorithm can be derandomized by exhaustively searching a pairwise-independent sample space of quadratic size, giving O(log2 n) time on O(mn2 ) processors, and later removed this penalty through the method of conditional probabilities [Lub93]. General-purpose derandomization techniques followed [MNN94; BR91], as did sharper algorithms for MIS: Goldberg and Spencer [GS89b; GS89a] brought the work to ∗ †

University of Maryland, College Park, MD. Harvard University, Cambridge, MA. 1

2

C. HUTTON AND A. MELROD

O (n + m) log2 n in polylogarithmic depth, and Han [Han96] computes an MIS in O(log2.5 n)

time on O (m+n)/ log1.5 n processors, for a total of O (n+m) log n work. Most recently, Ghaffari, Grunau, and Rozhoň developed a program of parallel derandomization [GGR23; GG24b] of Chernoff-like bounds, that for example is applicable to edge coloring. State of the Art. Following their contributions to derandomizing Chernoff-like bounds, Ghaffari and Grunau [GG25] developed derandomized algorithms with (n + m) poly(log log n) work and polylogarithmic depth for MIS and maximal matching. Their algorithms derandomize a hitting set abstraction that captures maximal matching and, in a more involved form, MIS, and that has the potential to apply to a broader class of problems. The method rounds fractional assignments to integral ones over Θ(log n) stages whose accumulated errors are governed by an extremely intricate potential analysis. Moreover, the application of their method to the MIS problem requires a significant amound of additional work. Ghaffari and Grunau pose explicitly the question of whether the remaining poly(log log n) overhead can be removed and true work efficiency reached. For (∆ + 1)-coloring, the best known deterministic bound is the O (n + m) log2 n) work algorithm given by Han [Han96], building off of Luby’s work providing a O (n + m) log3 n log log n) work solution [Lub93]. No better algorithm has appeared in the three decades since. Two further lines of work deserve mention. When the maximum degree of the graph is constant, work-efficient deterministic algorithms for both problems have long been known through the deterministic coin tossing technique of Cole and Vishkin [CV86; GPS88]. In the distributed and massively parallel settings, deterministic round-efficient algorithms for coloring and MIS have advanced considerably [RG20; GK21; GG24a; Coy+24], but simulating a round-efficient message-passing algorithm is inherently inefficient. On general graphs, among the three classical symmetry-breaking problems, only maximal matching was known to admit a work-efficient deterministic parallel algorithm [Kel94; Han95]. Whether MIS or (∆ + 1)-coloring admits one has remained open. Our Contributions and Paper Organization. This paper answers the question in the affirmative for both problems. Theorem 1.1 (cf. Corollary 5.2). A maximal independent set of any graph can be computed deterministically in O(n + m) work and poly(log n) depth. Theorem 1.2 (cf. Corollary 5.3). A (deg+1)-coloring of any graph—and in particular a (∆+1)coloring—can be computed deterministically in O(n + m) work and poly(log n) depth. To the best of our knowledge, these are the first work-efficient deterministic parallel algorithms for either problem. Theorem 1.2 improves the best known deterministic work bound for (∆ + 1)coloring by a factor of log2 n, Theorem 1.1 removes the final poly(log log n) overhead of [GG25], and together with the maximal matching algorithms of Kelsen and Han they complete the picture for the three classical symmetry-breaking problems. The complete argument, including all proofs, is elementary and short, and it employs no derandomization tool beyond the pairwiseindependence framework of Luby [Lub93] in the linear-work form given to it by Han [Han95]. Our approach rests on the observation that both MIS and (deg + 1)-coloring are extendable: a partial solution determines a residual instance on any set of unprocessed vertices at the cost of inspecting each edge joining that set to the processed part exactly once—for MIS by deleting the vertices that neighbor the current independent set, and for coloring by removing from each list the colors of processed neighbors. A solution may therefore be assembled piece by piece, exactly as in the sequential greedy procedure, at a cost of O(n + m) for all extension steps.

TRULY WORK-EFFICIENT PARALLEL DETERMINISTIC (∆+1)-COLORING AND MAXIMAL INDEPENDENT SET 3

The computation on these pieces can be made cheap deterministically by an edge-balanced partitioning routine that constitutes the technical core of the paper. Theorem 4.2 shows that, in O(n+m) work and poly(log n) depth, the vertex set of any graph can be partitioned intopoly(L) parts whose induced subgraphs jointly contain at most m/L edges. The partition is computed by recursive bisection which decreases the internal edges in each part by a factor of 5/12. This balance is enforced combinatorially by pairing vertices of consecutive degrees requiring that every pair be in different parts of the final partition. Derandomization enters only in computing such a partition: the number of edges cut by a random bipartition is a sum of functions of pairs of coordinates of the assignment, this is an instance of Luby’s bit-pair benefit problem [Lub93], which Han’s refinement [Han95] solves in O(n + m) work. Together, these ingredients upgrade any suboptimal deterministic algorithm for an extendable problem to a work-efficient one. By taking L = loga n, the pieces jointly contain at most m/ loga n edges, so an algorithm suboptimal by a factor of loga n solves all of them in O(m) total work. We isolate this as Theorem 5.1. For MIS, the instances arising on the pieces are ordinary MIS instances, and any of the deterministic algorithms with poly log n overhead discussed earlier can serve as the subroutine. For coloring, the pieces carry list instances, since colors used by earlier neighbors are removed from the palettes, and we use the algorithm of Luby [Lub93], which, while presented as a (∆ + 1)-coloring algorithm, directly works with no modification to produce a coloring by palettes of size deg + 1, provided they are in sorted order. This yields Theorems 1.1 and 1.2. In Section 3 we review Luby’s benefit problems, and give a self-contained linear-work solution of the bit pair benefit problem in the style of Han. In Section 4 we construct the deterministic sparse partition. In Section 5 we prove the bootstrapping theorem and derive the algorithms for MIS and (deg + 1)-coloring. 2. Preliminaries Model of computation. We work in the standard work–depth model [JáJ92; Ble96]: an algorithm runs on p processors sharing a memory, its work W (A) is the total number of its computational steps, and its depth D(A) is the length of its longest chain of sequentially dependent steps. The underlying machine is the common CRCW PRAM [KR90] in which concurrent reads of a memory location are unrestricted, and concurrent writes are permitted only when all writers write the same value. We note that our maximal independent set algorithm requires no concurrent writes and runs on the weaker CREW PRAM machine while our coloring algorithm requires them only in its extension step, when the colors already used among the neighbors of a vertex are recorded. Throughout, a machine word consists of Θ(log n) bits, where n is the number of vertices of the input graph, and the standard arithmetic, comparison, and bitwise operations on words each cost a single step. The input graph is provided as an array of n vertices and each vertex v possesses an array listing the neighbors of v. Basic subroutines. All prefix sums of an array of k numbers can be computed in O(k) work and O(log k) depth [JáJ92]. As a consequence, an array can be filtered within the same bounds: the entries satisfying a predicate testable in constant time can be moved into a contiguous array in their original order. Sorting k items under constant-time comparisons costs O(k log k) work and O(log k) depth [Col88]. We further use the following two sorting lemmas. Lemma 2.1. A list of m items with integer keys in [1, R] can be stable sorted deterministically in O(m + R) work and O(R + log m) depth. Proof. Partition the items into ⌈m/R⌉ blocks of at most R consecutive items. Each block, in parallel, computes sequentially in O(R) time its key histogram and the rank of each of its items

4

C. HUTTON AND A. MELROD

among equal keys within the block. The histograms form an R × ⌈m/R⌉ matrix of counts with O(m + R) entries, and a prefix sum over this matrix in key-major order [JáJ92] yields, for every key and block, the starting position of that block’s items with that key in the sorted output. Each item then computes its output position in O(1) from its block’s starting position and its within-block rank. □ Lemma 2.2 (Degree sort). The vertices of any graph with n vertices and m edges can be stable sorted by degree deterministically in O(n + m) work and O(log n) depth. Proof. Set θ := ⌈log n⌉ and split the vertex list, by a filter, into the vertices of degree at most θ and the remaining vertices, each group retaining its input order. The first group is stable sorted by Lemma 2.1 with key range [1, θ + 1], at a cost of O(n + θ) work and O(θ + log n) = O(log n) depth. Since the degrees sum to 2m, the second group contains at
most 2m/θ vertices, and it is sorted by parallel merge sort [Col88] at a cost of O (m/θ) log m = O(m) work and O(log n) depth. Every degree in the first group is smaller than every degree in the second, so the concatenation of the two sorted lists is the stable sorted output, and the total cost is O(n + m) work and O(log n) depth. □ 3. Benefit problems The general benefit problem as formulated by Luby in [Lub93] is as follows: let B be a function, called the benefit function, from {0, 1}n → R. A point x ∈ {0, 1}n is good if B(x) ≥ Eα [B(α)] where α is a uniformly random point of {0, 1}n , that is the benefit of x is at least the average benefit. The benefit problem for B is then to efficiently find a good point. While Luby formulates the general benefit problem, he solves it in restricted cases where pairwise independence can be exploited to shrink the seed space; this is sufficient for many applications. 3.1. Bit pair benefit problem. The bit pair benefit problem assumes that the benefit function can be written as a sum of auxiliary functions X X B(x) = B(x1 , . . . , xn ) = Ψuv (xu , xv ) + Ψu (xu ) + c. u<v

u

Given a representation exists with at most m nonzero auxiliary functions computable in constant time, that function B is called a bit pair benefit function of size m. This representation is exploited by observing that if the bits xu are pairwise independent and uniform, the expected value is the same as if the entire x was uniformly sampled. As such, the size of the seed space can be dramatically reduced to the point where binary searching the seed space for a good point solves the problem with logarithmic overhead. Evaluating the quantities needed to do the binary search takes O(m) work. This is the approach taken by Luby in [Lub93], which solves the benefit problem for B deterministically in O((n + m) log2 n) work and O(log2 n) depth. The inefficiency of this approach is primarily due to evaluating the benefit function at every step of the binary search. Han [Han95] later exploited, following an observation of Luby, that if one tracks the influence of each constraint more carefully, a linear algorithm can be obtained. After modifying the auxiliary functions so that they only depend on the xor of their inputs (which can be done without changing the expectation overall), each constraint is only relevant to deciding one of the bits of the seed of a good point. By grouping the relevant constraints together, redundant work is eliminated. The paper of Han only applies this observation to the problem of maximal matching, but it applies generally, and we require a slightly more complicated form. Thus, we now prove the following theorem by the same approach.

TRULY WORK-EFFICIENT PARALLEL DETERMINISTIC (∆+1)-COLORING AND MAXIMAL INDEPENDENT SET 5

of size m, and corresponding Theorem 3.1. Given a collection of constraint pairs P ⊆ [n] 2 auxiliary functions Ψp : {0, 1} → R, the benefit problem for X Ψp (xu ⊕ xv ) B(x) := p={u,v}∈P

can be solved deterministically in O(n + m) work and O(log m log n) depth. Here P may be a multiset, in which case repeated pairs contribute additively. This costs nothing below and is convenient for our later application in Section 4. Ψ (0)+Ψ (1) Ψ (0)−Ψ (1) We first normalize the problem. Writing Ψp (y) = p 2 p +βp (−1)y with βp := p 2 p , we obtain X βp (−1)xu ⊕xv . B(x) = Eα [B(α)] + p={u,v}∈P

A good point is therefore a point at which the weighted sum

P

p βp (−1)

xu ⊕xv is nonnegative.

3.2. Fixing a seed instead of the variables. Following Luby, we do not choose the bits xu directly but draw them from a small structured space and apply conditional expectations to the seed of that space, which has only O(log n) bits. Set ℓ := ⌈log2 n⌉ and regard each index u ∈ {0, . . . , n − 1} as an ℓ-bit string. For a seed r ∈ {0, 1}ℓ , define xu (r) :=

ℓ M

ut rt .

t=1

This is the pairwise independent space given in Luby’s original paper [Lub93]. For a constraint p = {u, v}, ℓ M xu (r) ⊕ xv (r) = (dp )t rt , dp := u ⊕ v ̸= 0, t=1

so the value of the constraint is the sum mod two of the seed coordinates at the positions where dp has a set bit, and at least one such position exists. Suppose some such position t is unfixed, and write the value of the constraint as rt ⊕b, where b is the sum mod two of the seed coordinates at the remaining set bits of dp . Conditioned on arbitrary values of every coordinate other than rt , the bit b is determined while rt is uniform, so the value of the entire constraint is uniform as long as any nonzero bit of dp is unfixed. In particular, under a fully uniform seed every constraint is a uniform bit and Er [B(x(r))] = Eα [B(α)] follows by linearity of expectation. The following structure essentially observed by Han in a less general form [Han95], is the only new input to Luby’s original strategy. Define the stage of p as t(p) := max{t : (dp )t = 1}, the most significant set bit of dp , and for 0 ≤ t ≤ ℓ let   Φt := Er B(x(r)) r1 , . . . , rt be the expectation over a uniform choice of the remaining seed coordinates. Lemma 3.2. Fix the seed coordinates in the order r1 , r2 , . . . , rℓ . Then Φ0 = E[B(α)], and for each stage t, X M Φt − Φt−1 = (−1)rt Ft , Ft := βp (−1)sp , sp := (dp )t′ rt′ . p : t(p)=t

t′ <t(p)

Proof. A constraint with t(p) > t has the unfixed coordinate t(p) in its support, so its conditional Ψ (0)+Ψ (1) expectation after stage t is the constant p 2 p , regardless of the choices made; in particular P Ψp (0)+Ψp (1) Φ0 = p = E[B(α)]. A constraint with t(p) ≤ t has all of its support fixed, and its 2 value is Ψp (sp ⊕rt(p) ). Having fixed the first t−1 bits of the seed, setting bit t of the seed changes

6

C. HUTTON AND A. MELROD

only the contribution of the constraints with t(p) = t. Accounting for the normalization, the change is thus  X  X Ψ (0)+Ψ (1) Ψp (sp ⊕ rt ) − p 2 p βp (−1)sp ⊕rt = (−1)rt Ft . □ = t(p)=t

t(p)=t

Lemma 3.2 determines the algorithm. Group the constraints by stage; then for t = 1, . . . , ℓ in order, compute Ft by a parallel sum over the group of stage t, and set rt := 0 if Ft ≥ 0 and rt := 1 otherwise, so that Φt − Φt−1 = |Ft |. After the last stage every constraint is determined, so ℓ X B(x(r)) = Φℓ = Eα [B(α)] + |Ft | ≥ Eα [B(α)], t=1

and x(r) is a good point. Each constraint participates in exactly one stage, which is the source of the linear work bound. It remains to implement the grouping and the quantities sp within it. 3.3. Implementation in linear work. Each index, each dp , and the seed occupy single words. The algorithm uses two lookup tables, indexed by the 2ℓ ≤ 2n possible words and computed before the stages begin. The table MSB stores in entry w ≥ 1 the position of the most significant set bit of w, and the table Par stores in entry w the parity of the bits of w. The table MSB is computed in O(n) work and O(1) depth: in parallel over t ∈ {1, . . . , ℓ} and over the entries w ∈ [2t−1 , 2t ), entry w is set to t, and since these ranges partition the index set, every entry is written exactly once. The table Par is computed by induction on the word length. Write Parj for the table over j-bit words. The table Par0 consists of the single entry Par[0] = 0, and Parj+1 agrees with Parj on its first half and satisfies Par[w + 2j ] = 1 ⊕ Par[w] on its second half, so it is obtained from Parj by one parallel copy and complement. The ℓ rounds cost O(2ℓ ) = O(n) total work and O(log n) depth. Given the tables, the quantities dp = u ⊕ v and t(p) = MSB[dp ] are computed in constant work per constraint. At stage t(p), let r denote the word whose bits at the positions fixed so far are the chosen seed coordinates, and let ∧ denote bitwise conjunction. The conjunction dp ∧ r ∧ (2 t(p)−1 − 1) retains exactly the bits (dp )t′ rt′ for t′ < t(p), since the mask 2 t(p)−1 − 1 removes the decisive position and every higher position. Therefore   sp = Par dp ∧ r ∧ (2 t(p)−1 − 1) , and the evaluation costs constant work per constraint. The grouping of the constraints by decisive stage is a stable integer sort with keys t(p) ∈ {1, . . . , ℓ}. By Lemma 2.1 with key range R = ℓ = O(log n), the sort costs O(n + m) work and O(log n + log m) depth, and it places the constraints of each stage in a contiguous segment of a single array. The value Ft is then computed at stage t by one parallel sum over the segment of stage t, in O(log m) depth. 4. Sparse Partitioning In this section, we consider the task of partitioning the vertices of a graph G with m edges into k pieces V1 , . . . , Vk such that the number of edges among the induced subgraphs G[V1 ], . . . , G[Vk ] sum to at most m/L. We call such a partition an L-sparse k-partition. For our applications in Section 5, it will be convenient to define a particular representation of such a partition. Call a neighbor v of a vertex u ∈ Vi left, internal, or right according to whether v lies in V1 ∪ · · · ∪ Vi−1 , in Vi , or in Vi+1 ∪ · · · ∪ Vk , and call u isolated if it has no internal neighbors. The partition is ordered if the adjacency array of every vertex lists its left neighbors first, then its internal ones,

TRULY WORK-EFFICIENT PARALLEL DETERMINISTIC (∆+1)-COLORING AND MAXIMAL INDEPENDENT SET 7

then its right ones, with the two block boundaries marked, and each piece Vi stores the list Ii of its isolated vertices. Our main technical lemma is a linear deterministic procedure to construct a single edgebalanced vertex partition. Lemma 4.1. The vertices of any graph G may be divided into two parts so that the induced subgraphs H1 and H2 both have at most 5m/12 edges, deterministically in O(n + m) work and O(poly log n) depth. Iterating this routine, we obtain the following construction of sparse partitions. Theorem 4.2. For any graph, an ordered k-sparse (poly k)-partition can be computed deterministically in O(n + m + poly k) work and O(log k poly log n) depth. Proof. We compute the partition by a recursion of t := ⌈log6/5 k⌉ levels, whose parts form a binary tree rooted at the whole vertex set. At each level, every part containing at least one edge is split by an application of Lemma 4.1 into a left and a right child, each inducing at most 5/12 of the edges of the part, while edgeless parts remain leaves. The parts after level j therefore contain at most (5/6)j m edges in total, which is at most m/k after t levels, and the number of parts is at most 2t ≤ 2k 1/ log2 (6/5) = O(k 4 ). The output parts V1 , . . . , VP are the leaves of the tree in left-to-right order. The recursion maintains two invariants. Each part holds its vertices in two lists, the active vertices, which have a neighbor inside the part, and the isolated vertices, which have none. Furthermore the partition is ordered, that is the adjacency array of every vertex lists first its neighbors in parts to the left of its own, then its internal neighbors, and finally its neighbors in parts to the right, with two indices, the left and the right delimiter, marking the ends of the internal range. Initially the whole vertex set is one part and every neighbor is internal, and at termination the second invariant is precisely desired the representation in the theorem. A part with an edge is split as follows. Let A be its set of active vertices. The subgraph G[A] is bisected by Lemma 4.1 into the vertex sets A1 and A2 of the left and the right child, and the isolated list of the parent is passed to the isolated list of the left child by a pointer. Every vertex of A records its side in a global array side, with one entry per vertex of G, allocated at the beginning of the procedure. The internal range of each vertex of A is then partitioned using a filter based on the side array and delimiters updated so that the second invariant is maintained. Finally, for each child, the newly isolated vertices are extracted from the current vertices by a filter and added to their respective isolated lists. An entry of an adjacency array is touched only while the endpoints of its edge share a part, and a vertex is never read after the split at which it becomes isolated. A part with m′ edges
′ j has at most 2m active vertices, so the work of level j is O (5/6) m apart from a constant for passing down pointers. The total work is thus O(n + m) +

t−1 X

O (5/6)j m + O 2t = O(n + m + k 4 ).

j=0

Each level costs O(poly log n) depth by Lemma 4.1, so the depth is O(log k poly log n).

□

4.1. Edge-balanced vertex partition. In order to give an algorithm to compute the desired partition of Lemma 4.1, we will instantiate a bit pair benefit problem adapted to the balancing guarantee we need. As a first step, we stable sort the vertices of G by degree using Lemma 2.2, obtaining a list u1 , . . . , un with deg(ui ) ≤ deg(ui+1 ) in which the vertices of degree zero occupy a prefix. If n is not even, introduce a dummy vertex of degree zero and place it at the front of the list. We then consider the involution σ : V → V defined by mapping u2k−1 7→ u2k and u2k 7→

8

C. HUTTON AND A. MELROD

u2k−1 for each 1 ≤ k ≤ n/2. The provided involution satisfies where ∆ is the max degree of the graph G. To see this, write X

| deg(u) − deg(σu)| = 2

u∈V

n/2 X

P

u∈V | deg(u) − deg(σu)| ≤ 2∆,

deg(u2k ) − deg(u2k−1 )

k=1

≤2

n−1 X

deg(ui+1 ) − deg(ui ) = 2(deg(un ) − deg(u1 )) ≤ 2∆.

i=1

This property implies that partitions of V which respect the involution satisfy a good balancing guarantee. Lemma 4.3. If V = V1 ∪ V2 is a partition so that σV1 = V2 , then |m1 − m2 | ≤ ∆/2, where m1 and m2 are the number of edges in the subgraphs induced by V1 and V2 respectively, and ∆ is the maximum degree of the graph G. Proof. We may write the sum of degrees of vertices in V1 and V2 respectively as X X deg(u) = 2m1 + |c(V1 , V2 )| and deg(u) = 2m2 + |c(V1 , V2 )| u∈V1

u∈V2

where c(V1 , V2 ) denotes the cut edges of the partition. Therefore |m1 − m2 | =

X 1 X 1 X deg(u) − deg(u) − deg(σu) deg(u) = 2 2 u∈V1

≤

1 X 2

u∈V1

u∈V2

| deg(u) − deg(σu)| =

u∈V1

1X 4

| deg(u) − deg(σu)| ≤ ∆/2.

□

u∈V

Proof of Lemma 4.1. Suppose first that ∆ > 2m/3. Then the partition splitting the vertex v of maximum degree from the remaining vertices already suffices: the first part induces no edges, and the second induces m − deg(v) < m − 2m/3 = m/3 ≤ 5m/12 edges. This case is detected and executed in O(n + m) work and O(log n) depth, so we may assume ∆ ≤ 2m/3. Under this assumption, it suffices to produce an involution splitting partition whose cut contains at least m/2 edges. Indeed, such a partition satisfies m1 + m2 ≤ m/2, and combining with Lemma 4.3, m1 + m2 |m1 − m2 | m ∆ m m 5m + ≤ + ≤ + = . max(m1 , m2 ) ≤ 2 2 4 4 4 6 12 To find such a partition, start with an involution splitting partition V = S ∪ σS, say S = {u2k : 1 ≤ k ≤ n/2}. Given a partition P = {P1 , P2 } of S, we obtain another involution splitting partition V P = {V1P , V2P } of V where V1P = P1 ∪ σP2 and V2P = σP1 ∪ P2 . An assignment x = x1 . . . xn/2 ∈ {0, 1}n/2 corresponds to the partition P (x) = {{si : xi = 0}, {sj : xj = 1}} of S, and thus induces the partition V x := V P (x) of V . Writing si := u2i , the number of cut edges of V x is X X X B(x) := c(V1x , V2x ) = 1[xi ̸= xj ]+ 1[xi ̸= xj ]+ 1[xi = xj ], {si ,sj }∈G[S]

{σsi ,σsj }∈G[σS]

{si ,σsj }∈c(S,σS)

the last sum reflecting that si and σsj land in the same part exactly when xi ̸= xj . Both indicators are functions of xi ⊕ xj alone, so B is a benefit function of size m over n/2 variables in the sense of Theorem 3.1. The parallel constraints arising from distinct edges are permitted

TRULY WORK-EFFICIENT PARALLEL DETERMINISTIC (∆+1)-COLORING AND MAXIMAL INDEPENDENT SET 9

since P may be a multiset. Each nonconstant term has expectation 1/2, and the constant terms contribute 1, so under a uniform assignment, we have E[B(x)] ≥ m/2, and solving the benefit problem by Theorem 3.1 yields x with c(V1x , V2x ) = B(x) ≥ E[B(x)] ≥ m/2. This splitting of V induced by x therefore satisfies the desired guarantee of the lemma. As for the complexity, the degree sort costs O(n + m) work and O(log n) depth by Lemma 2.2. The construction of the involution, the benefit instance, and the final partition are single scans of the vertex and edge lists, and the benefit problem costs O(n + m) work and O(log m log n) depth by Theorem 3.1, giving the stated bounds. □ 5. Derandomizing maximal independent set and graph coloring We now give deterministic algorithms that compute a maximal independent set and a (deg+1)coloring in linear work. Both follow the same scheme. Theorem 4.2 first partitions the graph into polylogarithmically many pieces inducing O(m/L) edges in total, and the pieces are then processed from left to right. Before a piece is solved, the partial solution on the preceding pieces are extended: for MIS, vertices with a neighbor in the current independent set are deleted, and for coloring, the palettes of each vertex are updated by removing colors already used by its neighbors. This leaves a self-contained instance on the piece, which one of Luby’s deterministic algorithms [Lub93] solves with work optimal up to a polylogarithmic factor, after which the next piece is processed in the same way. Taking L a sufficiently large power of log n makes the subroutine calls cost O(m) in total, while the updates cost O(n + m), as they charge each vertex only its degree. Theorem 5.1 states the scheme abstractly, and the two corollaries following it verify its hypotheses. One point requires care. The partition bounds the number of edges inside the pieces but not the number of vertices. Thus, naively applying Luby’s algortihm to each piece of the partition can cost Ω(n poly log n) work. Hypothesis (A) therefore requires that an isolated vertex of an instance be resolvable in constant work. Deleting the isolated vertices leaves an instance with at most twice as many vertices as edges, so the cost of each call to the subroutine is governed by the number of edges of its piece, and the sparsity of the partition makes the total linear. Theorem 5.1. Let Π be a graph problem with the following two properties. (A) There is a deterministic procedure which, given disjoint U, W ⊆ V (G), a solution s of Π on G[U ], and access to the cut (U, W ) and to
G[W ], outputs an instance of Π on a subgraph of G[W ] of size O |W | + |E(G[W ])| , such that any solution of the instance P combines with s
to give a solution of Π on G[U ∪ W ]. The procedure performs O v∈W (1 + degG (v)) work in O(poly log n) depth, and an isolated vertex of the instance can be resolved and deleted in O(1) work. (B) Π admits a deterministic algorithm solving any instance with n′ vertices, m′ edges, and
a size O(n′ + m′ ) in O (n′ + m′ ) log n work and O(poly log n) depth, for some constant a. Then Π can be solved deterministically in O(n + m) work and O(poly log n) depth. Proof. Set L := loga n and let V1 , . . . , VP be the partition given by Theorem 4.2 P for k = L, 4a computed in O(n+m) work and O(poly log n) depth, so that P = O(log n) and i mi ≤ m/L, where mi := |E(G[Vi ])|. Write V<i := V1 ∪ · · · ∪ Vi−1 . The partition is ordered, so the adjacency array of each v ∈ Vi lists its neighbors in V<i and then those in Vi , providing the access to the cut and to G[Vi ] that (A) assumes for the pair U = V<i , W = Vi . Process the parts in sequence, maintaining a solution si−1 of Π on G[V<i ]. At step i, apply (A) with U = V<i and W = Vi to obtain an instance Ti on a subgraph of G[Vi ]. Each piece Vi has its

10

C. HUTTON AND A. MELROD

isolated vertex list, so those vertices of Ti can be resolved and deleted immediately. This leaves the instance Ti′ given by the remaining vertices. We run the algorithm of (B) on Ti′ , and combine its output with si−1 to form si . By (A) and induction on i, each si solves Π on G[V1 ∪ · · · ∪ Vi ], so sP solves Π on G. Every edge of G is inspected at most twice, once from the part of each endpoint, so the extension steps cost P X X
 O 1 + degG (v) = O(n + m) i=1

v∈Vi

work in total. Resolving and deleting isolated vertices costs O(n) work in total. As Ti′ has at most mi edges and every vertex not originally in the isolated vertex list is incident to one of a those mi edges, this instance has at most 2m i vertices, so the call to (B) costs O(mi log n)
work, and these sum to O loga n · m/ loga n = O(m). Including the partition itself, the work is O(n + m). The parts are processed sequentially and each costs O(poly log n) depth, so the depth is O(poly log n) as P = O(poly log n). □ Corollary 5.2. A maximal independent set of any graph can be computed deterministically in O(n + m) work and O(poly log n) depth. Proof. The independent set is maintained globally as an indicator array. We verify (A). Given a maximal independent set M of G[U ], each v ∈ W forms an auxiliary array over its left neighbors, filled by the respective neighbors indicator values. A parallel reduction over the auxiliary array decides whether v has a neighbor in M . We then delete all such vertices, and output H := G[W \ D]. All of this performs
O(1 +′ degG (v)) work at each v in O(log n) depth, and the size of H is O |W | + |E(G[W ])| . If M is a maximal independent set of H, then M ∪ M ′ , formed by setting the bits of M ′ in the indicator, is a maximal independent set of G[U ∪ W ]; any new incidence would have to come from a cut edge, and all such vertices were removed from consideration in the update step. An isolated vertex of H is resolved by placing it in the independent set, which is sound because it has a neighbor neither in M nor in H, and two isolated vertices are never adjacent. Property (B) holds by any of the deterministic MIS algorithms of [Lub93; GS89b; Han96], so Theorem 5.1 applies. □ Corollary 5.3. A (deg+1)-coloring of any graph can be computed deterministically in O(n+m) work and O(poly log n) depth. In particular, so can a (∆ + 1)-coloring. Proof. We verify (A). Given a proper coloring φ of G[U ] from its palettes, each v ∈ W computes its residual palette C ′ (v) := C(v) \ {φ(u) : u ∈ NG (v) ∩ U } as follows: in a Boolean array indexed by {1, . . . , degG (v) + 1}, each adjacency entry of v holding a neighbor u ∈ U with φ(u) ≤ degG (v) + 1 marks the cell φ(u), and v then stably filters C(v), keeping the unmarked colors. Colors above degG (v) + 1 never lie in C(v), so C ′ (v) is as claimed, and stability ensures the palette remains sorted. This costs O(degG (v) + 1) work at each v and O(log n) depth. At most degU (v) colors are removed, so |C ′ (v)| ≥ degG (v) + 1 − degU (v) ≥ degG[W ] (v) + 1. Each palette C ′ (v) is then truncated to size deg(v) + 1. The resulting graph G[W ] with the palettes C ′ is again an instance of (deg +1)-coloring. No vertex of W retains a color used by a neighbor in U , so any proper coloring from the palettes C ′ combines with φ into one of G[U ∪W ], and an isolated vertex is resolved by the first color of its palette, which is nonempty. For (B), the subroutine receives an instance of the above form with n′ vertices and m′ edges, after which we apply the deterministic coloring algorithm from Luby’s paper [Lub93]. We remark here that Luby’s coloring algorithm is presented as only using ∆ + 1 colors, but his exact algorithm works

REFERENCES

11

given that each vertex v has a sorted palette C(v) of size deg(v) + 1, so we may apply it to our instance. □ References [ABI86]

N. Alon, L. Babai, and A. Itai. “A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem”. In: Journal of Algorithms 7.4 (1986), pp. 567–583. doi: 10.1016/0196-6774(86)90019-2. [BR91] B. Berger and J. Rompel. “Simulating (logc n)-Wise Independence in NC”. In: Journal of the ACM 38.4 (1991), pp. 1026–1046. doi: 10.1145/115234.115347. [Ble96] G. E. Blelloch. “Programming Parallel Algorithms”. In: Communications of the ACM 39.3 (1996), pp. 85–97. doi: 10.1145/227234.227246. [BFS12] G. E. Blelloch, J. T. Fineman, and J. Shun. “Greedy Sequential Maximal Independent Set and Matching are Parallel on Average”. In: Proceedings of the TwentyFourth Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA. 2012, pp. 308–317. doi: 10.1145/2312005.2312058. arXiv: 1202.3205. [Col88] R. Cole. “Parallel Merge Sort”. In: SIAM Journal on Computing 17.4 (1988), pp. 770– 785. doi: 10.1137/0217049. [CV86] R. Cole and U. Vishkin. “Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking”. In: Information and Control 70.1 (1986), pp. 32–53. doi: 10.1016/S0019-9958(86)80023-7. [Coy+24] S. Coy, A. Czumaj, P. Davies-Peck, and G. Mishra. “Parallel Derandomization for Coloring”. In: 2024 IEEE International Parallel and Distributed Processing Symposium. IPDPS. 2024, pp. 1058–1069. [FN18] M. Fischer and A. Noever. “Tight Analysis of Parallel Randomized Greedy MIS”. In: Proceedings of the Twenty-Ninth Annual ACM–SIAM Symposium on Discrete Algorithms. SODA. 2018, pp. 2152–2160. [GG24a] M. Ghaffari and C. Grunau. “Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS”. In: 65th IEEE Annual Symposium on Foundations of Computer Science. FOCS. 2024, pp. 2148–2179. doi: 10.1109/FOCS61266. 2024.00007. arXiv: 2410.19516. [GG24b] M. Ghaffari and C. Grunau. “Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC. 2024, pp. 1889–1900. arXiv: 2311.13771. [GG25] M. Ghaffari and C. Grunau. “Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set”. In: 66th IEEE Annual Symposium on Foundations of Computer Science. FOCS. 2025, pp. 2694–2727. arXiv: 2504.15700. [GGR23] M. Ghaffari, C. Grunau, and V. Rozhoň. “Work-Efficient Parallel Derandomization I: Chernoff-Like Concentrations via Pairwise Independence”. In: 64th IEEE Annual Symposium on Foundations of Computer Science. FOCS. 2023, pp. 1551–1562. arXiv: 2311.13764. [GK21] M. Ghaffari and F. Kuhn. “Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition”. In: 62nd IEEE Annual Symposium on Foundations of Computer Science. FOCS. 2021, pp. 1009–1020. doi: 10.1109/ FOCS52979.2021.00101. arXiv: 2011.04511. [GPS88] A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. “Parallel Symmetry-Breaking in Sparse Graphs”. In: SIAM Journal on Discrete Mathematics 1.4 (1988), pp. 434–446.

12

[GS89a]

REFERENCES

M. K. Goldberg and T. H. Spencer. “A New Parallel Algorithm for the Maximal Independent Set Problem”. In: SIAM Journal on Computing 18.2 (1989), pp. 419– 427. doi: 10.1137/0218029. [GS89b] M. K. Goldberg and T. H. Spencer. “Constructing a Maximal Independent Set in Parallel”. In: SIAM Journal on Discrete Mathematics 2.3 (1989), pp. 322–328. doi: 10.1137/0402028. [Han95] Y. Han. “An Improvement on Parallel Computation of a Maximal Matching”. In: Information Processing Letters 56.6 (1995), pp. 343–348. [Han96] Y. Han. “A Fast Derandomization Scheme and Its Applications”. In: SIAM Journal on Computing 25.1 (1996), pp. 52–82. doi: 10.1137/S0097539790192702. [JáJ92] J. JáJá. An Introduction to Parallel Algorithms. Addison-Wesley, 1992. [KR90] R. M. Karp and V. Ramachandran. “Parallel Algorithms for Shared-Memory Machines”. In: Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. Ed. by J. van Leeuwen. Elsevier, 1990, pp. 869–941. [KW85] R. M. Karp and A. Wigderson. “A Fast Parallel Algorithm for the Maximal Independent Set Problem”. In: Journal of the ACM 32.4 (1985), pp. 762–773. doi: 10.1145/4221.4226. [Kel94] P. Kelsen. “An Optimal Parallel Algorithm for Maximal Matching”. In: Information Processing Letters 52.4 (1994), pp. 223–228. doi: 10.1016/0020-0190(94)90130-9. [Lub86] M. Luby. “A Simple Parallel Algorithm for the Maximal Independent Set Problem”. In: SIAM Journal on Computing 15.4 (1986), pp. 1036–1053. doi: 10.1137/0215074. [Lub93] M. Luby. “Removing Randomness in Parallel Computation without a Processor Penalty”. In: Journal of Computer and System Sciences 47.2 (1993), pp. 250–286. doi: 10.1016/0022-0000(93)90033-S. [MNN94] R. Motwani, J. Naor, and M. Naor. “The Probabilistic Method Yields Deterministic Parallel Algorithms”. In: Journal of Computer and System Sciences 49.3 (1994), pp. 478–516. [RG20] V. Rozhoň and M. Ghaffari. “Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization”. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. STOC. 2020, pp. 350–363. arXiv: 1907.10937.

Related documents

• Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling#1117362
• Greedy-Like Defective Coloring: Distributed Algorithms and Applications#999838
• Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings#183190
• Bounded Independence Edge Subsampling in Graphs#347579
• The Secretary Problem with a Stochastic Precursor#216841