A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation

Yuxi Wang; Jungyeul Park

cs.CLMar 29, 2026

A gentle tutorial on Bock's algorithm for minimum directed spanning trees with a structured reformulation

Authors: Yuxi Wang, Jungyeul Park

Organizations: UBC, Canada · KAIST, South Korea

Abstract

Bock's 1971 algorithm is an exact primal--dual method for the minimum-cost arborescence problem, but its Algol presentation obscures the interaction of its maintained arrays and label-directed control flow. We provide a self-contained tutorial comprising the original listing, a line-mapped explanation, a circuit-forming three-node example, and a complete trace of Bock's ten-node instance. We also present a structured reformulation that replaces temporary span-label changes with explicit component and trace state. Local tightness and contraction-progress results, together with an operational-correspondence theorem, establish that the reformulation preserves Bock's candidate choices, transfers, and final solution.

Figures & tables

BEGIN	INTEGER EX, N, I, J, J0, I1 , J1, I2, J2, K, H, H1, SS, M, DU, Z;
	INTEGER ARRAY U1, I STAR, I BAR, J BAR, SPAN[1:50], C[1:50, 1:50];
	PROCEDURE INPUT; PROCEDURE OUTPUT;
L1:	INPUT (EX, N, J0, M);
	FOR I := 1 STEP 1 UNTIL N DO FOR J := 1 STEP 1 UNTIL N DO INPUT (C[I, J]);
	GO TO L97;
L2:	FOR J:=1 STEP 1 UNTIL N DO

Figure 1: Algorithm 1. Minimum Directed Spanning Tree (Bock, verbatim reproduction)

Symbol	Role in Bock’s procedure
$U_{1}[J]$	Amount subtracted from the costs of links entering $J$ . The reduced cost of $I\to J$ is $C[I,J]-U_{1}[J]$ . The procedure changes $U_{1}[J]$ when the span containing $J$ is adjusted.
$I^{*}[J]$	Initial node of the link currently starred into $J$ . The equality $I^{}[J]=I$ records the provisional link $I\to J$ , while $I^{}[J]=0$ records the absence of a starred link entering $J$ .
$\bar{I}[J],\bar{J}[J]$	Candidate link whose backward trace passed through $J$ . If a subsequent transfer stars a new link into $J$ and displaces its existing star, the stored pair identifies the next candidate to be starred. The pair $(0,0)$ means that no candidate is stored.
$\mathrm{SPAN}[J]$	Label of the span containing $J$ . Equal positive labels identify nodes treated as one contracted span. A negative label temporarily marks a span encountered during a backward trace.

Table 1: Principal arrays maintained by Bock’s procedure.

(DU,I_{1},J_{1})\leftarrow(C[I,J]-U_{1}[J],I,J)

Algorithm 1 Control-flow summary of Bock’s original procedure

Bock’s representation	Readable representation	Role
$U_{1}[J]$	U1[J]	Cumulative adjustment of column $J$
$I^{*}[J]$	parents[J]	Current provisional link entering $J$
$(\bar{I}[J],\bar{J}[J])$	candidate_edges[J]	Candidate reference used during transfer
$\mathrm{SPAN}[J]$	components[J]	Component containing $J$
Negative $\mathrm{SPAN}$ labels	cycle_trace	Components visited by the current trace
$SS$	Not required	Fresh labels are replaced by the active label

Table 2: State correspondence between Bock’s Algol procedure and the readable implementation.

\mathcal{E}_{K}(H)=\{(I,J):J\leq K,\ \mathrm{components}[J]=H,\ \mathrm{components}[I]\neq H,\ C[I,J]<\infty\}

Algorithm 2 Structured reformulation of Bock’s algorithm

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 382 papers

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion
Feb 27, 2026Nate Veldt, Thomas Stanley, Benjamin W. Priest +5Learning-Augmented Algorithms Approximation Algorithms
Texas A&M University · Lawrence Livermore National Laboratory
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
May 13, 2026Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille +2Combinatorial Optimization
DTU Compute, Technical University of Denmark, 2800 Kongens Lyngby, Denmark
Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
Aug 12, 2026Debanjan Dutta, Anish Chakrabarty, Swagatam DasCoT Reasoning
Indian Statistical Institute Kolkata, India · LTCI, Télécom Paris Palaiseau, France

Feb 27, 2026J/K move · Enter open · S save

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Nate Veldt, Thomas Stanley, Benjamin W. Priest, Trevor Steil+4

Texas A&M University · Lawrence Livermore National Laboratory

Learning-Augmented Algorithms Approximation Algorithms

Open paper AskPDF arXiv

We present improved learning-augmented algorithms for finding an approximate minimum spanning tree (MST) for points in an arbitrary metric space. Our work follows a recent framework called metric forest completion (MFC), where the learned input is a forest that must be given additional edges to form a full spanning tree. Veldt et al. (2025) showed that optimally completing the forest takes

Ω(n^2)

time, but designed a 2.62-approximation for MFC with subquadratic complexity. The same method is a

(2γ+ 1)

-approximation for the original MST problem, where

γ\geq 1

is a quality parameter for the initial forest. We introduce a generalized method that interpolates between this prior algorithm and an optimal

Ω(n^2)

-time MFC algorithm. Our approach considers only edges incident to a growing number of strategically chosen ``representative'' points. One corollary of our analysis is to improve the approximation factor of the previous algorithm from 2.62 for MFC and

(2γ+1)

for metric MST to 2 and

2γ

respectively. We prove this is tight for worst-case instances, but we still obtain better instance-specific approximations using our generalized method. We complement our theoretical results with a thorough experimental evaluation.

Abstract

Combinatorial Optimization

Explore similar work

Better Learning-Augmented Spanning Tree Algorithms via Metric Forest Completion

Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm

Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity