PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Edge Ranking of Trees

Jeff Giliberti, MohammadTaghi Hajiaghayi, Changki Yun

arXiv:2610.12438v1cs.DS

TL;DR

Whether tree edge ranking is in NC or P-complete remained open, and which P-complete problems can be efficiently parallelized in MPC with strongly sublinear local memory was poorly understood. The paper compresses information from subtree merges to compute optimal tree edge rankings deterministically in MPC. Deciding whether T has edge ranking at most K is P-complete under logspace many-one reductions, even for trees of diameter at most six; bounds are O(n3/4D1/4) local memory and O(log D + log log n) rounds.

  • Problem

    Whether tree edge ranking is in NC or P-complete remained open, and which P-complete problems can be efficiently parallelized in MPC with strongly sublinear local memory was poorly understood.

    Source: §1 · pp. 2–3

  • Method

    The paper compresses information from subtree merges to compute optimal tree edge rankings deterministically in MPC.

    Source: §1 · p. 3

  • Results

    Deciding whether T has edge ranking at most K is P-complete under logspace many-one reductions, even for trees of diameter at most six; bounds are O(n3/4D1/4) local memory and O(log D + log log n) rounds.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The paper establishes that P-completeness does not preclude efficient MPC parallelization for this tree problem.

    Source: §1 · p. 3

    The MPC construction is analyzed for local memory S between n^3/4 and n; when a claimed bound is at least n, the tree is gathered on one machine.

    Source: §4.3 · p. 26

Abstract

from arXiv · show

In this work, we prove that computing the edge ranking of a tree in parallel is P-Complete. An optimal tree edge ranking assigns positive integer ranks to the edges such that any two edges with the same rank are separated by an edge of higher rank, while minimizing the highest rank. Tree edge ranking abstracts several classical problems such as parallel assembly in manufacturing, minimum-height dendrograms, reversible pebble game and edge-query binary search on trees. Its parallel complexity remained open for over thirty years, since the seminal work of de la Torre, Greenlaw, and Sch{\"a}ffer [SODA'93], and was listed as an open problem in the book Limits to Parallel Computation by Greenlaw, Hoover, and Ruzzo [1995]. We prove that deciding whether a tree has edge ranking at most $K$ is P-Complete, already for trees of diameter six. Our reduction is from NOR-CVP and simulates a greedy procedure underlying known sequential approaches. Despite ruling out NC algorithms, we prove that this hardness barrier can be bypassed in the well-known model of Massively Parallel Computation (MPC) with strongly sublinear local memory, showing that $O(\log n)$ MPC rounds suffice to solve the hard tree-edge ranking instances used to prove P-Completeness. Specifically, we present a deterministic MPC algorithm that computes an optimal edge ranking of an $n$-vertex tree of diameter $D$ in $O(\log D+\log\log n)$ rounds with $O(n^{3/4}D^{1/4})$ local memory. Our algorithm circumvents the linear-memory barrier by compressing the information required to produce a lexicographically minimal ranking from subtree merges. Overall, this result reinforces the strict separation between NC and what can be computed efficiently in MPC.

1 Introduction

Tree edge ranking, with applications including minimum-height dendrograms and reversible pebble games, had an open parallel-complexity question. The paper proves P-completeness even at diameter six and gives a deterministic MPC algorithm using strongly sublinear local memory.

1 Introduction

  • Even for trees of diameter at most six, deciding whether an edge ranking of at most K exists is P-complete under logspace many-one reductions.This resolves the longstanding question of whether tree edge ranking is in NC or P-complete.Source: §1 · p. 2

1.1.2 Edge ranking in MPC

  • The cited result reports O(n^(3/4)D^(1/4)) local memory and O(log D + log log n) rounds; with fixed O(S) memory per machine, solved subtree size grows by at least n^δ per stage.O(1/δ) = O(1) stages reach the whole tree; auxiliary tree operations take O(log D) rounds and dominate the round term.Source: §1 · p. 3, §1.1.2 · p. 6

1.1 Technical overview

  • The technical overview uses the lexicographically least visible set, called the critical set, to characterize a tree's edge-ranking number.A rank is visible when no larger rank lies between its edge and the root; computing the critical set determines the optimal ranking number.Source: §1.1 · pp. 3–4

1.1.1 P-completeness of edge ranking

  • The reduction encodes NOR-CVP evaluation in a greedy allocation procedure, then represents each allocation requirement with a tree branch to obtain edge-ranking instances.The branch construction uses O(log^2 q) vertices for requirement q, and the resulting reduction has small-diameter trees.Source: §1.1.1 · pp. 4–5

1.1.2 Edge ranking in MPC

  • For MPC, one exact representative per shared maximum rank compresses child critical sets, keeping the retained representations within O(n^3/4) words.This addresses the problem that combining interval representations of child sets can produce a linear-size list at their parent.Source: §1.1.2 · p. 5

2 Preliminaries

The preliminaries define the complexity framework and tree-ranking terminology, then develop critical sets and branch labeling as a way to characterize realizable rankings. They also specify the NOR-circuit reduction setting and MPC tools used in the paper.

2 Preliminaries

  • NC is characterized by uniform polylogarithmic-depth circuits or polynomial-processor PRAMs, while P-completeness uses logspace many-one reductions.A logspace reduction preserves yes/no membership and is computed with O(log N) workspace.Source: §2 · p. 7
  • An edge ranking assigns positive integer ranks so equal-ranked edges are separated by a higher-ranked edge, and an optimal ranking minimizes the maximum rank.The maximum rank of an optimal ranking is denoted er(T).Source: §2 · p. 7

2.1 Critical sets and branch labeling

  • A critical set is the minimum-weight visible set; branch labeling combines child visible sets, with each child requiring allocated weight at least its critical-set weight plus one.For a vertex, realizability is characterized by pairwise-disjoint rank subsets meeting those child weight requirements.Source: §2.1 · pp. 7–8

2.2 Circuits and logspace reductions

  • A NOR circuit is a topologically ordered list of constant nodes and NOR gates whose inputs come from earlier nodes.The output is the value of the final node.Source: §2.2 · p. 10

2.3 MPC primitives

  • MPC distributes input across machines with bounded local memory and communication per synchronous round; sorting, prefix sums, and aggregation take O(1) rounds for S=n^Ω(1).Rooting a tree and computing depths, subtree sizes, and preorder numbers takes O(log D) rounds.Source: §2.3 · p. 10

3 Edge ranking of trees is P-complete

This section completes a logspace reduction from NOR-CVP to tree edge ranking, encoding greedy rank-allocation requirements in trees of diameter at most six and using a final test tied to the circuit output. It also establishes P-completeness of the associated labeling problem.

3.1 The greedy allocation

  • GreedyAllocation assigns rank weights in decreasing order, rejecting when one residual needs at least twice the current weight or two residuals each need at least that weight.Otherwise it subtracts the weight from the unique eligible residual or covers a branch with the largest residual; a run never rejects exactly when an allocation exists.Source: §3.1 · p. 11

3.2 Requirement lists as trees

  • For a requirement list q, er(T(q)) ≤ K exactly when GreedyAllocation on q and ranks K,…,1 never rejects.The tree gadgets realize each branch requirement as the weight of its critical set plus one.Source: §3.2 · pp. 12–13

3.3 Circuit encoding

  • Circuit values are encoded as residuals: 1 uses one branch of weight 128u, while 0 uses two branches with residuals 3u + 1 and 3u.At the output scale, a test branch of requirement 128u rejects for output 1, while output 0 can be allocated; the construction reserves later weights to cover other residuals.Source: §3.3 · p. 13

3.4 Relays and wires

  • Two chained relays implement each wire: together they deliver the gate-input branches and forward the original source bit’s signal to the next relay.Each relay complements its forwarded signal, so the pair restores the source bit while delivering one gate input.Source: §3.4 · p. 16

3.5 Gates

  • The gate leaves signal H(u) exactly when both incoming bits are 1, and L(u) otherwise; receiving the complemented predecessor bits therefore computes NOR.The gate’s three scheduled weights transform the input residuals into the output signal while leaving branches below 192u unchanged.Source: §3.5 · pp. 17–18

3.6 The schedule and the invariant

  • The schedule maintains an invariant at each node’s scale: earlier wires carry complemented source values, later branches remain untouched, and the current node’s signal records its value.After the final node block, only its signal, the test branch, and garbage remain uncovered.Source: §3.6 · pp. 18–19
  • The schedule invariant carries ¬b_i along each outgoing wire through relay pairs; at a gate, merging the predecessor signals leaves b_i, while a constant node retains its stated signal.The proof applies the relay and gate/padding bounds to show the invariant across successive circuit nodes.Source: §3.6 · p. 19

3.7 Completing the reduction

  • The reduction’s output test rejects at its tested weights exactly when the circuit output bit b_m is 1.The constructed instance satisfies er(T(q)) ≤ K if and only if b_m = 0.Source: §3.7 · pp. 19–20
  • The map from a circuit to (T(q), K) is logspace-computable, with O(m^3) tree vertices, diameter at most six, and K ≤ 111m + 22.The construction’s bounds and logspace computability are given for circuits with m records.Source: §3.7 · p. 20
  • Tree edge ranking is P-complete under logspace reductions even on trees of diameter at most six.Membership follows from Lam and Yue’s polynomial-time algorithm [LY98b, LY01]; hardness follows by reducing topologically ordered NOR-CVP [GHR95, Problems A.1.2 and A.1.5].Source: §3.7 · pp. 20–21
  • The labeling problem—deciding whether max Lab(A_1, …, A_d) ≤ K—is P-complete under logspace many-one reductions.The reduction represents each requirement q by the length-K bit vector of q − 1 and uses its equivalence to the tree-ranking instance.Source: §3.7 · p. 21

4 An MPC algorithm

This section presents a staged MPC algorithm for solving tree edge ranking by compressing child branches and merging rankings of progressively larger subtrees. It uses representatives, counts, and size thresholds to organize computations across machines while trading local memory for round complexity.

4.1 One representative per maximum

  • For each maximum rank, retaining only a minimum-weight critical set and counting the other branches preserves the optimal labeling; distinct maxima at a vertex are at most √(2N_v).The retained-set bound follows because children realizing distinct maxima have subtree sizes of at least 2, 3, and so on.Source: §4.1 · p. 22

4.2 Labeling with counted branches

  • Counted branches can be labeled in batches while keeping an optimal labeling in O(M + m + g + 1) words and a compact description of their labels.The batch labels are represented by O(m + g + 1) segments; the final batch-label set is derived from batch spans after excluding ordinary-branch labels.Source: §4.2 · pp. 24–25

4.3 Solving one subtree on one machine

  • When light subtrees are solved, their critical sets can be compressed and routed with heavy vertices to one machine, which evaluates and reconstructs the subtree in O(1) rounds using O(S) words.The machine retains a minimum-weight record per light-child group with the same maximum, counts the remaining branches, and processes heavy vertices in postorder.Source: §4.3 · p. 26

4.4 Size thresholds

  • The size thresholds B_j are nondecreasing and bounded by S^(4/3)/H^(1/3); B_L reaches n when S ≥ n^a_L H^(1−a_L), where a_L = 3·4^(L−1)/(4^L−1).Here σ = S/H, and the thresholds are defined for σ ≥ 1.Source: §4.4 · p. 27
  • The staged algorithm solves pieces up to increasing size thresholds, then solves the whole tree once a threshold reaches n.Stage 1 uses the sequential algorithm of Lam and Yue; later stages merge already-solved light pieces, and each stage takes O(1) rounds.Source: §4.4 · pp. 27–28
  • For S = n^(3/4+δ)H^(1/4), where H ≤ D + 1, the algorithm uses O(S) words of local memory and O(log D) rounds for fixed δ.Source: §4.4 · p. 28
  • Processing depths from leaves upward also computes an optimal ranking in O(D) rounds with S = n^3/4 local memory.Each depth takes O(1) rounds, and subtrees rooted at that depth are disjoint.Source: §4.4 · pp. 28–29
  • The arithmetic-threshold construction reduces each piece to a path of heavy vertices and solves its bottom subtree before processing the remaining path.The resulting critical ranking is optimal; the full procedure takes O(log D + J) = O(n/S + log D) rounds.Source: §4.4 · pp. 29–30
  • For n^3/4 ≤ S ≤ n, arithmetic thresholds give O(n/S + log D) rounds, O(S) local memory, and O(n) total memory.The thresholds are B_j = jS; the construction avoids using tree height or vertex depths.Source: §4.4 · pp. 29–30

AI Usage

The authors report using ChatGPT 6 Pro in developing Theorem 1.2 and ChatGPT-6-Astra and Claude Opus 5.5 to assist with presentation. They state that they checked the mathematical arguments and take responsibility for the content.

AI Usage

  • Theorem 1.2 developed through interaction with ChatGPT 6 Pro, starting from an unpresented O(log D)-round 2-approximate edge-ranking idea.The authors tested the model alongside strongly sublinear representations of critical sets, resulting in a diameter-sensitive MPC algorithm.Source: AI Usage · p. 31
  • While optimizing the general-case algorithm, the authors tested complexity hypotheses, including Theorem 1.1 in its primitive form.The passage describes this as part of the theorem-development process.Source: AI Usage · p. 31
  • ChatGPT-6-Astra and Claude Opus 5.5 assisted with presentation, while the authors say they checked the mathematical arguments and take responsibility for the content.The authors explicitly retain responsibility for all content.Source: AI Usage · p. 31
Loading 2610.12438v1…