Universally Optimal Decremental Tree Minima Benjamin Aram Berendsohn Abstract An algorithm on weighted graphs is called universally optimal if it is optimal for every input graph, in the worst case taken over all weight assignments. Informally, this means the algorithm is competitive even with algorithms that are optimized for only one specific input graph. Universal optimality was recently introduced [Haeupler et al. 2024] as an alternative to the stronger, but often unachievable instance optimality . In this paper, we extend the concept of universal optimality to data structures. In particular, we investigate the following dynamic graph problem: Given a vertex-weighted forest, maintain the minimum-weight vertex of every tree under edge deletions. The problem requires Θ ( log n ) \Theta(\log n) amortized time per operation in general, but only 𝒪 ( 1 ) \mathcal{O}(1) time if the initial forest is a path. We present a data structure that has optimal total running time for every fixed initial forest and every fixed number of operations/queries m m , when taking the worst case over all weight assignments and operation sequences of length m m . This definition of universal optimality is easily adapted to other data structure problems. Our result combines two techniques: (1) A decomposition of the input into paths, to take advantage of the 𝒪 ( 1 ) \mathcal{O}(1) -time path-specific data structure; and (2) splay trees [Sleator and Tarjan 1985], which, informally speaking, are used to optimally handle a certain sorting-related subproblem. We apply our data structure to solve problems related to Cartesian trees , path minimum queries , and bottleneck vertex/edge queries , each with a certain universal optimality guarantee. Our data structure also can be modified to support edge weights instead of vertex weights. Further, it generalizes to support semigroup sum queries instead of minimum queries, in universally optimal time. 1 Introduction In this paper, we study the following dynamic graph problem, which we call Decremental Tree Minima (DTM). We are given a vertex-weighted forest, and need to support the following two operations: \textup{{delete-edge}}(u,v) , which does the obvious; and \textup{{tree-min}}(v) , which returns the minimum vertex in the connected component (i.e., the tree) that contains v . Note that vertex weights cannot be changed and edges cannot be inserted. We assume weights are pairwise distinct and can only be accessed via comparisons. To the author’s knowledge, previous works only considered the fully-dynamic variant of this problem, where edge insertions are also allowed [ GGT91 ] . Standard dynamic forest data structures like link-cut trees [ ST83 , ST85 ] solve the fully-dynamic problem in \mathcal{O}(n\log n) time, when there are n vertices and \Theta(n) operations. This is tight by a reduction from dynamic connectivity [ PD06 ] , even when the forest is a collection of paths at all times. For the Decremental Tree Minima problem (where insertions are not allowed), the same \Omega(n\log n) lower bound holds by a reduction from sorting, so the above solutions are worst-case optimal. What makes the DTM problem interesting is that it is easy when the input tree is a path: Using a standard range minimum query data structure [ BF00 ] , we can achieve \mathcal{O}(m+n) time for m operations and n vertices. This begs the question whether we can beat \Theta(\log n) amortized time per operation on other input forests. In this paper, we give a complete answer to this question: A data structure that has optimal running time on every input forest . To formalize this, we extend the notion of universal optimality , recently defined for (non-dynamic) graph algorithms [ HHR+24a ] , to data structures. We also give several applications of our data structure, which yields universally optimal algorithms . In the following, we first discuss universal optimality in more detail, and then present our results. Universal optimality for algorithms. In classical worst-case complexity, the running time of an algorithm is usually measured in terms of input size only; i.e., for a fixed input size, take the worst case over all inputs of that size. For graph algorithms, sometimes both the number n of vertices and the number m of edges is fixed, and parametrized graph algorithms additionally fix the value of some parameter. In universal optimality, the parameter is the graph itself , and the worst case is only taken over additional data like vertex weights. More precisely, consider a problem where the input is a graph G with an (edge- or vertex-)weight function w , and let A be an algorithm for this problem. Let \mathbb{T}(A,G,w) denote the running time of A on input (G,w) , and let \mathbb{T}(A,G)=\max_{w}\mathbb{T}(A,G,w) , where the maximum is taken over all possible weight functions for G . 1 1 1 We assume here that running times are integers and that the maximum exists. Then A is universally optimal if, for every graph G , and every other algorithm A^{\prime} , we have \mathbb{T}(A,G)\leq c\cdot\mathbb{T}(A^{\prime},G) for some globally fixed constant c . In particular, universal optimality means that A is competitive with algorithms that are specifically engineered for a single graph. In contrast, instance optimality means that we have \mathbb{T}(A,G,w)\leq c\cdot\mathbb{T}(A^{\prime},G,w) for every input (G,w) and some globally fixed constant c . Instance optimality can be seen as the ‘‘ultimate’’ optimality guarantee; 2 2 2 If we ignore constant factors. unfortunately, it is often unachievable. This is in particular true for problems that contain sorting as a special case. Indeed, every sequence can be sorted in linear time by some algorithm, but for every sorting algorithm there exists a sequence that requires \Omega(n\log n) time. We now discuss some problems where universally optimal algorithms are known. First, in the distance ordering problem , we are given a directed edge-weighted graph G and a starting vertex s , and need to order the vertices by distance from s . Haeupler, Hladík, Rozhon, Tarjan, and Tětek [ HHR+24a ] showed that Dijkstra’s algorithm, equipped with a special priority queue, solves this problem in universally optimal running time. A related problem is partial order sorting . Here, we are given a set of elements and the Hasse diagram of a partial order on these elements. We need to sort the elements using comparisons, under the promise that the sorted order is a linear extension of the given partial order. For universal optimality, the Hasse diagram corresponds to the graph G , and the underlying order takes the role of the weight assignment. Two different universally optimal algorithms for this problem have been found recently [ HHI+25 , vdHRR25b ] . Finally, there is an algorithm for convex hull [ KS86 , ABC17 ] that has been called universally optimal [ vdHRR25a ] . This is obviously not a graph problem; however, the concept of universal optimality can be generalized to arbitrary input types, as long as we can identify a primary input part (replacing the graph), and a secondary input part (replacing the weight assignment). For convex hull, the primary input part is taken as the set of input points, and the secondary input part is the order in which they are given. A universally optimal algorithm by this definition is instance-optimal among all algorithms that behave the same irrespective of input order; accordingly, the term used originally was instance optimality in the order-oblivious model [ ABC17 ] . Note that all three problems have worst-case lower bounds of \Omega(n\log n) (where n denotes the number of vertices in the graph, the number of elements to sort, or the number of points). These lower bounds are achieved if the input is a star, a partial order consisting of a single antichain, or a set of points in convex position, respectively. In all three cases, worst-case optimal algorithms have been known for a long time. On the other hand, the following easy cases can be identified: For the distance-ordering problem, if G is a directed path starting at s , then the problem can be solved in linear time, regardless of the edge weights. Similarly, if the given partial order is a chain, then no comparisons are necessary to determine the sorted order. Finally, it is known that a convex hull can be computed in linear time if it only contains a constant number of points, regardless of the input order [ KS86 , Cha96 ] . Thus, worst-case running times range between \Theta(n\log n) and \Theta(n) depending on the primary input part (i.e., the graph, partial order, or point set). It is reasonable to ask for some interpolation between these extremes. A well-known result in that direction are the output-sensitive convex hull algorithms of Kirkpatrick–Seidel [ KS86 ] and Chan [ Cha96 ] , which take \mathcal{O}(n\log h) time, where h is the number of points on the convex hull. Universally optimal algorithms can be seen as a best possible such interpolation. Universal optimality for data structures. Recall the Decremental Tree Minima (DTM) problem defined above. We start with a vertex-weighted forest, we can delete an edge with \textup{{delete-edge}}(u,v) , and we can find the minimum-weight vertex in the tree containing a given vertex v with \textup{{tree-min}}(v) . In the following, we call vertex weights priorities , to distinguish them from numerical weights. We assume priorities in the input forest are pairwise distinct and can only be accessed via comparisons. When the input forest G has n vertices, then \Theta(n) DTM operations can be performed in \mathcal{O}(n\log n) time [ GGT91 ] . This is tight if G is a star where the central vertex has priority \infty . Indeed, in this case a DTM data structure can sort the leaf priorities with alternating tree-min queries and edge deletions, which requires \Omega(n\log n) . On the other hand, if G is path, then DTM can be solved with \mathcal{O}(n) time preprocessing and \mathcal{O}(1) time per operation (details are given in section 2.3 ). We are thus in a similar situation as for the aforementioned algorithmic problems: The worst-case running time for \Theta(n) operations a fixed graph can be \Theta(n\log n) or \Theta(n) , depending on the graph (in fact, it can be anything in between). However, it is not immediately obvious how to define universal optimality for data structures. In particular, the restriction to \Theta(n) operations may not adequately capture the complexity of the problem. On the other hand, if the number of operation is arbitrary, the worst-case total running time for any fixed graph is unbounded. We hence use the following definition, which can be easily adapted to a wide range of dynamic graph problems (see below). We model a problem instance as a tuple (G,p,\sigma) , where G is the initial tree, p is the priority assignment and \sigma is the sequence of operations. The primary input part for universal optimality is (G,|\sigma|) , i.e., the graph and the number of operations. Note that \sigma is revealed one-by-one, and not even |\sigma| is known at the start. More precisely, if D is a data structure for the DTM problem, G is a graph, and m\in\mathbb{N} , then \mathbb{T}(D,G,m) denotes the total time D requires for an input (G,p,\sigma) , in the worst case over all possible priority assignments p and all valid operation sequences \sigma with |\sigma|=m . We call D universally optimal when, for each G , each m , and each other data structure D^{\prime} , we have \mathbb{T}(D,G,m)\leq c\cdot\mathbb{T}(D^{\prime},G,m) for some globally fixed constant c . Our main result is: Theorem 1.1 . There is a universally optimal data structure for the Decremental Tree Minima problem. Alternative definitions. Our definition is not the only reasonable interpretation of universal optimality. For the DTM problem specifically, one could require tree-min to run in constant time, and measure the total time for preprocessing plus the at most n edge deletions. This is in line with the idea of “maintaining” tree minima. However, our definition is stronger and more directly generalizes to other decremental graph problems. Another definition may count each operation separately. For example, for DTM, we may consider pairs m_{1},m_{2}\in\mathbb{N} instead of a single value m , and take the worst case over all sequences of m_{1} edge deletions and m_{2} tree-min queries. Our data structure does not achieve this definition of universal optimality, but perhaps it could be adapted with some mechanism that postpones edge deletions until required. For an even stronger definition, we could fix the whole sequence of operations, taking the worst case over only the input weights. An algorithm satisfying this definition would have to match the running time of an optimal offline algorithm, which is impossible for DTM, as is explained at the end of this section. However, for a different problem where operations have weight parameters, the following definition could be interesting: Fix the operations and their vertex parameters, but not the weight parameters. 3 3 3 This definition was suggested by an anonymous reviewer. For incremental graph data structures, we can easily adapt our definition by taking the final graph instead of the initial graph. For fully-dynamic problems, one could take the graph containing all edges ever present in the graph. 4 4 4 This may seem crude, but there are applications where this graph is meaningful. For example, a maximum flow algorithm of Goldberg and Tarjan [ GT88 ] uses a dynamic forest data structure, and all edges ever inserted into the dynamic forest are contained in the input graph. Cartesian trees on graphs. Figure 1: A graph (right), an elimination tree on that graph (center), and the eight priority-orderings of vertices inducing that elimination tree (right). Our second result is a universally optimal algorithm for computing a certain graph decomposition, using our Decremental Tree Minima data structure. We start with some definitions. An elimination tree on a connected graph G is a rooted tree T with V(T)=V(G) , constructed as follows (see fig. 1 , left/center): First, pick an arbitrary vertex r\in V(G) as the root of T . Then, recursively construct elimination trees on each component of G-r , and add them as child subtrees to r . Note that if G is a path, then T is a binary tree, and fixing a direction on the path induces the usual left and right children. Elimination trees have been studied in the context of matrix factorization, vertex search, and structural graph theory; see section 1.3 for more details. A priority assignment p uniquely determines an elimination tree T on G as follows (see fig. 1 ): Whenever a subtree root is picked, pick the currently available vertex with minimum priority. Alternatively, T is the unique elimination tree on G such that for each ancestor-descendant pair u,v , we have p(u)
H_{S}(T).
This implies
H_{S}(T) |\widetilde{T}_{u}|
. Using
lemma
5.2
and the fact that
S
and
\widetilde{S}
are both closed under taking descendants, we have:
\displaystyle H_{\widetilde{S}}(\widetilde{T})=\sum_{u\in\widetilde{S}}\log\frac{|\widetilde{S}|}{|\widetilde{T}_{u}|}<2\sum_{u\in S}\log\frac{|\widetilde{S}|}{|\widetilde{T}_{u}|}\leq 2\sum_{u\in S}\log\frac{2|S|}{2|T_{u}|-1}
\displaystyle\leq 2\sum_{u\in S}\log\frac{2|S|}{|T_{u}|}\leq 2|S|+2\sum_{u\in S}\log\frac{|S|}{|T_{u}|}\leq 2|S|+2H_{S}(T).
∎
8.1
Decremental tree minima with edge weights
Consider the following variant of
Decremental Tree Minima
, which we call
Edge Decremental Tree Minima
(EDTM). Given is an initial rooted tree
T
and a priority function
p
on the
edge set
E(T)
.
\textup{{tree-min}}(v)
now reports the minimum-priority edge in the tree containing
v
, or
\infty
if that tree contains no edges.
cut
works as usual.
We can now use our DTM data structure to solve the EDTM problem as follows. Consider an EDTM input
(T,p)
. First, build the corresponding DTM input
(\widetilde{T},\widetilde{p})
, and initialize a DTM data structure on it. Whenever an edge
e
is deleted in
T
, we delete the two edges adjacent to the corresponding vertex
v_{e}
in
T
. More formally, for a given
\textup{{cut}}(u)
in
T
, we perform
\textup{{cut}}(u)
and
\textup{{cut}}(v_{u})
in
\widetilde{T}
.
tree-min
queries can be answered directly.
It is easy to see that this is a correct EDTM data structure. From
theorem
5.6
, we obtain:
Lemma 8.2
.
Let
T
be a rooted tree with
n
nodes, let
p
be a priority function for
E(T)
, and let
\sigma
be a sequence of
m
EDTM operation applied to
(T,p)
.
Then, our data structure takes
\mathcal{O}(H_{2m}(\widetilde{T})+m+n)
total time for
(T,p,\sigma)
.
We now prove a corresponding lower bound.
We show that the
Top-
k
Tree Sorting
problem on
T
can be solved with an EDTM data structure on
T
, using
2k
operations. Given is a tree
T
and a
T
-monotone vertex priority function
p
. First, compute an edge priority function
p^{\prime}
, where
p^{\prime}(e)=p(u)
for each edge
e
that connects a child
u
with its parent. Now build an EDTM data structure on
(T,p^{\prime})
. Let
r
be the root of
r
. Call
\textup{{find-min}}(r)
, which reports the minimum-priority edge
e
. Output
p^{\prime}(e)
, delete
e
, and repeat until there are no more edges. At the end, output the root priority
p(r)
.
Observe that whenever this algorithm finds an edge
e
, one of its endpoints must currently be a leaf (since
p
is
T
-monotone). Thus, all remaining edges stay in the same component as the initial root
r
.
The output of the algorithm is clearly the priorities of
(T,p)
in sorted order. From our lower bound for
Top-
k
Tree Sorting
(
section
5.2
), we obtain:
Lemma 8.3
.
For every EDTM data structure
X
, every tree
T
, and every positive integer
k\leq|V(T)|-1
, there exists a sequence
\sigma
of
2k
operations such that
X
takes total time
\log|\mathcal{L}_{k}(T)|\geq\Omega(H_{k}(T)-k)
for
(T,p,\sigma)
.
We now show universal optimality. Let
T
be a rooted tree, and let
m\in\mathbb{N}_{+}
be the number of operations. By
lemma
8.2
, the running time of our algorithm for any edge priority function
p
and any operation sequence of length
m
is
\mathcal{O}(H_{2m}(\widetilde{T})+m+n)
, which is
\mathcal{O}(H_{m}(T)+m+n)
by
lemmas
5.5
and
8.1
. Considering the trivial lower bound
\Omega(m+n)
, this matches
lemma
8.3
.
Theorem 8.4
.
Our EDTM data structure is universally optimal.
8.2
Cartesian edge-partition trees
Recall the definition of
Cartesian edge-partition trees
(Cartesian EPTs) from the introduction. A Cartesian EPT on a connected graph
G
with edge priority function
p
is a rooted binary tree
T
with
V(T)=E(G)\cup V(G)
, where the edges of
G
correspond to inner nodes of
T
, and vertices of
G
correspond to leaves of
T
. If
G
consists of a single vertex, then
T
also consists of that vertex. Otherwise, the root of the EPT is the minimum-priority edge of
(G,p)
, and the the up to two child subtrees are recursively constructed on the up to two components of
G-e
.
We also write
\mathcal{C}^{\mathrm{E}}(G,p)=T
.
Let
\mathcal{E}^{\mathrm{E}}(G)
denote the set of possible Cartesian EPTs on
G
.
It is known that Cartesian EPTs on
trees
can be constructed in
\mathcal{O}(n\log n)
time
[
Cha87
]
, or in
\mathcal{O}(n\log\ell)
time if
G
has
\ell
leaves
[
DM13
]
. In this section, we give a universally optimal algorithm for arbitrary graphs.
Fix some connected graph
G
and edge priority function
p
on
G
. Recall that
\widetilde{p}
assigns multiple vertices the same priority
\infty
. Since this does not play well with our definition of Cartesian trees, we introduce the following tie-breaking.
Fix an arbitrary ordering
\pi
on
V(G)
, and redefine
\widetilde{p}(v)=\infty_{v}
; where
\infty_{v}
is a priority that is larger than all edge priorities, and
\infty_{v}<\infty_{u}
if
v
precedes
u
in
\pi
. We can now prove the following.
Lemma 8.5
.
Let
G
be a graph with edge priority function
p
. Then
\mathcal{C}^{\mathrm{E}}(G,p)
is isomorphic to
\mathcal{C}(\widetilde{G},\widetilde{p})
under the mapping
v\rightarrow v
for
v\in V(G)
and
e\rightarrow v_{e}
for
e\in E(G)
.
Proof.
If
G
contains only one vertex, then both
\mathcal{C}^{\mathrm{E}}(G,p)
and
\mathcal{C}(\widetilde{G},\widetilde{p})
consist of that vertex only.
Otherwise, let
e
be the minimum-priority edge of
G
, and recall that
v_{e}
must be the minimum-priority vertex of
\widetilde{G}
.
Suppose first that
G-e
is disconnected, so it has two components
H_{1}
,
H_{2}
.
Then
\widetilde{G}-v_{e}
also has two components
H^{\prime}_{1}
,
H^{\prime}_{2}
. It is easy to see that
H^{\prime}_{1}=\widetilde{H}_{1}
and
H^{\prime}_{2}=\widetilde{H}_{2}
(for some assignment of the names
H_{1},H_{2}
).
By induction,
\mathcal{C}(H_{i},p)=\mathcal{C}(\widetilde{H}_{i},\widetilde{p})
for
i\in\{1,2\}
. Since
\mathcal{C}^{\mathrm{E}}(G,p)
consists of the root
e
with children
\mathcal{C}(H_{1},p)
,
\mathcal{C}(H_{2},p)
, and
\mathcal{C}(\widetilde{G},\widetilde{p})
consists of the root
v_{e}
with children
\mathcal{C}(\widetilde{H}_{1},\widetilde{p})
,
\mathcal{C}(\widetilde{H}_{2},\widetilde{p})
, our claim follows.
Suppose now
H\coloneq G-e
is connected. Clearly,
\widetilde{G}-v_{e}=\widetilde{H}
. Our claim follows similarly.
∎
Observe that
lemma
8.5
in particular implies that the choice of
\pi
for tie-breaking does not affect the Cartesian tree
\mathcal{C}(\widetilde{G},\widetilde{p})
.
We now give the universally optimal algorithm. Given is a graph
G
with
n
vertices and
m
edges, and an edge priority function
p
. Start by computing
(\widetilde{G},\widetilde{p})
in
\mathcal{O}(m+n)
time. Then, compute
\mathcal{C}(\widetilde{G},\widetilde{p})
with
theorem
1.2
. Using
lemma
8.5
, we can map the result to the correct EPT
\mathcal{C}^{\mathrm{E}}(G,p)
.
The total running time is
\mathcal{O}(m+n+\log|\mathcal{E}(\widetilde{G})|)
. Since
lemma
8.5
defines a bijection between
\mathcal{E}^{\mathrm{E}}(G)
and
\mathcal{E}(\widetilde{G})
, we have
|\mathcal{E}^{\mathrm{E}}(G)|=|\mathcal{E}(\widetilde{G})|
.
Theorem 8.6
.
Given a connected graph
G
with edge priority function
p
, we can compute
\mathcal{C}^{\mathrm{E}}(G,p)
in time
\mathcal{O}(|E(G)|+\log|\mathcal{E}^{\mathrm{E}}(G)|
.
By the information-theoretic lower bound and the trivial
\Omega(|E(G)|)
lower bound,
theorem
8.6
is universally optimal.
8.3
Edge-weighted path-minimum and bottleneck queries.
It is well known that Cartesian EPTs can be used to answer edge-weighted variants of
path-min
and
bottleneck
queries
[
Cha87
,
DLW14
]
, much like Cartesian trees can be used for the vertex-weighted variants. For
bottleneck
queries on general graphs, again a spanning tree reduction is used
[
Hu61
,
SYZ11
,
DLW14
]
. Using the same techniques as above, we obtain a universally optimal algorithm to preprocess a graph
G
with edge priorities such that
bottleneck
queries can be answered without further comparisons. We omit the details.
Acknowledgments.
The author would like to thank Tomasz Kociumaka and Marek Sokołowski for useful suggestions.
Appendix A
The potential of complete binary trees
Let
T
be a binary tree and
w\colon V(T)\rightarrow\mathbb{N}_{+}
be a node weight function. Recall that the
rank
of a node
v\in V(T)
is
\log w(T_{v})
and the
potential
\Phi(T)
of
T
is defined as the sum of all node ranks. In the following, we explicitly write
\Phi(T,w)
to denote the potential of
T
w.r.t. the weight function
w
.
The
complete binary tree
C_{n}
on
n=2^{k}-1
nodes is the tree where all leaves are at depth
k
. If
n+1
is not a power of two, then
C_{n}
is constructed from
C_{n^{\prime}}
with
n^{\prime}=2^{\lceil\log(n+1)\rceil}-1
by progressively removing leaves from right to left until the number of nodes is
n
.
In this section, we show:
Theorem A.1
.
Let
T=B_{n}
and let
w\colon V(T)\rightarrow\mathbb{N}_{+}
. Let
W=w(T)
be the sum of weights in
T
. Then
\Phi(T,w)\in\mathcal{O}(W)
.
The following lemma is central:
Lemma A.2
.
Let
T=B_{n}
, let
v\in V(T)
, and let
w,w^{\prime}\colon V(T)\rightarrow\mathbb{N}_{+}
be weight functions such that
w^{\prime}(u)=w(u)
for all
u\neq v
and
w^{\prime}(v)>w(v)
. Then
\Phi(T,w^{\prime})\leq\Phi(T,w)+3(w^{\prime}(v)-w(v))
.
Proof.
Let
x=w^{\prime}(v)-w(v)
. Let
a_{0}=v
and let
a_{1},a_{2},\dots,a_{k}
be the proper ancestors of
v
in
T
, ordered from
v
to the root. The weight increase of
v
only affects itself and its ancestors, so we have:
\Phi(T,w^{\prime})-\Phi(T,w)=\sum_{i=0}^{k}\log w^{\prime}(T_{a_{i}})-\log w(T_{a_{i}})=\sum_{i=0}^{k}\log\frac{w(T_{a_{i}})+x}{w(T_{a_{i}})}.
Observe that
w(T_{a_{i}})\geq 2^{i+1}-1\geq 2^{i}
. Using the fact that
\tfrac{a+x}{a}\leq\tfrac{b+x}{b}
for all
a\geq b
, we get
\displaystyle\Phi(T,w^{\prime})-\Phi(T,w)
\displaystyle\leq\sum_{i=0}^{k}\log\frac{2^{i}+x}{2^{i}}\leq\sum_{i=0}^{k}\log\left(1+\frac{x}{2^{i}}\right)\leq\sum_{i=0}^{k}\log e^{x/2^{i}}
\displaystyle\leq 2x\log e\leq 3x.
∎
Proof of
theorem
A.1
.
Suppose that
n=2^{k}-1
; the other cases follow by padding with weight-one leaves.
We start with the case that
w(v)=1
for all
v\in V(T)
.
Then
\Phi(T,w)=\sum_{i=0}^{k-1}2^{i}\log\tfrac{n}{2^{i}}\in\mathcal{O}(n),
as desired.
We can now transform
w
into an arbitrary weight function
w^{\prime}
by repeatedly increasing the weight of some node by some amount
x
. Every time we do this, the potential increases by at most
3x
by
lemma
A.2
. Thus, the total potential increase is at most
3(w^{\prime}(T)-w(T))=3(w^{\prime}(T)-n)
, for a total potential of
\mathcal{O}(w^{\prime}(T)+n)=\mathcal{O}(w^{\prime}(T))
.
∎
Appendix B
The Dijkstra-Jarník-Prim algorithm with working-set heaps
In this section, we give a technical description of how to compute a minimum spanning tree in the time required by
theorem
1.2
. The main theorem follows.
See
6.10
We first specify the priority queue data structure used in the Dijkstra-Jarník-Prim algorithm. We use the classical operation names, where our
priorities
are called
keys
.
Definition B.1
.
A
priority queue
maintains a set of elements
S
and an injective priority assignment
p\colon S\rightarrow\mathfrak{P}
, under the following operations:
•
\texttt{delete-min}()\rightarrow x
removes and returns the minimum-priority element
x
in
S
.
•
\texttt{insert}(x,q)
inserts an element
x
and sets
p(x)\leftarrow q
.
•
\texttt{decrease-key}(x,y)
sets
p(x)\leftarrow q
, assuming
x\in S
and
q
is smaller than the previous value for
p(x)
.
•
\texttt{get-key}(x)\rightarrow q
returns
q=p(x)
.
Algorithm 1
The Dijkstra-Jarník-Prim MST algorithm. The input is an edge-weighted graph
(G,w)
and a starting vertex
s\in V(G)
procedure
DJP
(
G,w,s
)
Initialize empty priority queue
Q
Q.\texttt{insert}(s,?)
\triangleright
Priority is arbitrary
Initialize map
R\colon V(G)\rightarrow V(G)\cup\{\bot\}
with
\bot
\triangleright
Predecessors
Initialize map
p\colon V(G)\rightarrow\mathfrak{P}
with
\infty
\triangleright
Current priorities
Initialize set
U\leftarrow\emptyset
\triangleright
Visited vertices
while
Q
is not empty
do
u\leftarrow Q.\texttt{delete-min}()
U\leftarrow U\cup\{u\}
for each
neighbor
v
of
u
with
v\notin U
do
if
v\notin Q
then
Q.\texttt{insert}(v,w(u,v))
.
R[v]=u
else
if
w(u,v)