Department of Computer Science, Utah State University, Logan, UT 84322,
<EMAIL_ADDRESS>of Computer Science, Utah State University,
Logan, UT 84322<EMAIL_ADDRESS>Haitao Wang and Yiming Zhao
[100]Theory of computation $\rightarrow$ Design and analysis of algorithms
This research was supported in part by NSF under Grant CCF-2005323.

###### Acknowledgements.

John Q. Open and Joan R. Access 2 42nd Conference on Very Important Topics
(CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United
Kingdom 42 23

# Algorithms for Diameters of Unicycle Graphs and Diameter-Optimally
Augmenting Trees111A preliminary version of this paper appears in the
Proceedings of the 15th International Conference and Workshops on Algorithms
and Computation (WALCOM 2021).

Haitao Wang  Yiming Zhao222Corresponding author.

###### Abstract

We consider the problem of computing the diameter of a unicycle graph (i.e., a
graph with a unique cycle). We present an $O(n)$ time algorithm for the
problem, where $n$ is the number of vertices of the graph. This improves the
previous best $O(n\log n)$ time solution [Oh and Ahn, ISAAC 2016]. Using this
algorithm as a subroutine, we solve the problem of adding a shortcut to a tree
so that the diameter of the new graph (which is a unicycle graph) is
minimized; our algorithm takes $O(n^{2}\log n)$ time and $O(n)$ space. The
previous best algorithms solve the problem in $O(n^{2}\log^{3}n)$ time and
$O(n)$ space [Oh and Ahn, ISAAC 2016], or in $O(n^{2})$ time and $O(n^{2})$
space [Bilò, ISAAC 2018].

###### keywords:

diameter, unicycle graphs, augmenting trees, shortcuts

###### category:

##  1 Introduction

Let $G$ be a graph of $n$ vertices such that each edge has a positive length.
A shortest path connecting two vertices $s$ and $t$ in $G$ is a path of
minimum total edge length; the length of the shortest path is also called the
distance between $s$ and $t$ in $G$. The diameter of $G$ is the maximum
distance between all pairs of vertices of $G$. $G$ is a unicycle graph if it
has only one cycle, i.e., $G$ is a tree plus an additional edge.

We consider the problem of computing the diameter of a unicycle graph $G$.
Previously, Oh and Ahn [20] solved the problem in $O(n\log n)$ time, where $n$
is the number of vertices of $G$. We present an improved algorithm of $O(n)$
time. Using our new algorithm, we also solve the _diameter-optimally
augmenting tree_ (DOAT for short) problem, defined as follows.

Let $T$ be a tree of $n$ vertices such that each edge has a positive length.
We want to add a new edge (called shortcut) to $T$ such that the new graph
(which is a unicycle graph) has the minimum diameter. We assume that there is
an oracle that returns the length of any given shortcut in $O(1)$ time.
Previously, Oh and Ahn [20] solved the problem in $O(n^{2}\log^{3}n)$ time and
$O(n)$ space, and Bilò [3] reduced the time to $O(n^{2})$ but the space
increases to $O(n^{2})$. As observed by Oh and Ahn [20], the problem has an
$\Omega(n^{2})$ lower bound on the running time as all $\Theta(n^{2})$
possible shortcuts have to be checked in order to find an optimal shortcut.
Hence, Bilò’s algorithm is time-optimal. In this paper, we propose an
algorithm with a better time and space trade-off, and our algorithm uses
$O(n^{2}\log n)$ time and $O(n)$ space.

###  1.1 Related work

The diameter is an important measure of graphs and computing it is one of the
most fundamental algorithmic graph problems. For general graphs or even planar
graphs, the only known way to compute the diameter is to first solve the all-
pair-shortest-path problem (i.e., compute the distances of all pairs of
vertices of the graph), which inherently takes $\Omega(n^{2})$ time, e.g.,
[11, 25]. Better algorithms exist for special graphs. For example, the
diameter of a tree can be computed in linear time, e.g., by first computing
its center [19]. If $G$ is an outerplanar graph and all edges have the same
length, its diameter can be computed in linear time [10]. The diameter of
interval graphs (with equal edge lengths) can also be computed in linear time
[21]. Our result adds the unicycle graph (with different edge lengths) to the
linear-time solvable graph category.

The DOAT problem and many of its variations enjoy an increasing interest in
the research community. If the tree $T$ is embedded in a metric space (so that
the triangle inequality holds for edge lengths), Große et al. [15] first
solved the problem in $O(n^{2}\log n)$ time. Bilò [3] later gave an $O(n\log
n)$ time and $O(n)$ space algorithm, and another $(1+\epsilon)$-approximation
algorithm of $O(n+\frac{1}{\epsilon}\log\frac{1}{\epsilon})$ time and
$O(n+\frac{1}{\epsilon})$ space for any $\epsilon>0$. A special case where $T$
is a path embedded in a metric space was first studied by Große et al. [14],
who gave an $O(n\log^{3}n)$ time algorithm, and the algorithm was later
improved to $O(n\log n)$ time by Wang [23]. Hence, Bilò’s work [3] generalizes
Wang’s result [23] to trees.

A variant of the DOAT problem which aims to minimize the _continuous diameter_
, i.e., the diameter of $T$ is measured with respect to all the points of the
tree (including the points in the interior of the edges), has also been
studied. If $T$ is a path embedded in the Euclidean plane, De Carufel et al.
[5] solved the problem in $O(n)$ time. If $T$ is a tree embedded in a metric
space, De Carufel et al. [6] gave an $O(n\log n)$ time algorithm. If $T$ is a
general tree, Oh and Ahn [20] solved the problem in $O(n^{2}\log^{3}n)$ time
and $O(n)$ space.

The DOAT problem is to minimize the diameter. The problem of minimizing the
radius was also considered. For the case where $T$ is a path embedded in a
metric space, Johnson and Wang [17] presented a linear time algorithm which
adds a shortcut to $T$ so that the radius of the resulting graph is minimized.
The radius considered in [17] is defined with respect to all points of $T$,
not just the vertices. Wang and Zhao [24] studied the same problem with radius
defined with respect to only the vertices, and they gave a linear time
algorithm.

The more general problem in which one wants to add $k$ shortcuts to a graph to
minimize the diameter is NP-hard [22] and some variations are even W[2]-hard
[12, 13]. Approximation algorithms have been proposed [4, 7, 9, 12, 18]. The
upper and lower bounds on the values of diameters of certain augmented graphs
were also studied, e.g., [1, 8, 16]. Bae et al. [2] considered the problem of
adding $k$ shortcuts to a circle in the plane to minimize the diameter of the
resulting graph.

###  1.2 Our approach

To compute the diameter of a unicycle graph $G$, Oh and Ahn [20] reduces the
problem to a geometric problem and then uses a one-dimensional range tree to
solve the problem. We take a completely different approach. Let $C$ be the
unique cycle of $G$. We define certain “domination” relations on the vertices
of $C$ so that if a vertex $v$ is dominated by another vertex then $v$ is not
important to the diameter. We then present a pruning algorithm to find all
undominated vertices (and thus those dominated vertices are “pruned”); it
turns out that finding the diameter among the undominated vertices is fairly
easy. In this way, we compute the diameter of $G$ in linear time.

For the DOAT problem on a tree $T$, Oh and Ahn [20] considered all possible
shortcuts of $T$ by following an Euler tour of $T$; they used the
aforementioned one-dimensional range tree to update the diameter for the next
shortcut. Bilò’s method [3] is to transform the problem to adding a shortcut
to a path whose edge lengths satisfy a property similar in spirit to the
triangle inequality (called graph-triangle inequality) and then the problem on
$P$ can be solved by applying the $O(n\log n)$ time algorithm for trees in
metric space [3]. Unfortunately, the problem transformation algorithm relies
on using $O(n^{2})$ space to store the lengths of all possible $\Theta(n^{2})$
shortcuts of $T$. The algorithm has to consider all these $\Theta(n^{2})$
shortcut lengths in a global manner and thus it inherently uses
$\Omega(n^{2})$ space. Note that Bilò’s method [3] does not need an algorithm
for computing the diameter of a unicycle graph.

We propose a novel approach. We first compute a diametral path $P$ of $T$.
Then we reduce the DOAT problem on $T$ to finding a shortcut for $P$. To this
end, we consider vertices of $P$ individually. For each vertex $v_{i}$ of $P$,
we want to find an optimal shortcut with the restriction that it must connect
$v_{i}$, dubbed a $v_{i}$-shortcut. For this, we define a “domination”
relation on all $v_{i}$-shortcuts and we show that those shortcuts dominated
by others are not important. We then design a pruning algorithm to find all
shortcuts that are not dominated by others; most importantly, these
undominated shortcuts have certain monotonicity properties that allow us to
perform binary search to find an optimal $v_{i}$-shortcut by using our
diameter algorithm for unicycle graphs as a subroutine. With these effort, we
find an optimal $v_{i}$-shortcut in $O(n\log n)$ time and $O(n)$ space. The
space can be reused for computing optimal $v_{i}$-shortcuts of other vertices
of $P$. In this way, the total time of the algorithm is $O(n^{2}\log n)$ and
the space is $O(n)$.

#### Outline.

In the following, we present our algorithm for computing the diameter of a
unicycle graph in Section 2. Section 3 is concerned with the DOAT problem.

##  2 Computing the Diameter of Unicycle Graphs

In this section, we present our linear time algorithm for computing the
diameter of unicycle graphs.

For a subgraph $G^{\prime}$ of a graph $G$ and two vertices $u$ and $v$ from
$G^{\prime}$, we use $\pi_{G^{\prime}}(u,v)$ to denote a shortest path from
$u$ to $v$ in $G^{\prime}$ and use $d_{G^{\prime}}(u,v)$ to denote the length
of the path. We use $\Delta(G)$ to denote the diameter of $G$. A pair of
vertices $(u,v)$ is called a diametral pair and $\pi_{G}(u,v)$ is called a
diametral path if $d_{G}(u,v)=\Delta(G)$.

In the following, let $G$ be a unicycle graph of $n$ vertices. Our goal is to
compute the diameter $\Delta(G)$ (along with a diametral pair). Let $C$ denote
the unique cycle of $G$.

###  2.1 Observations

Removing all edges of $C$ (while keeping its vertices) from $G$ results in
several connected components of $G$. Each component is a tree that contains a
vertex $v$ of $C$; we use $T(v)$ to denote the tree. Let
$v_{1},v_{2},\ldots,v_{m}$ be the vertices ordered clockwise on $C$. Let
$\mathcal{T}(G)=\\{T(v_{i})\ |\ 1\leq i\leq m\\}$. Note that the sets of
vertices of all trees of $\mathcal{T}(G)$ form a partition of the vertex set
of $G$.

Consider a diametral pair $(u^{*},v^{*})$ of $G$. There are two cases: (1)
both $u^{*}$ and $v^{*}$ are in the same tree of $\mathcal{T}(G)$; (2) $u^{*}$
and $v^{*}$ are in two different trees of $\mathcal{T}(G)$. To handle the
first case, we compute the diameter of each tree of $\mathcal{T}(G)$, which
can be done in linear time. Computing the diameters for all trees takes $O(n)$
time. The longest diameter of these trees is the diameter of $G$. In the
following, we focus on the second case.

Suppose $T(v_{i})$ contains $u^{*}$ and $T(v_{j})$ contains $v^{*}$ for $i\neq
j$. Observe that the diametral path $\pi_{G}(u^{*},v^{*})$ is the
concatenation of the following three paths: $\pi_{T(v_{i})}(u^{*},v_{i})$,
$\pi_{C}(v_{i},v_{j})$, and $\pi_{T(v_{j})}(v_{j},v^{*})$. Further, $u^{*}$ is
the farthest vertex in $T(v_{i})$ from $v_{i}$; the same holds for $v^{*}$ and
$T(v_{j})$. On the basis of these observations, we introduce some concepts as
follows.

For each vertex $v_{i}\in C$, we define a weight $w(v_{i})$ as the length of
the path from $v_{i}$ to its farthest vertex in $T(v_{i})$. The weights for
all vertices on $C$ can be computed in total $O(n)$ time. With this definition
in hand, we have $\Delta(G)=\max_{1\leq i<j\leq
m}(w(v_{i})+d_{C}(v_{i},v_{j})+w(v_{j}))$. We say that $(v_{i},v_{j})$ is a
vertex-weighted diametral pair of $C$ if $T(v_{i})$ contains $u^{*}$ and
$T(v_{j})$ contains $v^{*}$ for a diametral pair $(u^{*},v^{*})$ of $G$. To
compute $\Delta(G)$, it suffices to find a vertex-weighted diameter pair of
$C$.

We introduce a domination relation for vertices on $C$.

######  Definition 2.1.

For two vertices $v_{i},v_{j}\in C$, we say that $v_{i}$ dominates $v_{j}$ if
$w(v_{i})>w(v_{j})+d_{C}(v_{i},v_{j})$.

The following lemma shows that if a vertex is dominated by another vertex,
then it is not “important”.

######  Lemma 2.2.

For two vertices $v_{i}$ and $v_{j}$ of $C$, if $v_{i}$ dominates $v_{j}$,
then $v_{j}$ cannot be in any vertex-weighted diametral pair of $C$ unless
$(v_{i},v_{j})$ is such a pair.

######  Proof 2.3.

We assume that $(v_{i},v_{j})$ is not a vertex-weighted diametral pair. Assume
to the contrary that $(v_{k},v_{j})$ is a vertex-weighted diametral pair of
$C$. Then, $k\neq i$ and $\Delta(G)=w(v_{k})+d_{C}(v_{k},v_{j})+w(v_{j})$.
Note that $d_{C}(v_{k},v_{j})\leq d_{C}(v_{k},v_{i})+d_{C}(v_{i},v_{j})$
holds. Since $v_{i}$ dominates $v_{j}$, we have
$w(v_{i})>w(v_{j})+d_{C}(v_{i},v_{j})$. Consequently, we can derive

$\displaystyle\Delta(G)$ $\displaystyle=w(v_{k})+d_{C}(v_{k},v_{j})+w(v_{j})$
$\displaystyle\leq w(v_{k})+d_{C}(v_{k},v_{i})+d_{C}(v_{i},v_{j})+w(v_{j})$
$\displaystyle<w(v_{k})+d_{C}(v_{k},v_{i})+w(v_{i}).$

But this contradicts with the definition of $\Delta(G)$. The lemma thus
follows.

###  2.2 A pruning algorithm

In the sequel, we describe a linear time pruning algorithm to find all
vertices of $C$ that are dominated by other vertices (and thus those dominated
vertices are “pruned”). As will be seen later, the diameter can be easily
found after these vertices are pruned.

Figure 1: Illustrating the definitions of $C_{ccw}(v_{i})$ (the disks except
$v_{i}$) and $C_{cw}(v_{i})$ (the squares). We assume that $p$ is a point on
$C$ that together with $v_{i}$ partitions $C$ into two half-cycles of equal
length.

Let $|C|$ denote the sum of the lengths of all edges of $C$. For any vertex
$v_{i}$ of $C$, define $C_{ccw}(v_{i})$ as the set of vertices $v_{j}$ of $C$
such that the path from $v_{i}$ to $v_{j}$ counterclockwise along $C$ has
length at most $|C|/2$ (e.g., see Fig 1); define $C_{cw}(v_{i})$ as the set of
vertices of $C$ not in $C_{ccw}(v_{i})$. We assume that $v_{i}$ is in neither
subset.

######  Lemma 2.4.

With $O(n)$ time preprocessing, given any two vertices $v_{i}$ and $v_{j}$ of
$C$, we can do the following in $O(1)$ time: (1) compute $d_{C}(v_{i},v_{j})$;
(2) determine whether $v_{j}$ is in $C_{ccw}(v_{i})$; (3) determine whether
$v_{i}$ and $v_{j}$ dominate each other.

######  Proof 2.5.

We first compute the weight $w(v_{i})$ for all vertices $v_{i}\in C$. This can
be done in $O(n)$ time. Then, we compute the length $|C|$. Next, by scanning
the vertices $v_{1},v_{2},\ldots,v_{m}$ on $C$, we compute an array
$A[1,\ldots,m]$ with $A[i]$ equal to the length of the path from $v_{1}$ to
$v_{i}$ clockwise along $C$. Hence, for any $1\leq i<j\leq m$, $A[j]-A[i]$ is
the length of the path from $v_{i}$ to $v_{j}$ clockwise along $C$ and
$|C|-(A[j]-A[i]))$ is the length of the path from $v_{i}$ to $v_{j}$
counterclockwise along $C$. Note that
$d_{C}(v_{i},v_{j})=\min\\{A[j]-A[i],|C|-(A[j]-A[i])\\}$.

Consider any two vertices $v_{i}$ and $v_{j}$ of $C$. Without loss of
generality, we assume $i<j$. By comparing $A[j]-A[i]$ with $|C|/2$, we can
determine whether $v_{j}$ is in $C_{ccw}(v_{i})$ in $O(1)$ time. As $w(v_{i})$
and $w(v_{j})$ are both available, whether $v_{i}$ and $v_{j}$ dominate each
other can be determined in $O(1)$ time.

With Lemma 2.4 in hand, starting from $v_{1}$, our pruning algorithm processes
the vertices of $C$ from $v_{1}$ to $v_{m}$ in order (see Algorithm 1 for the
pseudocode). The algorithm maintains a stack $S$, which is empty initially.
Consider a vertex $v_{i}$. If $S=\emptyset$, then we push $v_{i}$ into $S$.
Otherwise, let $v$ be the vertex at the top of $S$. If $v$ is not in
$C_{ccw}(v_{i})$, then we also push $v_{i}$ into $S$. Otherwise, we check
whether $v$ and $v_{i}$ dominate each other. If they do not dominate each
other, then we push $v_{i}$ into $S$. Otherwise, if $v_{i}$ dominates $v$, we
pop $v$ out of $S$, and then we continue to pop the new top element $v$ of $S$
out as long as the following three conditions are all satisfied: (1)
$S\neq\emptyset$; (2) $v\in C_{ccw}(v_{i})$; (3) $v_{i}$ dominates $v$. Once
one of the three conditions is not satisfied, we push $v_{i}$ into $S$.

After $v_{m}$ is processed, the first stage of the pruning algorithm is over.
In the second stage, we process the vertices in the stack $S$ in a bottom-up
manner until a vertex not in $C_{cw}(v_{1})$; the processing of a vertex is
done in the same way as above (the vertex should be removed from $S$ first).
Specifically, let $v_{i}$ be the vertex at the bottom of $S$. If $v_{i}$ is
not in $C_{cw}(v_{1})$, then we stop the algorithm and return the vertices in
the current stack $S$. Otherwise, we remove $v_{i}$ from $S$ and then apply
the same processing algorithm as above in the first stage (i.e., begin with
checking whether $S$ is empty).

Intuitively, the first stage of the algorithm does a “full-cycle” scan on $C$
while the second stage does a “half-cycle” scan (i.e., the half-cycle
clockwise from $v_{1}$). With Lemma 2.4, the algorithm can be implemented in
$O(n)$ time. The following lemma establishes the correctness of the algorithm.

Function  _ProcessVertex(_$v_{i}$ , $S$_)_:

if  _$S==\emptyset$_ then

$S.\mathbf{push}(v_{i})$ // Push vertex $v_{i}$ into the stack

end if

else

$v\leftarrow S.\mathbf{top}()$ // $S.\mathbf{top}()$ is the top element of the
stack

if  _$v\notin C_{ccw}(v_{i})$_ then

$S.\mathbf{push}(v_{i})$

end if

else if  _$v_{i}$ and $v$ do not dominate each other_ then

$S.\mathbf{push}(v_{i})$

end if

else if  _$v_{i}$ dominates $v$_ then

$S.\mathbf{pop}()$ // Pop the top element out of $S$

while  _$S\neq\emptyset$ $\mathbf{and}$ $S.\mathbf{top}()\in C_{ccw}(v_{i})$
$\mathbf{and}$ $v_{i}$ dominates $S.\mathbf{top}()$_ do

$S.\mathbf{pop}()$

end while

$S.\mathbf{push}(v_{i})$

end if

end if

end

Function  _Main(_$S=\emptyset$ , $C$_)_:

// the full-cycle scan

$S=\emptyset$

for  _$i=1,2,...,m$_ do

ProcessVertex($v_{i}$, $S$) // Call ProcessVertex function on $v_{i}$

end for

// the half-cycle scan

$v_{i}\leftarrow$ the bottom element of $S$

while  _$v_{i}\in C_{cw}(v_{1})$_ do

Remove $v_{i}$ from $S$

ProcessVertex($v_{i}$, $S$)

$v_{i}\leftarrow$ the bottom element of $S$

end while

return $S$

end

Algorithm 1 The pruning algorithm

######  Lemma 2.6.

Let $S$ be the stack after the algorithm is over.

  1. 1.

Each vertex of $C$ that is not in $S$ is dominated by a vertex in $S$.

  2. 2.

No two vertices of $S$ dominate each other.

######  Proof 2.7.

We first proves an observation about two transitive properties of the
domination relation, which will be used to prove the lemma.

#### Observation.

Let $v_{i},v_{j},v_{k}$ be any three vertices of $C$.

  1. 1.

If $v_{i}$ dominates $v_{j}$ and $v_{j}$ dominates $v_{k}$, then $v_{i}$
dominates $v_{k}$.

  2. 2.

If $v_{i}$ and $v_{j}$ do not dominate each other, $v_{j}$ and $v_{k}$ do not
dominate each other, and
$d_{C}(v_{i},v_{k})=d_{C}(v_{i},v_{j})+d_{C}(v_{j},v_{k})$, then $v_{i}$ and
$v_{k}$ do not dominate each other.

#### Proof of observation.

  1. 1.

Since $v_{i}$ dominates $v_{j}$ and $v_{j}$ dominates $v_{k}$, we have
$w(v_{i})>w(v_{j})+d_{C}(v_{i},v_{j})$ and
$w(v_{j})>w(v_{k})+d_{C}(v_{j},v_{k})$. Thus,
$w(v_{i})>w(v_{k})+d_{C}(v_{j},v_{k})+d_{C}(v_{i},v_{j})\geq
w(v_{k})+d_{C}(v_{i},v_{k})$. Hence, $v_{i}$ dominates $v_{k}$.

  2. 2.

As $v_{i}$ and $v_{j}$ do not dominate each other, $w(v_{i})\leq
w(v_{j})+d_{C}(v_{i},v_{j})$. As $v_{j}$ and $v_{k}$ do not dominate each
other, $w(v_{j})\leq w(v_{k})+d_{C}(v_{j},v_{k})$. Since
$d_{C}(v_{i},v_{k})=d_{C}(v_{i},v_{j})+d_{C}(v_{j},v_{k})$, we have

$\displaystyle w(v_{i})$ $\displaystyle\leq w(v_{j})+d_{C}(v_{i},v_{j})\leq
w(v_{k})+d_{C}(v_{j},v_{k})+d_{C}(v_{i},v_{j})=w(v_{k})+d_{C}(v_{i},v_{k}),$

and

$\displaystyle w(v_{k})\leq w(v_{j})+d_{C}(v_{j},v_{k})\leq
w(v_{i})+d_{C}(v_{i},v_{j})+d_{C}(v_{j},v_{k})=w(v_{i})+d_{C}(v_{i},v_{k}).$

Therefore, $v_{i}$ and $v_{k}$ do not dominate each other.

This proves the observation.

We are now in a position to prove the lemma.

#### Proving the first lemma statement.

We start with the first lemma statement. Consider a vertex $v_{i}$ of $C$ that
is not in $S$. According to our algorithm, $v_{i}$ may or may not be processed
in the second stage. If $v_{i}$ is processed in the second stage, then $v_{i}$
was pushed into $S$ during the first stage but is removed from $S$ in the
second stage (hence $v_{i}$ was processed twice in the algorithm). If $v_{i}$
is not processed in the second stage, then $v_{i}$ was not in $S$ at the end
of the first stage (hence $v_{i}$ is processed only once in the algorithm). In
either case, $v_{i}$ must be dominated by a vertex $v_{j}$ that was in $S$. If
$v_{j}$ is still in $S$ at the end of the algorithm, then the first lemma
statement is proved; otherwise, we can prove inductively that $v_{j}$ is
dominated by a vertex $v_{k}$ in $S$. By the above Observation, $v_{i}$ is
dominated by $v_{k}$ and thus the first lemma statement follows.

#### Proving the second lemma statement.

We next prove the second lemma statement. We first prove a claim: at any
moment during the algorithm, for any two vertices $v$ and $u$ of $S$ such that
$v$ is above $u$ in the stack $S$ and $u\in C_{ccw}(v)$, $v$ and $u$ do not
dominate each other. We use mathematical induction to prove it, as follows.

The claim is vacuously true in the beginning of the algorithm because
$S=\emptyset$. We assume that the claim holds on $S$ right before a vertex
$v_{i}$ is processed. We show below that the claim still holds on $S$ after
$v_{i}$ is processed. We first consider the processing of $v_{i}$ in the first
stage of the algorithm. Let $S$ refer to the stack right before $v_{i}$ is
processed. Let $v$ be the top element of $S$ if $S\neq\emptyset$. According to
our algorithm, $v_{i}$ is pushed into $S$ in the following four cases.

  1. 1.

$S=\emptyset$. In this case, $S=\\{v_{i}\\}$ after $v_{i}$ is processed.
Hence, the claim trivially holds.

  2. 2.

$S\neq\emptyset$, and $v\notin C_{ccw}(v_{i})$. In this case,
$C_{ccw}(v_{i})\cap S=\emptyset$, and thus the claim holds after $v_{i}$ is
processed.

  3. 3.

$S\neq\emptyset$, $v\in C_{ccw}(v_{i})$, and $v$ and $v_{i}$ do not dominate
each other. Let $v_{j}$ be any vertex of $S$ such that $v_{j}\in
C_{ccw}(v_{i})$. To prove the lemma, it suffices to show that $v_{j}$ and
$v_{i}$ do not dominate each other.

Indeed, if $v_{j}=v$, then we know that $v$ and $v_{i}$ dot not dominate each
other. Otherwise, $v_{j}$ is below $v$. As $v_{j}\in C_{ccw}(v_{i})$, since
$v\in C_{ccw}(v_{i})$, $v_{j}$ is also in $C_{ccw}(v)$. Since $v$ is above
$v_{j}$ in $S$, by the induction hypothesis $v_{j}$ and $v$ do not dominate
each other. Since both $v_{j}$ and $v$ are in $C_{ccw}(v_{i})$,
$d_{C}(v_{i},v_{j})=d_{C}(v_{i},v)+d_{C}(v,v_{j})$ holds. By the above
Observation, $v_{i}$ and $v_{j}$ do not dominate each other. Hence, the claim
holds after $v_{i}$ is processed.

  4. 4.

$S\neq\emptyset$, $v\in C_{ccw}(v_{i})$, and $v_{i}$ dominates $v$. In this
case, $v_{i}$ is pushed into $S$ after some vertices including $v$ are popped
out of $S$. First of all, since the claim holds on $S$, after vertices popped
out of $S$, the claim still holds on the new $S$. Let $S$ refer to the stack
right before $v_{i}$ is pushed in. Hence, the claim holds on $S$.

If $S=\emptyset$, then the claim still holds after $v_{i}$ is pushed in since
$v_{i}$ will be the only vertex in $S$. Otherwise, let $v^{\prime}$ be the top
element of $S$. If $v^{\prime}\not\in C_{ccw}(v_{i})$, then the claim still
holds on $S$ after $v_{i}$ is pushed in. Otherwise, $v_{i}$ does not dominate
$v^{\prime}$ and both $v$ and $v^{\prime}$ are in $C_{ccw}(v_{i})$, and thus
$v^{\prime}$ is in $C_{ccw}(v)$. By the induction hypothesis, $v$ and
$v^{\prime}$ do not dominate each other. As $v_{i}$ dominates $v$,
$v^{\prime}$ cannot dominate $v_{i}$ since otherwise $v^{\prime}$ would
dominate $v$ by the above Observation. Hence, $v_{i}$ and $v^{\prime}$ do not
dominate each other. By the same argument as the above third case, $v_{j}$ and
$v_{i}$ do not dominate each other for any vertex $v_{j}$ of $S$ with
$v_{j}\in C_{ccw}(v_{i})$. Hence, the claim holds after $v_{i}$ is pushed into
$S$.

The above proves that the claim still holds after $v_{i}$ is processed in the
first stage of the algorithm. Now consider processing $v_{i}$ in the second
stage. If $v_{i}\not\in C_{cw}(v_{1})$, then the algorithm stops without
changing $S$ and thus the claim still holds on $S$. Otherwise, $v_{i}$ is
removed from $S$, after which the claim still holds on $S$. Next, the
algorithm processes $v_{i}$ in the same way as in the first stage and thus we
can use the same argument as above to prove that the claim still holds after
$v_{i}$ is processed. This proves the claim.

In the sequel we prove the second lemma statement by using the claim.

Consider two vertices $v_{i}$ and $v_{j}$ in $S$ at the end of the algorithm.
Notice that either $v_{i}\in C_{ccw}(v_{j})$ or $v_{j}\in C_{ccw}(v_{i})$.
Without loss of generality, we assume that the former case holds. Our goal is
to show that $v_{i}$ and $v_{j}$ do not dominate each other.

If $v_{j}$ is above $v_{i}$ in $S$ at the end of the algorithm, then by the
above claim, $v_{j}$ and $v_{i}$ do not dominate each other. Otherwise,
according to our algorithm, $v_{i}$ must be last pushed into $S$ in the second
stage while $v_{j}$ must be last pushed into $S$ in the first stage. Further,
$v_{i}$ was also pushed into $S$ in the first stage before $v_{j}$ was
processed and $v_{i}$ was never popped out of $S$ in the first stage. Hence,
at the moment of the algorithm right before $v_{j}$ was processed, $v_{i}$ was
already in $S$. At the moment of the algorithm right after $v_{j}$ was
processed, $v_{j}$ was at the top of $S$ and $v_{i}$ was also in $S$. Since
$v_{i}\in C_{ccw}(v_{j})$, by the above claim, $v_{j}$ and $v_{i}$ do not
dominate each other. This proves the second lemma statement.

###  2.3 Computing the diameter

In the following, we use $S$ to refer to the stack after the pruning
algorithm. Note that $S$ cannot be empty. The following lemma shows how $S$
can help to find a vertex-weighted diametral pair of $C$.

######  Lemma 2.8.

If $|S|=1$, then any vertex-weighted diametral pair of $C$ must contain the
only vertex in $S$. Otherwise, for any vertex $v$ of $C$ that is not in $S$,
$v$ cannot be in any vertex-weighted diametral pair of $C$.

######  Proof 2.9.

Suppose $|S|=1$ and let $v$ be the only vertex in $S$. Then, by Lemma 2.6,
every vertex of $C\setminus\\{v\\}$ is dominated by $v$. Let $(u^{*},v^{*})$
be a vertex-weighted diametral pair of $C$. At least one of $u^{*}$ and
$v^{*}$ is not $v$. Without loss of generality, we assume $u^{*}\neq v$.
Hence, $u^{*}$ is dominated by $v$. Since $(u^{*},v^{*})$ is a vertex-weighted
diametral pair, by Lemma 2.2, $v^{*}$ must be $v$. This proves the lemma for
the case $|S|=1$.

Now assume $|S|>1$. Let $v$ be a vertex of $C$ that is not in $S$. By Lemma
2.6, $S$ has a vertex $u$ that dominates $v$. Assume to the contrary that $v$
is in a vertex-weighted diametral pair. Then by Lemma 2.2, the pair must be
$(u,v)$. As $|S|>1$, $S$ has another vertex $u^{\prime}$ that is not in
$\\{u,v\\}$. Since $u$ dominates $v$, we have $w(u)>w(v)+d_{C}(u,v)$. Since
$u$ and $u^{\prime}$ do not dominate each other, we have $w(u)\leq
w(u^{\prime})+d_{C}(u,u^{\prime})$. Consequently, we can derive

$\displaystyle w(u)+d_{C}(u,u^{\prime})+w(u^{\prime})\geq
w(u)+w(u)>w(u)+d_{C}(u,v)+w(v).$

But this incurs contradiction since $(u,v)$ is a vertex-weighted diametral
pair.

In light of Lemma 2.8, if $|S|=1$, we compute the diameter $\Delta(G)$ as
follows. Let $v$ be the only vertex in $S$. We find the vertex $u\in
C\setminus\\{v\\}$ that maximizes the value $w(u)+d_{C}(u,v)+w(v)$, which can
be done in $O(n)$ time with Lemma 2.4. By Lemma 2.8, $(u,v)$ is a vertex-
weighted diametral pair and $\Delta(G)=w(u)+d_{C}(u,v)+w(v)$.

If $|S|>1$, by Lemma 2.8, $\Delta(G)=\max_{u,v\in S}(w(u)+d_{C}(u,v)+w(v))$.
The following lemma finds a vertex-weighted diametral pair and thus computes
$\Delta(G)$ in linear time.

######  Lemma 2.10.

A pair $(u,v)$ of vertices in $S$ that maximizes the value
$w(u)+d_{C}(u,v)+w(v)$ can be found in $O(n)$ time.

######  Proof 2.11.

Consider a vertex $u\in S$. Let $v_{i}$ and $v_{j}$ be two vertices in $S\cap
C_{cw}(u)$ such that $d_{C}(u,v_{i})<d_{C}(u,v_{j})$ (e.g., see Fig. 2). Note
that $d_{C}(u,v_{j})=d_{C}(u,v_{i})+d_{C}(v_{i},v_{j})$. We claim that
$w(u)+d_{C}(u,v_{i})+w(v_{i})\leq w(u)+d_{C}(u,v_{j})+w(v_{j})$. Indeed, by
Lemma 2.6(2), $v_{i}$ and $v_{j}$ do not dominate each other. Hence,
$w(u)+d_{C}(u,v_{i})+w(v_{i})\leq
w(u)+d_{C}(u,v_{i})+w(v_{j})+d_{C}(v_{i},v_{j})=w(u)+d_{C}(u,v_{j})+w(v_{j})$.
The claim follows. The claim implies that if we consider the vertices $v$ of
$S\cap C_{cw}(u)$ from $u$ along $C$ in clockwise order, then the value
$w(u)+d_{C}(u,v)+w(v)$ is monotonically increasing. Similarly, if we consider
the vertices $v$ of $S\cap C_{ccw}(u)$ from $u$ along $C$ in counterclockwise
order, then the value $w(u)+d_{C}(u,v)+w(v)$ is monotonically increasing. Let
$u^{cw}$ (resp., $u^{ccw}$) refer to the farthest vertex from $u$ in
$C_{cw}(u)$ (resp., $C_{ccw}(u)$); e.g., see Fig. 2. Based on the above
discussion, it holds that $\max_{v\in
S\setminus\\{u\\}}(w(u)+d_{C}(u,v)+w(v))=\max\\{w(u)+d_{C}(u,u^{cw})+w(u^{cw}),w(u)+d_{C}(u,u^{ccw})+w(u^{ccw})\\}$.

Figure 2: Illustrating the proof of Lemma 2.10: we assume that $p$ is a point
on $C$ that together with $u$ partitions $C$ into two half-cycles of equal
length.

To find $u^{cw}$ and $u^{ccw}$, notice that if we traverse the vertices $u$ of
$S$ along $C$ in clockwise order, then both $u^{cw}$ and $u^{ccw}$ are also
ordered along $C$ in clockwise order. Hence, $u^{cw}$ and $u^{ccw}$ for all
vertices $u$ of $S$ can be found in total $O(n)$ time by traversing the
vertices of $S$ along $C$. Consequently, we have $\max_{u,v\in
S}((w(u)+d_{C}(u,v)+w(v))=\max_{u\in
S}\max\\{w(u)+d_{C}(u,u^{cw})+w(u^{cw}),w(u)+d_{C}(u,u^{ccw})+w(u^{ccw})\\}$,
which can be computed in $O(n)$ time.

The proof of the following theorem summarizes our algorithm.

######  Theorem 2.12.

The diameter (along with a diametral pair) of a unicycle graph can be computed
in linear time.

######  Proof 2.13.

Recall that there are two cases for a diametral pair $(u^{*},v^{*})$ of $G$:
(1) both $u^{*}$ and $v^{*}$ are in the same tree of $\mathcal{T}(G)$; (2)
$u^{*}$ and $v^{*}$ are in two different trees of $\mathcal{T}(G)$.

  * •

The first case can be handled by computing the diameter and the corresponding
diametral pair of each tree of $\mathcal{T}(G)$, which can be done in total
$O(n)$ time. The longest diameter of these trees is kept as a candidate
diameter of $G$ and the corresponding diametral pair is kept as a candidate
diametral pair.

  * •

For the second case, we first compute the weights $w(v_{i})$ for all vertices
$v_{i}$ of the cycle $C$; for each $v_{i}$, we also store its farthest vertex
$f(v_{i})$ in $T(v_{i})$. Then, we perform the preprocessing of Lemma 2.4.
Next, we run the pruning algorithm to obtain $S$. If $|S|=1$, we find a
vertex-weighted diametral pair of $C$ as described above; otherwise, we use
Lemma 2.10 to find such a pair. In either case, let $(u,v)$ denote the pair.
Then, a candidate diameter is $w(u)+d_{C}(u,v)+w(v)$. In addition,
$(f(u),f(v))$ is a candidate diametral pair of $G$.

We compare the candidate diameters obtained from the above two cases and
return the larger one as the diameter of $G$; the corresponding diametral pair
is a diametral pair of $G$. The running time of the overall algorithm is
$O(n)$.

##  3 The Diameter-Optimally Augmenting Trees (DOAT)

In this section, we solve the DOAT problem in $O(n^{2}\log n)$ time and $O(n)$
space. Our algorithm for computing the diameter of a unicycle graph will be
used as a subroutine.

###  3.1 Observations

We follow the same notation as in Section 2 such as $\pi_{G^{\prime}}(s,t)$,
$d_{G^{\prime}}(s,t)$, $\Delta(G)$.

Let $T$ be a tree of $n$ vertices such that each edge of $T$ has a positive
length. For any two vertices $u$ and $v$ of $T$, we use $e(u,v)$ to refer to
the shortcut connecting $u$ and $v$; note that even if $T$ already has an edge
connecting them, we can always assume that there is an alternative shortcut
(or we could also consider the shortcut as the edge itself with the same
length). Let $|e(u,v)|$ denote the length of $e(u,v)$. Again, there is an
oracle that can return the value $|e(u,v)|$ in $O(1)$ time for any shortcut
$e(u,v)$. Denote by $T+e(u,v)$ the graph after adding $e(u,v)$ to $T$. The
goal of the DOAT problem is to find a shortcut $e(u,v)$ so that the diameter
of the new graph $\Delta(T+e(u,v))$ is minimized. Let $\Delta^{*}(T)$ be the
diameter of an optimal solution. In the following we assume that
$\Delta^{*}(T)<\Delta(T)$, since otherwise any shortcut would be sufficient.

For any shortcut $e(u,v)$, $T$ has a unique path $\pi_{T}(u,v)$ between $u$
and $v$. We make an assumption that $|e(u,v)|<d_{T}(u,v)$ since otherwise
$e(u,v)$ can never be used (indeed, whenever $e(u,v)$ was used in a shortest
path, we could always replace it with $\pi_{T}(u,v)$ to get a shorter path).
This assumption is only for the argument of the correctness of our algorithm;
the algorithm itself still uses the true value of $|e(u,v)|$ (this does not
affect the correctness, because if $|e(u,v)|\geq d_{T}(u,v)$, then $e(u,v)$
cannot be an optimal shortcut). For the reference purpose, we refer to this
assumption as the shortcut length assumption.

At the outset, we compute a diametral path $P$ of $T$ in $O(n)$ time. Let
$v_{1},v_{2},\ldots,v_{m}$ be the vertices of $P$ ordered along it. Removing
the edges of $P$ from $T$ results in $m$ connected components of $T$, each of
which is a tree containing a vertex of $P$; we let $T(v_{i})$ denote the tree
containing $v_{i}$. For each $v_{i}$, we define a weight $w(v_{i})$ as the
distance from $v_{i}$ to its farthest vertex in $T(v_{i})$. Let
$\mathcal{T}=\\{T(v_{i})\ |\ 1\leq i\leq m\\}$.

For any pair $(i,j)$ of indices with $1\leq i<j\leq m$, we define a critical
pair of vertices $(x,y)$ with $x\in T(v_{i})$ and $y\in T(v_{j})$ such that
they minimize the value
$d_{T(v_{i})}(v_{i},x^{\prime})+|e(x^{\prime},y^{\prime})|+d_{T(v_{j})}(y^{\prime},v_{j})$
among all vertex pairs $(x^{\prime},y^{\prime})$ with $x^{\prime}\in T(v_{i})$
and $y^{\prime}\in T(v_{j})$.

The following lemma will be used on several occasions later on.

######  Lemma 3.1.

For any vertex $v$ in any tree $T(v_{k})\in\mathcal{T}$, it holds that
$d_{T(v_{k})}(v,v_{k})\leq\\\
\min\\{d_{T}(v_{1},v_{k}),d_{T}(v_{k},v_{m})\\}$. Also,
$d_{T}(v_{1},v_{k})=d_{P}(v_{1},v_{k})$ and
$d_{T}(v_{k},v_{m})=d_{P}(v_{k},v_{m})$.

######  Proof 3.2.

Assume to the contrary that
$d_{T(v_{k})}(v,v_{k})>\min\\{d_{T}(v_{1},v_{k}),d_{T}(v_{k},v_{m})\\}$.
Without loss of generality, we assume
$d_{T(v_{k})}(v,v_{k})>d_{T}(v_{1},v_{k})$. Then,
$d_{T}(v,v_{m})=d_{T(v_{k})}(v,v_{k})+d_{T}(v_{k},v_{m})>d_{T}(v_{1},v_{k})+d_{T}(v_{k},v_{m})=d_{T}(v_{1},v_{m})=\Delta(T)$,
a contradiction.

The second part of the lemma holds because $P$ is a path of $T$.

The following lemma demonstrates why critical pairs are “critical”.

######  Lemma 3.3.

Suppose $e(u^{*},v^{*})$ is an optimal shortcut with $u^{*}\in T(v_{i})$ and
$v^{*}\in T(v_{j})$. Then, $i\neq j$ and any critical pair of $(i,j)$ also
defines an optimal shortcut.

######  Proof 3.4.

Because $P$ is a diametral path of $T$, if $i=j$, then $P$ is still the
shortest path from $v_{1}$ to $v_{m}$ in the new graph $T+e(u^{*},v^{*})$, and
thus we have
$\Delta^{*}=d_{T+e(u^{*},v^{*})}(v_{1},v_{m})=d_{T}(v_{1},v_{m})=\Delta(T)$.
But this contradicts with our assumption $\Delta^{*}<\Delta(T)$. Hence, $i\neq
j$.

Let $(x,y)$ be a critical pair of $(i,j)$ with $x\in T(v_{i})$ and $y\in
T(v_{j})$. Define
$\phi(v_{i},v_{j})=d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(v_{j},y)$ and
$\phi^{*}(v_{i},v_{j})=d_{T(v_{i})}(v_{i},u^{*})+|e(u^{*},v^{*})|+d_{T(v_{j})}(v_{j},v^{*})$.
By the definition of critical pairs, we have
$\phi(v_{i},v_{j})\leq\phi^{*}(v_{i},v_{j})$. Also, due to the shortcut length
assumption, it holds that
$\phi(v_{i},v_{j})\leq|e(v_{i},v_{j})|<d_{T}(v_{i},v_{j})$.

In the following, we prove that
$d_{T+e(x,y)}(u,v)\leq\Delta(T+e(u^{*},v^{*}))$ for any two vertices $u,v\in
T$. This will prove the lemma. To simplify the notation, let $T_{xy}=T+e(x,y)$
and $T^{*}=T+e(u^{*},y^{*})$.

First of all, if $d_{T^{*}}(u,v)=d_{T}(u,v)$, then $d_{T_{xy}}(u,v)\leq
d_{T}(u,v)=d_{T^{*}}(u,v)\leq\Delta(T^{*})$. Below we assume
$d_{T^{*}}(u,v)\neq d_{T}(u,v)$. Thus, $d_{T^{*}}(u,v)<d_{T}(u,v)$ and the
shortest path $\pi_{T^{*}}(u,v)$ must contain the shortcut $e(u^{*},v^{*})$.

Let $T(v_{k})$ and $T(v_{h})$ be the trees of $\mathcal{T}$ that contain $u$
and $v$, respectively, with $k\leq h$. Based on relationship of the indices
$k$, $h$, $i$, and $j$, there are several cases.

  1. 1.

$\\{k,h\\}\cap\\{i,j\\}=\emptyset$; e.g., see Fig. 4. In this case, we have

$\displaystyle d_{T_{xy}}(u,v)$ $\displaystyle\leq
d_{T}(u,v_{i})+\phi(v_{i},v_{j})+d_{T}(v_{j},v)$ $\displaystyle\leq
d_{T}(u,v_{i})+\phi^{*}(v_{i},v_{j})+d_{T}(v_{j},v)$
$\displaystyle=d_{T^{*}}(u,v)\leq\Delta(T^{*}).$

Note that $d_{T}(u,v_{i})+\phi^{*}(v_{i},v_{j})+d_{T}(v_{j},v)=d_{T^{*}}(u,v)$
because $\pi_{T^{*}}(u,v)$ contains $e(u^{*},v^{*})$ and $k\leq h$.

Figure 3: Illustrating the case $\\{k,h\\}\cap\\{i,j\\}=\emptyset$.

Figure 4: Illustrating the case $k=i$ and $h=j$.

  2. 2.

$k=i$ and $h=j$; e.g., see Fig. 4. In this case, we have

$\displaystyle d_{T_{xy}}(u,v)$ $\displaystyle\leq
d_{T(v_{i})}(u,x)+|e(x,y)|+d_{T(v_{j})}(y,v)$ $\displaystyle\leq
d_{T(v_{i})}(u,v_{i})+d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(y,v_{j})+d_{T(v_{j})}(v_{j},v).$

By Lemma 3.1, $d_{T(v_{i})}(u,v_{i})\leq d_{T}(v_{1},v_{i})$ and
$d_{T(v_{j})}(v_{j},v)\leq d_{T}(v_{j},v_{m})$. Hence, we can obtain

$\displaystyle d_{T_{xy}}(u,v)$ $\displaystyle\leq
d_{T}(v_{1},v_{i})+d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(y,v_{j})+d_{T}(v_{j},v_{m})$
$\displaystyle=d_{T}(v_{1},v_{i})+\phi(v_{i},v_{j})+d_{T}(v_{j},v_{m})$
$\displaystyle\leq
d_{T}(v_{1},v_{i})+\phi^{*}(v_{i},v_{j})+d_{T}(v_{j},v_{m})$
$\displaystyle=d_{T^{*}}(v_{1},v_{m})\leq\Delta(T^{*}).$

Figure 5: Illustrating the case $k=i$, $h>i$, and $h\neq j$.

Figure 6: Illustrating the case $k=h=i$.

  3. 3.

$k=i$, $h>i$, and $h\neq j$; e.g., see Fig. 6. In this case, we have

$\displaystyle d_{T_{xy}}(u,v)$ $\displaystyle\leq
d_{T(v_{i})}(u,x)+|e(x,y)|+d_{T(v_{j})}(y,v_{j})+d_{T}(v_{j},v)$
$\displaystyle\leq
d_{T(v_{i})}(u,v_{i})+d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(y,v_{j})+d_{T}(v_{j},v)$
$\displaystyle\leq
d_{T}(v_{1},v_{i})+d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(y,v_{j})+d_{T}(v_{j},v)$
$\displaystyle=d_{T}(v_{1},v_{i})+\phi(v_{i},v_{j})+d_{T}(v_{j},v)$
$\displaystyle\leq d_{T}(v_{1},v_{i})+\phi^{*}(v_{i},v_{j})+d_{T}(v_{j},v).$

On the other hand, since $h>i$, we also have

$\displaystyle d_{T_{xy}}(u,v)$ $\displaystyle\leq
d_{T(v_{i})}(u,v_{i})+d_{T}(v_{i},v)\leq d_{T}(v_{1},v_{i})+d_{T}(v_{i},v).$

Notice that
$d_{T^{*}}(v_{1},v)=\min\\{d_{T}(v_{1},v_{i})+d_{T}(v_{i},v),d_{T}(v_{1},v_{i})+\phi^{*}(v_{i},v_{j})+d_{T}(v_{j},v)\\}$.
Combining the above two inequalities, we derive $d_{T_{xy}}(u,v)\leq
d_{T^{*}}(v_{1},v)\leq\Delta(T^{*})$.

  4. 4.

$k<j$, $k\neq i$, and $h=j$. This is case is symmetric to the above case and
we can prove $d_{T_{xy}}(u,v)\leq\Delta(T^{*})$ by a similar argument.

  5. 5.

$k=h=i$; e.g., see Fig. 6. We claim that this case cannot happen. Indeed,
recall that $\pi_{T^{*}}(u,v)$ contains $e(u^{*},v^{*})$. Since both $u$ and
$v$ are in $T(v_{i})$, $\pi_{T^{*}}(u,v)$ must also contain $P[v_{i},v_{j}]$,
where $P[v_{i},v_{j}]$ is the subpath of $P$ between $v_{i}$ and $v_{j}$. On
the other hand, $\Delta(T)=d_{T}(v_{1},v_{m})$, which is equal to the length
of $P$. Since $\Delta(T)>\Delta^{*}=\Delta(T^{*})$, $\pi_{T^{*}}(v_{1},v_{m})$
must contain the shortcut $e(u^{*},v^{*})$ but cannot contain
$P[v_{i},v_{j}]$. This implies that $P[v_{i},v_{j}]$ is not a shortest path
between $v_{i}$ and $v_{j}$ in $T^{*}$. However, since $\pi_{T^{*}}(u,v)$,
which is a shortest path between $u$ and $v$ in $T^{*}$, contains
$P[v_{i},v_{j}]$, $P[v_{i},v_{j}]$ must be a shortest path between $v_{i}$ and
$v_{j}$ in $T^{*}$. We thus obtain contradiction.

  6. 6.

$k=h=j$. This case is symmetric to the above case. By a similar argument, we
can show that it cannot happen.

Figure 7: Illustrating the case $k<i$ and $h=i$.

  7. 7.

$k<i$ and $h=i$; e.g., see Fig. 7. We claim that this case cannot happen.
Indeed, since $\pi_{T^{*}}(u,v)$ contains $e(u^{*},v^{*})$ and $k<i$,
$\pi_{T^{*}}(u,v)$ must also contain the subpath of $P$ between $v_{i}$ and
$v_{j}$. By the same analysis as the above fifth case, we can obtain
contradiction.

  8. 8.

$k=j$ and $h>j$. This case is symmetric to the above case. By a similar
argument, we can show that it cannot happen.

In summary, $d_{T_{xy}}(u,v)\leq\Delta(T^{*})$ holds in all possible cases.
The lemma thus follows.

###  3.2 Reducing DOAT to finding a shortcut for $\boldsymbol{P}$

In light of Lemma 3.3, we reduce our DOAT problem on $T$ to finding a shortcut
for the vertex-weighted path $P$ as follows.

For an index pair $(i,j)$ with $1\leq i<j\leq m$, we define a shortcut
$\overline{e}(v_{i},v_{j})$ connecting $v_{i}$ and $v_{j}$ with length
$|\overline{e}(v_{i},v_{j})|=d_{T(v_{i})}(v_{i},x)+|e(x,y)|+d_{T(v_{j})}(v_{j},y)$,
where $(x,y)$ is a critical pair of $(i,j)$. The diameter
$\Delta(P+\overline{e}(v_{i},v_{j}))$ is defined as $\max_{1\leq k<h\leq
m}\\{w(v_{k})+d_{P+\overline{e}(v_{i},v_{j})}(v_{k},v_{h})+w(v_{h})\\}$. The
diameter-optimally augmenting path (DOAP) problem on $P$ is to find a shortcut
$\overline{e}(v_{i},v_{j})$ so that the diameter
$\Delta(P+\overline{e}(v_{i},v_{j}))$ is minimized; we use $\Delta^{*}(P)$ to
denote the minimized diameter.

With the help of Lemma 3.3, the following lemma shows that the DOAT problem on
$T$ can be reduced to the DOAP problem on $P$. Similar problem reductions were
also used in [14, 3].

######  Lemma 3.5.

  1. 1.

For any index pair $(i,j)$ with $1\leq i<j\leq m$, it holds that
$\Delta(P+\overline{e}(v_{i},v_{j}))=\Delta(T+e(x,y))$, where $(x,y)$ is a
critical pair of $(i,j)$.

  2. 2.

If $\overline{e}(v_{i},v_{j})$ is an optimal shortcut for the DOAP problem on
$P$, then $e(x,y)$ is an optimal shortcut for the DOAT problem on $T$, where
$(x,y)$ is a critical pair of $(i,j)$.

  3. 3.

$\Delta^{*}(T)=\Delta^{*}(P)$.

######  Proof 3.6.

Before proving the first lemma statement, we first use it to prove the second
and third lemma statements.

#### The second lemma statement.

Suppose $\overline{e}(v_{i},v_{j})$ is an optimal shortcut for the DOAP
problem on $P$. By the first lemma statement, we have
$\Delta(P+\overline{e}(v_{i},v_{j}))=\Delta(T+e(x,y))$. Assume to the contrary
that $e(x,y)$ is not an optimal shortcut for the DOAT problem for $T$, and let
$e(u^{*},v^{*})$ instead be an optimal shortcut, with $u^{*}\in T(v_{k})$ and
$v^{*}\in T(v_{h})$. Then, $\Delta(T+e(x,y))>\Delta(T+e(u^{*},v^{*}))$. By
Lemma 3.3, $k\neq h$ and the critical pair $(x^{\prime},y^{\prime})$ of
$(k,h)$ also defines an optimal shortcut for $T$. Hence,
$\Delta(T+e(u^{*},v^{*}))=\Delta(T+e(x^{\prime},y^{\prime}))$. By the first
lemma statement,
$\Delta(P+\overline{e}(v_{k},v_{h}))=\Delta(T+e(x^{\prime},y^{\prime}))$.
Combining all above, we obtain

$\displaystyle\Delta(P+\overline{e}(v_{k},v_{h}))=\Delta(T+e(x^{\prime},y^{\prime}))=\Delta(T+e(u^{*},v^{*}))<\Delta(T+e(x,y))=\Delta(P+\overline{e}(v_{i},v_{j})).$

But this incurs contradiction since $\overline{e}(v_{i},v_{j})$ is an optimal
shortcut for the DOAP problem on $P$. Hence, the second lemma statement is
proved.

#### The third lemma statement.

The third lemma statement follows immediately from the first two lemma
statements. Indeed, suppose $\overline{e}(v_{i},v_{j})$ is an optimal solution
for the DOAP problem on $P$. Then, by the second lemma statement, $e(x,y)$ is
an optimal shortcut for the DOAT problem on $T$, where $(x,y)$ is a critical
pair of $(i,j)$. Hence, we have
$\Delta(P^{*})=\Delta(P+\overline{e}(v_{i},v_{j}))$ and
$\Delta(T^{*})=\Delta(T+e(x,y))$. By the first lemma statement,
$\Delta(P+\overline{e}(v_{i},v_{j}))=\Delta(T+e(x,y))$. Hence,
$\Delta^{*}(T)=\Delta^{*}(P)$.

#### The first lemma statement.

We now prove the first lemma statement. To simplify the notation, let
$P^{\prime}=P+\overline{e}(v_{i},v_{j})$ and $T^{\prime}=T+e(x,y)$. Our goal
is to prove $\Delta(P^{\prime})=\Delta(T^{\prime})$.

First of all, because $(x,y)$ is a critical pair of $(i,j)$,
$d_{P^{\prime}}(v_{k},v_{h})=d_{T^{\prime}}(v_{k},v_{h})$ holds for any two
vertices $v_{k}$ and $v_{h}$ of $P$ with $1\leq k<h\leq m$.

We first prove that $\Delta(P^{\prime})\leq\Delta(T^{\prime})$. Let $v_{k}$
and $v_{h}$ be any two vertices of $P$ with $1\leq k<h\leq m$. It suffices to
show that
$w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})\leq\Delta(T^{\prime})$.

Let $u$ be the vertex of $T(v_{k})$ farthest from $v_{k}$, i.e.,
$w(v_{k})=d_{T(v_{k})}(v_{k},u)$. Similarly, let $v$ be the vertex of
$T(v_{h})$ farthest from $v_{h}$. Recall that $i<j$ and $k<h$. Depending on
the values of $i,j,k,h$, there are several cases.

Figure 8: Illustrating the case $i=k$ and $j=h$.

Figure 9: Illustrating the case $\\{i,j\\}\cap\\{k,h\\}=\emptyset$.

  1. 1.

$i=k$ and $j=h$; e.g., see Fig. 9. In this case,
$d_{T^{\prime}}(v_{1},v_{k})=d_{T}(v_{1},v_{k})$ and
$d_{T^{\prime}}(v_{h},v_{m})=d_{T}(v_{h},v_{m})$. By Lemma 3.1,
$d_{T(v_{k})}(u,v_{k})\leq d_{T}(v_{1},v_{k})$ and $d_{T(v_{h})}(v,v_{h})\leq
d_{T}(v_{h},v_{m})$. Hence, we can derive

$\displaystyle w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})$
$\displaystyle=d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle\leq
d_{T}(v_{1},v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T}(v_{h},v_{m})$
$\displaystyle=d_{T^{\prime}}(v_{1},v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T^{\prime}}(v_{h},v_{m})$
$\displaystyle=d_{T^{\prime}}(v_{1},v_{m})\leq\Delta(T^{\prime}).$

  2. 2.

$\\{i,j\\}\cap\\{k,h\\}=\emptyset$; e.g., see Fig. 9. In this case, the
shortest path $\pi_{T^{\prime}}(u,v)$ between $u$ and $v$ in $T^{\prime}$ must
contain $\pi_{T(v_{k})}(u,v_{k})$ and $\pi_{T(v_{h})}(v_{h},v)$. Hence, we
have

$\displaystyle w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})$
$\displaystyle=d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle=d_{T^{\prime}}(u,v)\leq\Delta(T^{\prime}).$

Figure 10: Illustrating the case $i=k$ and $j\neq h$.

Figure 11: Illustrating the case $j=k$.

  3. 3.

$i=k$ and $j\neq h$; e.g., see Fig. 11. In this case, the shortest path
$\pi_{T^{\prime}}(v_{1},v)$ between $v_{1}$ and $v$ in $T^{\prime}$ must
contain $\pi_{T}(v_{1},v_{k})$ and $\pi_{T(v_{h})}(v_{h},v)$. Hence, we have

$\displaystyle w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})$
$\displaystyle=d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle\leq
d_{T}(v_{1},v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle=d_{T^{\prime}}(v_{1},v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle=d_{T^{\prime}}(v_{1},v)\leq\Delta(T^{\prime}).$

  4. 4.

$i\neq k$ and $j=h$. This case is symmetric to the above case. By a similar
argument, we can show that
$w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})\leq\Delta(T^{\prime})$.

  5. 5.

$j=k$; e.g., see Fig. 11. In this case, we claim that
$\pi_{T(v_{k})}(u,v_{k})$ is $\pi_{T^{\prime}}(u,v_{k})$. Indeed, assume to
the contrary that this is not true. Then, $\pi_{T^{\prime}}(u,v_{k})$ must
contain the shortcut $e(x,y)$. This further implies that
$\pi_{T^{\prime}}(u,v_{k})$ must contain $\pi_{T}(v_{i},v_{k})$, which is the
subpath of $P$ between $v_{i}$ and $v_{k}$ (=$v_{j}$). Since $(x,y)$ is a
critical pair of $(i,j)$, $\pi_{T}(v_{i},v_{k})$ is no shorter than the path
$\pi^{\prime}=\pi_{T(v_{i})}(v_{i},x)\cup e(x,y)\cup\pi_{T(v_{k})}(y,v_{k})$.
Therefore, if we replace $\pi_{T}(v_{i},v_{k})$ by $\pi^{\prime}$ in
$\pi_{T^{\prime}}(u,v_{k})$, we can obtain another shortest path
$\pi^{\prime}_{T^{\prime}}(u,v_{k})$ from $u$ to $v_{k}$ in $T^{\prime}$.
However, $\pi^{\prime}_{T^{\prime}}(u,v_{k})$ cannot be a shortest path as it
contains $e(x,y)$ twice. This incurs contradiction and thus the claim follows.

Due to the claim, we have
$d_{T^{\prime}}(u,v)=d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$.
We can now obtain

$\displaystyle w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})$
$\displaystyle=d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle=d_{T^{\prime}}(u,v)\leq\Delta(T^{\prime}).$

  6. 6.

$i=h$. This case is symmetric to the above case. By a similar argument, we can
show that
$w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})\leq\Delta(T^{\prime})$.

This proves that $\Delta(P^{\prime})\leq\Delta(T^{\prime})$.

Next we prove that $\Delta(T^{\prime})\leq\Delta(P^{\prime})$. Let $u$ and $v$
be any two vertices of $T$ with $u\in T(v_{k})$ and $v\in T(v_{h})$, with
$1\leq k\leq h\leq m$. It suffices to show that
$d_{T^{\prime}}(u,v)\leq\Delta(P^{\prime})$.

If $k\neq h$, then we can deduce

$\displaystyle d_{T^{\prime}}(u,v)$ $\displaystyle\leq
d_{T(v_{k})}(u,v_{k})+d_{T^{\prime}}(v_{k},v_{h})+d_{T(v_{h})}(v_{h},v)$
$\displaystyle\leq w(v_{k})+d_{T^{\prime}}(v_{k},v_{h})+w(v_{h})$
$\displaystyle=w(v_{k})+d_{P^{\prime}}(v_{k},v_{h})+w(v_{h})\leq\Delta(P^{\prime}).$

Figure 12: Illustrating the case where both $u$ and $v$ are in $T(v_{k})$.

If $k=h$, then both $u$ and $v$ are in $T(v_{k})$; e.g., see Fig. 12. Hence,
it holds that $d_{T^{\prime}}(u,v)\leq d_{T(v_{k})}(u,v)\leq
d_{T(v_{k})}(v,v_{k})+d_{T(v_{k})}(v_{k},u)$. By Lemma 3.1,
$d_{T(v_{k})}(v,v_{k})\leq\min\\{d_{T}(v_{1},v_{k}),d_{T}(v_{k},v_{m})\\}$. On
the other hand, notice that the shortest path from $u$ to either $v_{1}$ or
$v_{m}$ in $T^{\prime}$ does not contain the shortcut $e(x,y)$. Without loss
of generality, we assume that the shortest path $\pi_{T^{\prime}}(u,v_{1})$
from $u$ to $v_{1}$ in $T^{\prime}$ does not contain $e(x,y)$. Thus,
$\pi_{T^{\prime}}(u,v_{1})$ must contain $\pi_{T}(v_{1},v_{k})$, implying that
$\pi_{T}(v_{1},v_{k})$ is $\pi_{T^{\prime}}(v_{1},v_{k})$. Note that
$\pi_{T}(v_{1},v_{k})$ is $\pi_{P}(v_{1},v_{k})$, which is the portion of $P$
between $v_{1}$ and $v_{k}$. Hence, $\pi_{P}(v_{1},v_{k})$ is also the
shortest path from $v_{1}$ to $v_{k}$ in $P^{\prime}$ (i.e.,
$\pi_{P^{\prime}}(v_{1},v_{k})$ does not contain the shortcut
$\overline{e}(v_{i},v_{j})$). Therefore,
$d_{P^{\prime}}(v_{1},v_{k})=d_{T}(v_{1},v_{k})$. Since $u\in T(v_{k})$,
$w(v_{k})\geq d_{T(v_{k})}(v_{k},u)$. Combining all above we can derive

$\displaystyle\Delta(P^{\prime})$ $\displaystyle\geq
w(v_{1})+d_{P^{\prime}}(v_{1},v_{k})+w(v_{k})=w(v_{1})+d_{T}(v_{1},v_{k})+w(v_{k})$
$\displaystyle\geq d_{T}(v_{1},v_{k})+w(v_{k})\geq
d_{T}(v_{1},v_{k})+d_{T(v_{k})}(v_{k},u)$ $\displaystyle\geq
d_{T(v_{k})}(v,v_{k})+d_{T(v_{k})}(v_{k},u)\geq d_{T^{\prime}}(u,v).$

This proves the first lemma statement and thus the entire lemma.

In light of Lemma 3.5, we will focus on solving the DOAP problem on the
vertex-weighted path $P$. Notice that the lengths of the shortcuts of $P$ have
not been computed yet.

###  3.3 Computing an optimal shortcut for $\boldsymbol{P}$

To find an optimal shortcut for the DOAP problem on $P$, for each
$i\in[1,m-1]$, we will compute an index $j(i)$ that minimizes the diameter
$\Delta(P+\overline{e}(v_{i},v_{j}))$ among all indices $j\in[i+1,m]$, i.e.,
$j(i)=\arg\min_{i+1\leq j\leq m}\Delta(P+\overline{e}(v_{i},v_{j}))$, as well
as the diameter $\Delta(P+\overline{e}(v_{i},v_{j(i)}))$. After that, the
optimal shortcut of $P$ is the one that minimizes
$\Delta(P+\overline{e}(v_{i},v_{j(i)}))$ among the shortcuts
$\overline{e}(i,j(i))$ for all $i\in[1,m-1]$. We refer to the shortcuts for
$\overline{e}(v_{i},v_{j})$ for all $j\in[i+1,m]$ as $v_{i}$-shortcuts.
Therefore, our goal is to find an optimal $v_{i}$-shortcut
$\overline{e}(i,j(i))$ for each $i\in[1,m-1]$.

Let $n_{i}$ denote the number of vertices in $T(v_{i})$, for each $1\leq i\leq
m$. Note that $n=\sum_{i=1}^{m}n_{i}$. Fix an index $i$ with $1\leq i\leq
m-1$. In the following, we will present an algorithm that computes an optimal
$v_{i}$-shortcut $\overline{e}(v_{i},v_{j(i)})$ and the diameter
$\Delta(P+\overline{e}(v_{i},v_{j(i)}))$ in $O(n\cdot n_{i}+n\log n)$ time and
$O(n)$ space. In this way, solving the DOAP problem on $P$ takes $O(n^{2}\log
n)$ time and $O(n)$ space in total.

Figure 13: $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{k})$
if
$|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{k})\leq|\overline{e}(v_{i},v_{k})|$,
i.e., the length of the red path is less than or equal to the length of the
blue path.

We introduce a domination relationship among $v_{i}$-shortcuts.

######  Definition 3.7.

For any two index $j$ and $k$ with $i<j<k\leq m$, we say that
$\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{k})$ if
$|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{k})\leq|\overline{e}(v_{i},v_{k})|$;
e.g., see Fig. 13.

The following lemma implies that if $\overline{e}(v_{i},v_{j})$ dominates
$\overline{e}(v_{i},v_{k})$, then shortcut $\overline{e}(v_{i},v_{k})$ can be
ignored or “pruned”.

######  Lemma 3.8.

If $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{k})$, then
$\Delta(P+\overline{e}(v_{i},v_{j}))\leq\Delta(P+\overline{e}(v_{i},v_{k}))$.

######  Proof 3.9.

Let $u$ and $v$ be any two vertices of $P$. To prove the lemma, it suffices to
show that $d_{P+\overline{e}(v_{i},v_{j})}(u,v)\leq
d_{P+\overline{e}(v_{i},v_{k})}(u,v)$.

If $d_{P+\overline{e}(v_{i},v_{k})}(u,v)=d_{P}(u,v)$, then
$d_{P+\overline{e}(v_{i},v_{j})}(u,v)\leq
d_{P}(u,v)=d_{P+\overline{e}(v_{i},v_{k})}(u,v)$. Otherwise, the shortest path
$\pi_{P+\overline{e}(v_{i},v_{k})}(u,v)$ contains the shortcut
$\overline{e}(v_{i},v_{k})$. Hence, $d_{P+\overline{e}(v_{i},v_{k})}(u,v)$ is
equal to either $d_{P}(u,v_{i})+|\overline{e}(v_{i},v_{k})|+d_{P}(v_{k},v)$ or
$d_{P}(u,v_{k})+|\overline{e}(v_{i},v_{k})|+d_{P}(v_{i},v)$. We assume that it
is the former case. Then we have

$\displaystyle d_{P+\overline{e}(v_{i},v_{k})}(u,v)$
$\displaystyle=d_{P}(u,v_{i})+|\overline{e}(v_{i},v_{k})|+d_{P}(v_{k},v)$
$\displaystyle\geq
d_{P}(u,v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{k})+d_{P}(v_{k},v)$
$\displaystyle\geq d_{P}(u,v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v)$
$\displaystyle\geq d_{P+\overline{e}(v_{i},v_{j})}(u,v)$

The lemma thus follows.

Let $S_{i}$ be the set of all $v_{i}$-shortcuts, i.e.,
$S_{i}=\\{\overline{e}(v_{i},v_{j})\|\ i+1\leq j\leq m\\}$. In the following,
we describe a pruning algorithm that computes a subset $S$ of $S_{i}$ such
that no two shortcuts of $S$ dominate each other and $S$ contains at least one
optimal $v_{i}$-shortcut. As will be seen later, these properties of $S$ allow
an efficient algorithm to find an optimal $v_{i}$-shortcut.

Before running the pruning algorithm, we compute the lengths of shortcuts of
$S_{i}$ by brute force, as follows. First, with $O(n)$ time preprocessing,
given any two vertices $u$ and $v$ with $u\in T(v_{i})$ and $v\in T(v_{j})$
for $j\neq i$, we can compute $d_{T}(u,v)$ in constant time. Consider a tree
$T(v_{j})$ with $j\geq i+1$. Computing the length of
$\overline{e}(v_{i},v_{j})$ reduces to finding a critical pair of $(i,j)$. To
this end, we compute $d_{T(v_{i})}(v_{i},u)+|e(u,v)|+d_{T(v_{j})}(v,v_{j})$
for all vertices $u\in T(v_{i})$ and all vertices $v\in T(v_{j})$, which can
be done in $O(n_{i}\cdot n_{j})$ time (and $O(n)$ space). As such, computing
the lengths of all shortcuts of $S_{i}$ takes $O(n_{i}\cdot n)$ time.

Our pruning algorithm processes the shortcuts $\overline{e}(v_{i},v_{j})$ for
all $j=i+1,i+2,\ldots,m$ one by one. A stack $S$ is maintained and
$S=\emptyset$ initially. Consider any $j\in[i+1,m]$. If $S=\emptyset$, then we
push $\overline{e}(v_{i},v_{j})$ into $S$. Otherwise, let $\overline{e}$ be
the shortcut at the top of $S$. If $\overline{e}$ and
$\overline{e}(v_{i},v_{j})$ do not dominate each other, then we push
$\overline{e}(v_{i},v_{j})$ into $S$. Otherwise, if $\overline{e}$ dominates
$\overline{e}(v_{i},v_{j})$, then we proceed on $j+1$, i.e.,
$\overline{e}(v_{i},v_{j})$ is pruned. If $\overline{e}(v_{i},v_{j})$
dominates $\overline{e}$, then we pop $\overline{e}$ out of $S$ (i.e.,
$\overline{e}$ is pruned). Next, we keep popping the top element out of $S$
until either $S$ becomes $\emptyset$ or $\overline{e}(v_{i},v_{j})$ does not
dominate it; in either case we push $\overline{e}(v_{i},v_{j})$ into $S$.

As the lengths of the shortcuts of $S_{i}$ are available, the algorithm runs
in $O(n)$ time. The following lemma proves the correctness of the algorithm.

######  Lemma 3.10.

After the algorithm, no two shortcuts of $S$ dominate each other and $S$
contains at least one optimal $v_{i}$-shortcut.

######  Proof 3.11.

We first prove the following observation, which will be used for proving the
lemma.

#### Observation.

Consider any three indices $j$, $k$, and $h$ with $i<j<k<h\leq m$.

  1. 1.

If $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{k})$, and
$\overline{e}(v_{i},v_{k})$ dominates $\overline{e}(v_{i},v_{h})$, then
$\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{h})$.

  2. 2.

If $\overline{e}(v_{i},v_{j})$ and $\overline{e}(v_{i},v_{k})$ do not dominate
each other, and $\overline{e}(v_{i},v_{k})$ and $\overline{e}(v_{i},v_{h})$ do
not dominate each other, then $\overline{e}(v_{i},v_{j})$ and
$\overline{e}(v_{i},v_{h})$ do not dominate each other.

#### Proof of the observation.

Since $i<j<k<h$, $d_{P}(v_{j},v_{k})+d_{P}(v_{k},v_{h})=d_{P}(v_{j},v_{h})$.

  1. 1.

If $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{k})$, and
$\overline{e}(v_{i},v_{k})$ dominates $\overline{e}(v_{i},v_{h})$, then we
have

$\displaystyle|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{h})$
$\displaystyle=|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{k})+d_{P}(v_{k},v_{h})$
$\displaystyle\leq|\overline{e}(v_{i},v_{k})|+d_{P}(v_{k},v_{h})\leq|\overline{e}(v_{i},v_{h})|.$

Hence, $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}(v_{i},v_{h})$.

  2. 2.

If $\overline{e}(v_{i},v_{j})$ and $\overline{e}(v_{i},v_{k})$ do not dominate
each other, and $\overline{e}(v_{i},v_{k})$ and $\overline{e}(v_{i},v_{h})$ do
not dominate each other, then we have

$\displaystyle|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{h})$
$\displaystyle=|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{k})+d_{P}(v_{k},v_{h})$
$\displaystyle>|\overline{e}(v_{i},v_{k})|+d_{P}(v_{k},v_{h})>|\overline{e}(v_{i},v_{h})|.$

Hence, $e(v_{i},v_{j})$ does not dominate $e(v_{i},v_{h})$.

$\displaystyle|\overline{e}(v_{i},v_{h})|+d_{P}(v_{j},v_{h})$
$\displaystyle=|\overline{e}(v_{i},v_{h})|+d_{P}(v_{k},v_{h})+d_{P}(v_{j},v_{k})$
$\displaystyle>|\overline{e}(v_{i},v_{k})|+d_{P}(v_{j},v_{k})>|\overline{e}(v_{i},v_{j})|.$

Hence, $\overline{e}(v_{i},v_{h})$ does not dominate $e(v_{i},v_{j})$.

Therefore, $\overline{e}(v_{i},v_{j})$ and $\overline{e}(v_{i},v_{h})$ do not
dominate each other.

This proves the observation.

We are now in a position to prove the lemma.

We first show that no two shortcuts in $S$ dominate each other by mathematical
induction. Initially the statement holds, for $S=\emptyset$. We assume that
the statement holds right before $\overline{e}(v_{i},v_{j})$ is processed. Let
$S$ refer to the stack right before $\overline{e}(v_{i},v_{j})$ is processed;
let $\overline{e}$ be the shortcut at the top of $S$ if $S\neq\emptyset$.
According to our algorithm, $\overline{e}(v_{i},v_{j})$ is pushed into $S$ in
the following cases.

  1. 1.

$S=\emptyset$. In this case, $S$ has only one shortcut after
$\overline{e}(v_{i},v_{j})$ is pushed in. Hence, the statement trivially
holds.

  2. 2.

$S\neq\emptyset$, and $\overline{e}$ and $\overline{e}(v_{i},v_{j})$ do not
dominate each other. Let $\overline{e}^{\prime}$ be any shortcut in $S$. To
prove the statement holds on $S$ after $\overline{e}(v_{i},v_{j})$ is pushed
in, it suffices to show that $\overline{e}^{\prime}$ and
$\overline{e}(v_{i},v_{j})$ do not dominate each other. If
$\overline{e}^{\prime}=\overline{e}$, then this is obviously true. Otherwise,
by the induction hypothesis, $\overline{e}^{\prime}$ and $\overline{e}$ do not
dominate each other. As $\overline{e}$ and $\overline{e}(v_{i},v_{j})$ do not
dominate each other, by the above Observation, $\overline{e}^{\prime}$ and
$\overline{e}(v_{i},v_{j})$ do not dominate each other.

  3. 3.

$S\neq\emptyset$, and $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}$. In
this case, $\overline{e}$ is popped out of $S$, and afterwards, the algorithm
keeps popping out the top element of $S$ until either $S$ becomes $\emptyset$
or $e(v_{i},v_{j})$ does not dominate the current top element of $S$, denoted
by $\overline{e}^{\prime\prime}$. In the former case, the statement trivially
holds. In the latter case, we claim that $\overline{e}^{\prime\prime}$ does
not dominate $\overline{e}(v_{i},v_{j})$. Indeed, by the induction hypothesis,
$\overline{e}$ and $\overline{e}^{\prime\prime}$ do not dominate each other.
Since $\overline{e}(v_{i},v_{j})$ dominates $\overline{e}$,
$\overline{e}^{\prime\prime}$ cannot dominate $\overline{e}(v_{i},v_{j})$
since otherwise $\overline{e}^{\prime\prime}$ would dominate $\overline{e}$ by
the above Observation. Then, following the same argument as the above case,
$\overline{e}(v_{i},v_{j})$ and $\overline{e}^{\prime}$ do not dominate each
other for any $e^{\prime}$ in the current stack $S$. The statement thus holds
after $\overline{e}(v_{i},v_{j})$ is pushed into $S$.

This proves that no two shortcuts in $S$ dominate each other.

We next show that $S$ contains at least one optimal $v_{i}$-shortcut. Let
$\overline{e}^{*}$ be an optimal $v_{i}$-shortcut. If $\overline{e}^{*}$ is in
$S$, then we are done with the proof. Otherwise, according to our algorithm,
$\overline{e}^{*}$ must be dominated by another shortcut $\overline{e}$ of
$S_{i}$. By Lemma 3.8, $\overline{e}$ is also an optimal $v_{i}$-shortcut. If
$\overline{e}$ is in $S$, then we are done with the proof. Otherwise, we can
inductively show that $S$ contains an optimal $v_{i}$-shortcut.

This completes the proof of the lemma.

Using the algorithm for Theorem 2.12 as a subroutine, the following lemma
provides a binary search algorithm that finds an optimal $v_{i}$-shortcut from
$S$ in $O(n\log n)$ time and $O(n)$ space.

######  Lemma 3.12.

An optimal $v_{i}$-shortcut in $S$ can be found in $O(n\log n)$ time and
$O(n)$ space.

######  Proof 3.13.

We first prove some properties that our algorithm relies on.

Consider the graph $P+\overline{e}(v_{i},v_{j})$ for an index $j$ with
$i<j\leq m$. By slightly abusing the notation, let
$\Delta(i,j)=\Delta(P+\overline{e}(v_{i},v_{j}))$. Suppose $(v_{a},v_{b})$ is
a diametral pair of $P+\overline{e}(v_{i},v_{j})$ with $a<b$. Then,
$\Delta(i,j)=w(v_{a})+d_{P+\overline{e}(v_{i},v_{j})}(v_{a},v_{b})+w(v_{b})$.

We claim that if $a\in(1,i]$, then $(v_{1},v_{b})$ is also a diametral pair.
Indeed, since $a\neq 1$, by Lemma 3.1 and the definition of $w(v_{a})$, we
have $w(v_{a})\leq d_{P}(v_{1},v_{a})$. Hence, we can derive

$\displaystyle w(v_{a})+d_{P+\overline{e}(v_{i},v_{j})}(v_{a},v_{b})+w(v_{b})$
$\displaystyle\leq
d_{P}(v_{1},v_{a})+d_{P+\overline{e}(v_{i},v_{j})}(v_{a},v_{b})+w(v_{b})$
$\displaystyle=d_{P+\overline{e}(v_{i},v_{j})}(v_{1},v_{b})+w(v_{b})$
$\displaystyle\leq
w(v_{1})+d_{P+\overline{e}(v_{i},v_{j})}(v_{1},v_{b})+w(v_{b}).$

Hence, $(v_{1},v_{b})$ is also a diametral pair.

Similarly, we claim that if $b\in[j,m)$, then $(v_{a},v_{m})$ is also a
diametral pair. The claim can be proved by a similar argument as above.

Note that since $a<b$, $a\neq m$ and $b\neq 1$. Due to the above two claims,
we assume that $a\in\\{1\\}\cup(i,m)$ and $b\in(1,j)\cup\\{m\\}$. Based on the
values of $a$ and $b$, we define the following five functions (e.g., see Fig.
14).

(a)

(b)

(c)

(d)

(e)

Figure 14: (a) $\alpha(i,j)$ is the distance between $v_{1}$ and $v_{m}$. (b)
$\beta(i,j)$ is the maximum distance between $v_{1}$ and all vertices on
$(i,j)$. (c) $\gamma(i,j)$ is the maximum distance between $v_{m}$ and all
vertices on $(i,m)$. (d) $\delta(i,j)$ is the maximum distance between two
vertices on $(i,j)$. (e) $\lambda(i,j)$ is the maximum distance between
$v_{1}$ and all vertices on $(1,i]$.

  1. 1.

For the case $a=1$ and $b=m$, we define

$\displaystyle\alpha(i,j)=w(v_{1})+d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m})+w(v_{m}).$

Hence, if $a=1$ and $b=m$, we have $\Delta(i,j)=\alpha(i,j)$.

  2. 2.

For the case $a=1$ and $b\in(i,j)$, we define

$\displaystyle\beta(i,j)=w(v_{1})+\max_{i<b^{\prime}<j}\bigg{\\{}\min\\{d_{P}(v_{1},v_{b^{\prime}}),d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{b^{\prime}})+w(v_{b^{\prime}})\\}\bigg{\\}}.$

Hence, if $a=1$ and $b\in(i,j)$, we have $\Delta(i,j)=\beta(i,j)$.

  3. 3.

For the case $a\in(i,m)$ and $b=m$, we define

$\displaystyle\gamma(i,j)=\max_{i<a^{\prime}<m}\bigg{\\{}w(v_{a^{\prime}})+d_{P+\overline{e}(v_{i},v_{j})}(v_{a^{\prime}},v_{m})\bigg{\\}}+w(v_{m}).$

Note that $d_{P+\overline{e}(v_{i},v_{j})}(v_{a^{\prime}},v_{m})$ is equal to
$\min\\{d_{P}(v_{a^{\prime}},v_{m}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m})\\}$
if $a^{\prime}\in(i,j)$, and $d_{P}(v_{a^{\prime}},v_{m})$ otherwise.

Hence, if $a\in(i,m)$ and $b=m$, we have $\Delta(i,j)=\gamma(i,j)$.

  4. 4.

For the case $i<a<b<j$, we define

$\displaystyle\delta(i,j)=\max_{i<a^{\prime}<b^{\prime}<j}\bigg{\\{}w(v_{a^{\prime}})+\min\\{d_{P}(v_{a^{\prime}},v_{b^{\prime}}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{b^{\prime}})\\}+w(v_{b^{\prime}})\bigg{\\}}.$

Hence, if $a,b\in(i,j)$, we have $\Delta(i,j)=\delta(i,j)$.

  5. 5.

For the case $a=1$ and $b\in(1,i]$, we define

$\displaystyle\lambda(i,j)=\max_{1<b^{\prime}\leq
i}\bigg{\\{}w(v_{1})+d_{P}(v_{1},v_{b^{\prime}})+w(v_{b^{\prime}})\bigg{\\}}.$

Hence, if $a=1$ and $b\in(1,i]$, we have $\Delta(i,j)=\lambda(i,j)$.

With the above definitions, we have

$\Delta(i,j)=\max\\{\alpha(i,j),\beta(i,j),\gamma(i,j),\delta(i,j),\lambda(i,j)\\}.$

Hence, if $j$ changes in $[i+1,m]$, the graph of $\Delta(i,j)$ is the upper
envelope of the graphs of the five functions.

Recall that our goal is to find an optimal $v_{i}$-shortcut in $S$. Let $I$
denote the set of the indices $j$ of all shortcuts $\overline{e}(v_{i},v_{j})$
of $S$. We consider these indices of $I$ in order. We intend to show that
$\Delta(i,j)$ is a unimodal function (first decreases and then increases) as
$j$ changes in $I$. To this end, we prove that each of the above five
functions is a monotonically increasing or decreasing function as $j$ changes
in $I$. Note that each index of $I$ is in $[i+1,m]$. To simplify the notation,
we simply let $I=\\{i+1,i+2,\ldots,m\\}$, or equivalently, one may consider
that our pruning algorithm does not prune any shortcut from $S_{i}$ and thus
$S=S_{i}$.

As no two shortcuts of $S$ dominate each other, $\overline{e}(v_{i},v_{j})$
and $\overline{e}(v_{i},v_{j+1})$ do not dominate each other for any
$j\in(i,m)$, i.e.,
$|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{j+1})>|\overline{e}(v_{i},v_{j+1})|$
and
$|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j},v_{j+1})>|\overline{e}(v_{i},v_{j})|$.
Relying on this property, we prove monotonicity properties of the five
functions as follows. Consider any index $j\in(i,m)$.

  1. 1.

$\alpha(i,j)>\alpha(i,j+1)$.

Proof:

$\displaystyle\alpha(i,j+1)$
$\displaystyle=w(v_{1})+d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{m})+w(v_{m})$
$\displaystyle<w(v_{1})+d_{P}(v_{1},v_{i})+\overline{e}(v_{i},v_{j})+d_{P}(v_{j},v_{j+1})+d_{P}(v_{j+1},v_{m})+w(v_{m})$
$\displaystyle=w(v_{1})+d_{P}(v_{1},v_{i})+\overline{e}(v_{i},v_{j})+d_{P}(v_{j},v_{m})+w(v_{m})$
$\displaystyle=\alpha(i,j).$

Hence, $\alpha(i,j)$ is monotonically decreasing as $j$ increases.

  2. 2.

$\beta(i,j)\leq\beta(i,j+1)$.

Proof:  For each $b^{\prime}\in(i,j)$, we have

$\displaystyle\min\\{d_{P}(v_{1},v_{b^{\prime}}),d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{b^{\prime}})\\}$
$\displaystyle\leq\min\\{d_{P}(v_{1},v_{b^{\prime}}),d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{j})+d_{P}(v_{j},v_{b^{\prime}})\\}$
$\displaystyle=\min\\{d_{P}(v_{1},v_{b^{\prime}}),d_{P}(v_{1},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{b^{\prime}})\\}.$

Hence, $\beta(i,j)\leq\beta(i,j+1)$ holds and $\beta(i,j)$ is monotonically
increasing as $j$ increases.

  3. 3.

$\gamma(i,j)\geq\gamma(i,j+1)$.

Proof:

Let $a^{\prime}$ be the index such that
$\gamma(i,j+1)=w(v_{a^{\prime}})+d_{P+\overline{e}(v_{i},v_{j+1})}(v_{a^{\prime}},v_{m})+w(v_{m})$.
Depending on whether $a^{\prime}\in(i,j+1)$ or $a^{\prime}\in[j+1,m)$, there
are two cases.

     * •

If $a^{\prime}\in[j+1,m)$, then

$\displaystyle\gamma(i,j+1)=w(v_{a^{\prime}})+d_{P}(v_{a^{\prime}},v_{m})+w(v_{m}).$

On the other hand,
$d_{P+\overline{e}(v_{i},v_{j})}(v_{a^{\prime}},v_{m})=d_{P}(v_{a^{\prime}},v_{m})$.
Hence, $\gamma(i,j)\geq
w(v_{a^{\prime}})+d_{P}(v_{a^{\prime}},v_{m})+w(v_{m})=\gamma(i,j+1)$.

     * •

If $a^{\prime}\in(i,j+1)$, then

$\displaystyle\gamma(i,j+1)=w(v_{a^{\prime}})+\min\\{d_{P}(v_{a^{\prime}},v_{m}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{m})\\}+w(v_{m}).$

Since $\overline{e}(v_{i},v_{j})$ and $\overline{e}(v_{i},v_{j+1})$ do not
dominate each other, we have

$\displaystyle
d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{m})$
$\displaystyle<d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{j+1})+d_{P}(v_{j+1},v_{m})$
$\displaystyle=d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m}).$

Hence,

$\displaystyle\gamma(i,j+1)$ $\displaystyle\leq
w(v_{a^{\prime}})+\min\\{d_{P}(v_{a^{\prime}},v_{m}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m})\\}+w(v_{m}).$

If $a^{\prime}\in(i,j)$, then we have $\gamma(i,j)\geq
w(v_{a^{\prime}})+\min\\{d_{P}(v_{a^{\prime}},v_{m}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m})\\}+w(v_{m})\geq\gamma(i,j+1)$;
otherwise, $\gamma(i,j)\geq
w(v_{a^{\prime}})+d_{P}(v_{a^{\prime}},v_{m})+w(v_{m})\geq
w(v_{a^{\prime}})+\min\\{d_{P}(v_{a^{\prime}},v_{m}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{m})\\}+w(v_{m})\geq\gamma(i,j+1)$.
As such, in either case $\gamma(i,j)\geq\gamma(i,j+1)$ holds.

Hence, $\gamma(i,j)$ is monotonically decreasing as $j$ increases.

  4. 4.

$\delta(i,j)\leq\delta(i,j+1)$.

Proof:  For each $i<a^{\prime}<b^{\prime}<j$, we have,

$\displaystyle\min\\{d_{P}(v_{a^{\prime}},v_{b^{\prime}}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j})|+d_{P}(v_{j},v_{b^{\prime}})\\}$
$\displaystyle\leq\min\\{d_{P}(v_{a^{\prime}},v_{b^{\prime}}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{j})+d_{P}(v_{j},v_{b^{\prime}})\\}$
$\displaystyle\leq\min\\{d_{P}(v_{a^{\prime}},v_{b^{\prime}}),d_{P}(v_{a^{\prime}},v_{i})+|\overline{e}(v_{i},v_{j+1})|+d_{P}(v_{j+1},v_{b^{\prime}})\\}.$

Hence, $\delta(i,j)\leq\delta(i,j+1)$ and $\delta(i,j)$ is monotonically
increasing as $j$ increases.

  5. 5.

$\lambda(i,j)=\lambda(i,j+1)$.

Proof:  By definition, $\lambda(i,j)$ is constant for all indices $j$. Thus,
$\lambda(i,j)=\lambda(i,j+1)$.

On the basis of the above monotonicity properties of the functions, we present
a binary search algorithm that finds an optimal $v_{i}$-shortcut in $O(n\log
n)$ time and $O(n)$ space.

Our algorithm performs binary search on the indices $[l,r]$, with $l=i+1$ and
$r=m$ initially. In each step, we decide whether we will proceed on $[k,r]$ or
on $[l,k]$, where $k=\lfloor\frac{l+r}{2}\rfloor$. To this end, we compute
$\Delta(i,k)$ and $\Delta(i,k+1)$. By Lemma 3.5,
$\Delta(i,k)=\Delta(T+e(x,y))$ where $(x,y)$ is a critical pair of $(i,k)$.
Since $T+e(x,y)$ is a unicycle graph, we compute $\Delta(T+e(x,y))$ in $O(n)$
time by Theorem 2.12. Therefore, $\Delta(i,k)$ can be computed in $O(n)$ time.
Note that the algorithm of Theorem 2.12 also returns a diametral pair for
$T+e(x,y)$, and we can decide which of the five cases for the functions
$\alpha$, $\beta$, $\gamma$, $\delta$, and $\lambda$ the diametral pair belong
to. We do the same for $\Delta(i,k+1)$. Assume that $\Delta(i,k)=f(i,k)$ and
$\Delta(i,k+1)=g(i,k+1)$, for two functions $f$ and $g$ in
$\\{\alpha,\beta,\gamma,\delta,\lambda\\}$. Then we have the following cases

  1. 1.

$f=g$. We have the following subcases.

     * •

$f=g\in\\{\beta,\delta\\}$. In this case, our algorithm proceeds on the
interval $[l,k]$. To see this, since both $\beta$ and $\delta$ are
monotonically increasing functions, we have $\Delta(i,j)\geq f(i,j)\geq
f(i,k)=\Delta(i,k)$, for any $j\in(k,r]$. As such, the diameter $\Delta(i,j)$
would increase if we proceed on $j\in(k,r]$.

     * •

$f=g\in\\{\alpha,\gamma\\}$. In this case, we proceed on the interval $[k,r]$
because both functions are monotonically decreasing.

     * •

$f=g=\lambda$. In this case, we stop the algorithm and return
$\overline{e}(i,k)$ as an optimal $v_{i}$-shortcut. To see this,
$\Delta(i,j)\geq\lambda(i,j)=\lambda(i,k)=\Delta(i,k)$ for any $j\in[l,r]$.
Hence, $\Delta(i,j)$ achieves the minimum at $j=k$ among all $j\in[l,r]$.

  2. 2.

$f\neq g$. We have the following subcases.

     * •

One of $f$ and $g$ is $\lambda$. In this case, by a similar argument as
before, we return $\overline{e}(v_{i},v_{k})$ as an optimal $v_{i}$-shortcut
if $f=\lambda$, and return $\overline{e}(v_{i},v_{k+1})$ as an optimal
$v_{i}$-shortcut if $g=\lambda$.

     * •

$\\{f,g\\}=\\{\beta,\delta\\}$. In this case, since both $\beta$ and $\delta$
are increasing functions, by a similar argument as before, we proceed on the
interval $[l,k]$.

     * •

$\\{f,g\\}=\\{\alpha,\gamma\\}$. In this case, since both $\alpha$ and
$\gamma$ are decreasing functions, by a similar argument as before, we proceed
on the interval $[k,r]$.

     * •

One of $f$ and $g$ is in $\\{\beta,\delta\\}$ and the other is in
$\\{\alpha,\gamma\\}$. In this case, one of $\overline{e}(v_{i},v_{k})$ and
$\overline{e}(v_{i},v_{k+1})$ is an optimal $v_{i}$-shortcut, which can be
determined by comparing $\Delta(i,k)$ with $\Delta(i,k+1)$. To see this,
without loss of generality, we assume that $f\in\\{\beta,\delta\\}$ and
$g\in\\{\alpha,\gamma\\}$. Hence, $\Delta(i,j)\geq f(i,j)\geq
f(i,k)=\Delta(i,k)$ for any $j\in[k+1,r]$, and $\Delta(i,j)\geq g(i,j)\geq
g(i,k+1)=\Delta(i,k+1)$ for any $j\in[l,k]$. As such,
$\min\\{\Delta(i,k),\Delta(i,k+1)\\}\leq\Delta(i,j)$ for all $j\in[l,r]$.

The algorithm will find an optimal $v_{i}$-shortcut in $O(\log n)$ iterations.
As each iteration takes $O(n)$ time, the total time of the algorithm is
$O(n\log n)$. The space is $O(n)$.

The proof of the following theorem summarizes our algorithm for the DOAT
problem.

######  Theorem 3.14.

The DOAT problem on the tree $T$ can be solved in $O(n^{2}\log n)$ time and
$O(n)$ space.

######  Proof 3.15.

We first compute a diametral path $P$ of $T$ as well as the weights $w(v_{i})$
for all vertices $v_{i}$ of $P$, which takes $O(n)$ time. Then, for each
$i\in[1,m-1]$, we compute an optimal $v_{i}$-shortcut
$\overline{e}(v_{i},v_{j(i)})$ and its diameter
$\Delta(P+\overline{e}(v_{i},v_{j(i)}))$ for the DOAP problem on the vertex-
weighted path $P$. To do so, we first compute the critical pairs of $(i,j)$
for all $j\in[i+1,m]$ and thus the lengths of the set $S_{i}$ of the shortcuts
$\overline{e}(v_{i},v_{j})$ for all $j\in[i+1,m]$. This step takes $O(n\cdot
n_{i})$ time and $O(n)$ space. Next, we run a pruning algorithm to prune those
shortcuts that are dominated by others from $S_{i}$ and obtain a subset $S$ of
$S_{i}$ such that no two shortcuts of $S$ dominate each other and $S$ contains
an optimal $v_{i}$-shortcut; this step takes $O(n)$ time.

After having $S$, by using the algorithm of Theorem 2.12 as a subroutine, a
binary search algorithm can find an optimal $v_{i}$-shortcut
$\overline{e}(v_{i},v_{j(i)})$ as well as the diameter
$\Delta(P+\overline{e}(v_{i},v_{j(i)})$. Recall that the critical pairs of
$(i,j)$ for all $j\in[i+1,m]$ have been computed. Let $(x_{i},y_{i})$ be the
critical pair of $(i,j(i))$. We store $(x_{i},y_{i})$ and
$\Delta(P+\overline{e}(v_{i},v_{j(i)})$. Other space used in this step will be
disregarded when we run the same algorithm to compute the optimal
$v_{i}$-shortcuts for other $i$’s; so the total space used in the algorithm is
bounded by $O(n)$. After the optimal $v_{i}$-shortcuts for all $i\in[1,m-1]$
are computed, we determine the index $i$ with minimum
$\Delta(P+\overline{e}(v_{i},v_{j(i)})$ and return $e(x_{i},y_{i})$ as the
optimal shortcut for the DOAT problem on $T$ and return
$\Delta(P+\overline{e}(i,j(i))$ as the diameter. It takes $O(n\cdot
n_{i}+n\log n)$ time and $O(n)$ space to compute an optimal $v_{i}$-shortcut
for each $i\in[1,m-1]$. Hence, computing optimal $v_{i}$-shortcuts for all
$i\in[1,m-1]$ takes $O(n^{2}\log n)$ time in total, for
$\sum_{i=1}^{m}n_{i}=n$. The space is $O(n)$ because only constant space is
occupied (for storing $(x_{i},y_{i})$ and
$\Delta(P+\overline{e}(v_{i},v_{j(i)}))$) after an optimal $v_{i}$-shortcut is
computed for each $i$.

## References

  * [1] N. Alon, A. Gyárfás, and M. Ruszinkó.  Decreasing the diameter of bounded degree graphs.  Journal of Graph Theory, 35:161–172, 2000.
  * [2] S.W. Bae, M. de Berg, O. Cheong, J. Gudmundsson, and C. Levcopoulos.  Shortcuts for the circle.  Computational Geometry: Theory and Applications, 79:37–54, 2019\.
  * [3] D. Bilò.  Almost optimal algorithms for diameter-optimally augmenting trees.  In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC), pages 40:1–40:13, 2018.
  * [4] D. Bilò, Luciano Gualà, and Guido Proietti.  Improved approximability and non-approximability results for graph diameter decreasing problems.  Theoretical Computer Science, 417:12–22, 2012.
  * [5] J.-L. De Carufel, C. Grimm, A. Maheshwari, and M. Smid.  Minimizing the continuous diameter when augmenting paths and cycles with shortcuts.  In Proceedings of the 15th Scandinavian Workshop on Algorithm Theory, pages 27:1–27:14, 2016.
  * [6] J.-L. De Carufel, C. Grimm, S. Schirra, and M. Smid.  Minimizing the continuous diameter when augmenting a tree with a shortcut.  In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS), pages 301–312, 2017.
  * [7] V. Chepoi and Y. Vaxes.  Augmenting trees to meet biconnectivity and diameter constraints.  Algorithmica, 33(2):243–262, 2002.
  * [8] F.R.K. Chung and M.R. Garey.  Diameter bounds for altered graphs.  Journal of graph theory, 8(4):511–534, 1984.
  * [9] E.D. Demaine and M. Zadimoghaddam.  Minimizing the diameter of a network using shortcut edges.  In Proceedings of the 12th Scandinavian conference on Algorithm Theory (SWAT), pages 420–431, 2010.
  * [10] A.M. Farley and A. Proskurowski.  Computation of the center and diameter of outerplanar graphs.  Discrete Applied Mathematics, 2:185–191, 1980.
  * [11] G.N. Federickson.  Fast algorithms for shortest paths in planar graphs, with applications.  SIAM Journal on Computing, 16:1004–1022, 1987.
  * [12] F. Frati, S. Gaspers, J. Gudmundsson, and L. Mathieson.  Augmenting graphs to minimize the diameter.  Algorithmica, 72:995–1010, 2015.
  * [13] Y. Gao, D.R. Hare, and J. Nastos.  The parametric complexity of graph diameter augmentation.  Discrete Applied Mathematics, 161:1626–1631, 2013.
  * [14] U. Große, J. Gudmundsson, C. Knauer, M. Smid, and F. Stehn.  Fast algorithms for diameter-optimally augmenting paths.  In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming, pages 678–688, 2015.
  * [15] U. Große, J. Gudmundsson, C. Knauer, M. Smid, and F. Stehn.  Fast algorithms for diameter-optimally augmenting paths and trees.  arXiv:1607.05547, 2016.
  * [16] T. Ishii.  Augmenting outerplanar graphs to meet diameter requirements.  Journal of Graph Theory, 74(4):392–416, 2013.
  * [17] C. Johnson and H. Wang.  A linear-time algorithm for radius-optimally augmenting paths in a metric space.  In Proceedings of the 16th Algorithms and Data Structures Symposium (WADS), pages 466–480, 2019.
  * [18] C.-L. Li, S.T. McCormick, and D. Simchi-Levi.  On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems.  Operations Research Letters, 11:303–308, 1992.
  * [19] N. Megiddo.  Linear-time algorithms for linear programming in $R^{3}$ and related problems.  SIAM Journal on Computing, 12(4):759–776, 1983.
  * [20] E. Oh and H.-K. Ahn.  A near-optimal algorithm for finding an optimal shortcut of a tree.  In Proceedings of the 27th International Symposium on Algorithms and Computation (ISAAC), pages 59:1–59:12, 2016.
  * [21] S. Olariu.  A simple linear-time algorithm for computing the center of an interval graph.  International Journal of Computer Mathematics, 34:121–128, 1990\.
  * [22] A.A. Schoone, H.L. Bodlaender, and J. Van Leeuwen.  Diameter increase caused by edge deletion.  Journal of Graph Theory, 11:409–427, 1997.
  * [23] H. Wang.  An improved algorithm for diameter-optimally augmenting paths in a metric space.  Computational Geometry: Theory and Applications, 75:11–21, 2018\.
  * [24] H. Wang and Y. Zhao.  A linear-time algorithm for discrete radius optimally augmenting paths in a metric space.  In Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG), pages 174–180, 2020.
  * [25] R. Williams.  Faster all-pairs shortest paths via circuit complexity.  SIAM Journal on Computing, 47:1965–1985, 2018.


# Measurement of electroweak-boson production in Pb–Pb and p–Pb collisions at
the LHC with ALICE

for the ALICE collaboration
Laboratoire de Physique de Clermont, France
E-mail

###### Abstract:

Measurements of electroweak-bosons in heavy-ion collisions with ALICE are
reported. They are measured at large rapidities, via their (di)muonic decay: Z
$\rightarrow\mu^{+}\mu^{-}$ and W${}^{\pm}\rightarrow\mu^{\pm}\nu$. The Z
production and nuclear modification factor in Pb–Pb collisions at
$\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV are presented and compared to theoretical
predictions with or without nuclear modifications of the Parton Distribution
Functions. Measurements of electroweak-boson production in p–Pb collisions at
$\sqrt{s_{{}_{\rm NN}}}$ = 5.02 and 8.16 TeV are also presented and discussed.

##  1 Introduction

The study of the Quark-Gluon Plasma (QGP) [1] in heavy-ion collisions requires
a precise knowledge of the initial state of the system in order to disentangle
QGP-induced phenomena from other nuclear effects. In this regard, the weakly-
interacting Z and W± bosons, when detected through their leptonic decay
channels, provide a medium-blind reference that allows us to probe the
initial-state effects such as the nuclear modifications of the Parton
Distribution Functions (PDFs). The various sets of nuclear PDFs (nPDFs)
available are currently suffering from large uncertainties due to the lack of
experimental constraints in the $x$-range probed at the LHC [2].

Thanks to the high collision energies and luminosities delivered by the LHC,
the measurement of the production of electroweak bosons is now accessible in
heavy-ion collisions [3, 4, 5, 6, 7, 8, 9, 10]. The four main LHC experiments
have complementary kinematic coverages that give access to a wide range of
Bjorken-$x$ values (from $10^{-4}$ to almost unity) in a region of high
virtuality ($Q^{2}\sim M^{2}_{Z,W}$) where the nPDFs are poorly constrained by
other experiments.

##  2 Analysis and results

###  2.1 Procedure

The Z and W± bosons are detected in their (di)muonic decay channels from data
recorded with the ALICE muon spectrometer [11]. The spectrometer is a conical-
shape detector consisting of five stations of tracking chambers, two stations
of trigger chambers and a set of absorbers that shield the detector from
various background sources such as hadrons produced in the collision and the
products of interactions of large-$\eta$ primary particles with the beam-pipe.
A complete description of the ALICE detector can be found in [12]. The
spectrometer acceptance covers the pseudo-rapidity interval $-4<\eta<-2.5$,
corresponding to a rapidity acceptance in the range $2.5<y<4$ for Pb–Pb
collisions.111In the ALICE reference frame, the spectrometer covers negative
$\eta$. However, positive values are used when referring to $y$. In proton-
lead collisions, the proton and lead beams have different energies, the
nucleon-nucleon centre-of-mass is thus boosted with respect to the one in the
laboratory frame by $\Delta y=0.465$ in the direction of the proton beam. The
rapidity acceptance of the spectrometer is then $2.03<y_{cms}<3.53$
($-4.46<y_{cms}<-2.96$) in the p–going (Pb–going) direction, when the proton
(Pb) beam moves toward the spectrometer.

In the following, results from three different periods are presented. The
collision systems, energies in the centre-of-mass, integrated luminosities and
performed measurements are summarized in Table 1.

Collision system | Year | $\mathbf{\sqrt{s_{{}_{\rm\textbf{NN}}}}}$ | Luminosity | Analyses
---|---|---|---|---
p–Pb | 2013 | 5.02 TeV | 5.03 $\pm$ 0.18 nb-1 | Z, W±
Pb–p | 5.81 $\pm$ 0.20 nb-1
Pb–Pb | 2015 | 5.02 TeV |  $\sim$ 225 $\rm\mu$b-1 | Z
p–Pb | 2016 | 8.16 TeV | 8.47 $\pm$ 0.18 nb-1 | Z
Pb–p | 12.75 $\pm$ 0.25 nb-1
Table 1: Analyses performed in the different data taking periods.

In order to ensure the quality of the data sample, a selection is applied on
each muon track on the trigger-tracker matching (each track reconstructed in
the tracking chambers has to match a track segment in the trigger chambers),
the distance at the end of the front absorber and the product of the track
momentum to its distance of closest approach (i.e. the distance to the primary
vertex of the track extrapolated to the plane transverse to the beam axis and
containing the vertex itself). This aims at reducing the background noise by
removing tracks that are poorly reconstructed, crossing the high-Z material
part of the detector or not coming from the interaction vertex.

The W± candidates are extracted by fitting the single muon transverse momentum
distribution, starting at $p_{\rm T}^{\mu}>10$ GeV/$c$ to remove muons from
low-mass particles decay. The fit is performed using a combination of Monte-
Carlo templates to account for the various contributions. In the Z case, a
selection on the muon pseudo-rapidity ($-4<\eta_{\mu}<-2.5$) and transverse
momentum ($p_{\rm T}^{\mu}>20$ GeV/$c$) as well as on the dimuon invariant
mass ($60<m_{\mu\mu}<120$ GeV/$c^{2}$) leaves a nearly background-free sample
from which the Z signal is obtained by simply counting the number of opposite-
sign dimuons in the fiducial region defined by the selection.

Finally, the systematic uncertainties on the measurements are evaluated by
combining the systematics on the signal extraction, including its potential
contamination by background sources, the detector performances and the
simulations from which the acceptance $\times$ efficiency factor is estimated.

The strategies for the Z and W± analyses are described in more details in [3,
4].

###  2.2 Pb–Pb collisions

The measured Z yield, normalized to the average nuclear overlap function
$\left<T_{AA}\right>$ obtained from the Glauber model [13], is displayed in
the left panel of Figure 1, for a collision centrality in the $0-90\%$ range
and integrated in rapidity ($2.5<y<4$). The measurement is compared to several
predictions, from free-PDF only, using CT14 [14], or using three different
parametrizations for the nuclear modification of the PDFs: EPS09 [15], EPPS16
[16] (both with CT14 as baseline PDF) or nCTEQ15 [17, 18]. Calculations using
the free-PDF set alone are found to overestimate the measured yield by
$2.3\sigma$, while the predictions from nPDFs are all in agreement with the
measurement within uncertainties.

Figure 1: Left: Z yield in Pb–Pb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02
TeV, divided by the average nuclear overlap function, in the rapidity region
$2.5<y<4$ and a $0-90\%$ collision centrality, compared to predictions from
free-PDF and various nPDFs. The horizontal bar and boxes correspond to the
statistical and model uncertainties, while the filled band indicates the
systematic uncertainty of the experimental value. Right: Centrality dependence
of the Z nuclear modification factor. The vertical bars represent the
statistical uncertainty, while the boxes represent the systematic uncertainty
on the measurements. The filled box located at $R_{AA}=1$ shows the
normalisation uncertainty. See text for details about the models.

Figure 1 (right) shows the centrality dependence of the Z nuclear modification
factor $R_{AA}$, compared to calculations including a centrality-dependent
nuclear modification of the PDFs. The nuclear modification factor is defined
as the ratio of the yield in Pb–Pb collisions to the cross section in p–p
collisions scaled by the average nuclear overlap function:

$R_{AA}=\frac{1}{\left<T_{AA}\right>}\frac{\mbox{d}N_{AA}/\mbox{d}y}{\mbox{d}\sigma_{pp}/\mbox{d}y}.$
(1)

A significant deviation by $3\sigma$ from unity is observed for the 20% most
central collisions. Theoretical calculations including the nuclear
modifications of the PDFs are found to reproduce the measured ratio within
uncertainties.

###  2.3 p–Pb collisions

Figure 2 (left) shows the Z production cross sections measured in p–Pb and
Pb–p collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV. They are compared to
theoretical calculations at NLO and NNLO, both with and without nuclear
modifications of the PDF. The NLO calculations are obtained from pQCD, using
CT10 [19] as free-PDF. The NNLO predictions are computed in the FEWZ [20]
framework with MSTW2008 [21] as baseline PDF. In both cases, the nuclear
modifications are implemented with EPS09 [15]. The ratios of the measured
cross sections to the predictions with nuclear modification are shown in the
middle (bottom) panel of the figure for NLO (NNLO) computations.

Figure 2 (right) presents the W lepton-charge asymmetry, a quantity that gives
access to the down over up quark ratio while allowing for a partial
cancellation of the uncertainties. It is compared to predictions obtained from
the same methods as for the Z cross section computation. The measurement-to-
theory ratio can be seen in the lowest panels of each figure.

Figure 2: Left: Z production as a function of rapidity in p–Pb collisions at
$\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV. The bars and boxes around the data points
correspond to statistical and systematic uncertainties respectively. The
horizontal width of the boxes indicates the measured rapidity range. The
measurements are compared to theoretical predictions, horizontally shifted for
readability. Right: W lepton charge asymmetry in p–Pb collisions at
$\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV compared to theoretical calculations, at
forward and backward rapidities. The statistical (systematic) uncertainties
are displayed as bars (boxes), the predictions are shifted horizontally for
readability. In both figures, the vertical middle (bottom) panels display the
ratio of the data and NLO (NNLO) calculations with nuclear modifications over
the NLO (NNLO) calculations from free-PDF only.

The effect of the nuclear modifications is smaller in p–Pb collisions than in
the Pb–Pb case. In addition, the measured yields are found to be smaller,
leading to a higher associated relative uncertainty. The combination of those
effects prevents any firm conclusion on nuclear effects, as the measured cross
sections and charge asymmetry are found to be consistent, within
uncertainties, with predictions both including and excluding nuclear
modifications.

A new preliminary cross section of the Z production has been measured in p–Pb
and Pb–p collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 8.16 TeV. The results are
displayed in Figure 3 (left) where they are compared to the 5.02 TeV
measurement. The same backward – forward asymmetry is observed, which results
from the change in Bjorken-$x$ induced by the rapidity shift. Figure 3 (right)
shows the measured cross sections, compared with theoretical calculations at
NLO, with and without including nuclear effects. The predictions with nuclear
modifications are calculated using the two most recents nPDFs available,
EPPS16 [16], using CT14 [14] as baseline PDF, and nCTEQ15 [17]. Within
uncertainties, the measurements are reproduced with and without nuclear
modifications of the PDFs.

Figure 3: Z production cross section as a function of rapidity in p–Pb
collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 8.16 TeV, compared to the measured
production at 5.02 TeV (left panel) and theoretical calculations (right
panel). The bars and boxes around the data points correspond to statistical
and systematic uncertainties respectively. The theoretical points are
horizontally shifted for readability, the close (open) symbols correspond to
predictions with (without) nuclear modification of the PDF.

##  3 Conclusion

The electroweak-boson measurements performed by the ALICE collaboration have
been presented. In Pb–Pb at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV, the measured
Z production is well reproduced by theoretical calculations including nuclear
modifications of the PDFs, while a significant deviation is found from free-
PDF predictions, by $2.3\sigma$ for the centrality-integrated yield. In p–Pb
collisions, at centre-of-mass energies of 5.02 and 8.16 TeV, the measurements
are well reproduced by calculations but the statistical limitations an the
small magnitude of nuclear effects prevent any firm conclusion to be drawn on
nuclear modifications. Further measurements with better precision are needed
to provide more stringent constraints on the nPDFs.

## References

  * [1] R. Pasechnik and M. Sumbera, _Phenomenological Review on Quark-Gluon Plasma: Concepts vs. Observations_ , _Universe_ 3 (2017) 7 [arXiv:1611.01533].
  * [2] H. Paukkunen and C. Salgado, _Constraints for the nuclear parton distributions from $Z$ and $W$ production at the LHC_, _Journal of High Energy Physics_ 2011 (2011) 71 [arXiv:1010.5392].
  * [3] ALICE Collaboration, _Measurement of $Z^{0}$-boson production at large rapidities in Pb–Pb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV_, _Physics Letters B_ 780 (2018) 372  [arXiv:1711.10753].
  * [4] ALICE Collaboration, _W and Z boson production in p-Pb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV_, _Journal of High Energy Physics_ 2017 (2017) 77 [arXiv:1611.03002].
  * [5] ATLAS Collaboration, _Measurement of $Z$ boson production in Pb+Pb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 2.76 TeV with the ATLAS detector_, _Physical Review Letters_ 110 (2013) 022301 [arXiv:1210.6486].
  * [6] ATLAS Collaboration, _$Z$ boson production in p+Pb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV measured with the ATLAS detector_, _Physical Review C_ 92 (2015) 044915 [arXiv:1507.06232].
  * [7] LHCb Collaboration, _Observation of $Z$ production in proton-lead collisions at LHCb_, _Journal of High Energy Physics_ 2014 (2014) 30 [arXiv:1406.2885].
  * [8] CMS Collaboration, _Study of $W$ boson production in PbPb and pp collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 2.76 TeV_, _Physics Letters B_ 715 (2012) 66  [arXiv:1205.6334].
  * [9] CMS Collaboration, _Study of $Z$ production in PbPb and pp collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 2.76 TeV in the dimuon and dielectron channels_, _Journal of High Energy Physics_ 2015 (2015) 22 [arXiv:1410.4825].
  * [10] CMS Collaboration, _Study of $Z$ boson production in pPb collisions at $\sqrt{s_{{}_{\rm NN}}}$ = 5.02 TeV_, _Physics Letters B_ 759 (2016) 36  [arXiv:1512.06461].
  * [11] ALICE Collaboration, _ALICE dimuon forward spectrometer: Technical Design Report_ , Tech. Rep. CERN-LHCC-99-022, CERN, 1999.
  * [12] ALICE Collaboration, _The ALICE experiment at the CERN LHC_ , _Journal of Instrumentation_ 3 (2008) S08002.
  * [13] M. L. Miller, K. Reygers, S. Sanders and P. Steinberg, _Glauber Modeling in High Energy Nuclear Collisions_ , _Annual Review of Nuclear and Particle Science_ 57 (2007) 205 [arXiv:nucl-ex/0701025].
  * [14] S. Dulat, T. J. Hou, J. Gao, M. Guzzi, J. Huston, P. Nadolsky et al., _New parton distribution functions from a global analysis of quantum chromodynamics_ , _Physical Review D_ 93 (2016) 033006 [arXiv:1506.07443].
  * [15] K. J. Eskola, H. Paukkunen and C. A. Salgado, _EPS09 - a New Generation of NLO and LO Nuclear Parton Distribution Functions_ , _Journal of High Energy Physics_ 2009 (2009) 65 [arXiv:0902.4154].
  * [16] K. J. Eskola, P. Paakkinen, H. Paukkunen and C. A. Salgado, _EPPS16: Nuclear parton distributions with LHC data_ , _The European Physical Journal C_ 77 (2017) 163 [arXiv:1612.05741].
  * [17] K. Kovarik, A. Kusina, T. Jezo, D. B. Clark, C. Keppel, F. Lyonnet et al., _nCTEQ15: Global analysis of nuclear parton distributions with uncertainties in the CTEQ framework_ , _Physical Review D_ 93 (2016) 085037 [arXiv:1509.00792].
  * [18] A. Kusina, F. Lyonnet, D. B. Clark, E. Godat, T. Jezo, K. Kovarik et al., _Vector boson production in proton-lead and lead-lead collisions at the LHC and its impact on nCTEQ15 PDFs_ , _The European Physical Journal C_ 77 (2017) 488 [arXiv:1610.02925].
  * [19] H.-L. Lai, M. Guzzi, J. Huston, Z. Li, P. M. Nadolsky, J. Pumplin et al., _New parton distributions for collider physics_ , _Physical Review D_ 82 (2010) 074024 [arXiv:1007.2241].
  * [20] R. Gavin, Y. Li, F. Petriello and S. Quackenbush, _FEWZ 2.0: A code for hadronic Z production at Next-to-Next-to-Leading-Order_ , _Computer Physics Communications_ 182 (2011) 2388  [arXiv:1011.3540].
  * [21] A. Martin, W. Stirling, R. Thorne and G. Watt, _Parton distributions for the LHC_ , _The European Physical Journal C_ 63 (2009) 189  [arXiv:0901.0002].