On the Minmax Regret Path Center Problem on Trees

Abstract

This paper studies the problem of finding the path center on a tree in which vertex weights are uncertain and the uncertainty is described by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. An O(n log n)-time algorithm is presented, improving the previous upper bound of O(n ²).

1 Introduction

The objective of a location problem is to decide the location of facilities in a network so as to minimize the communication or transportation costs [14, 15, 22, 24]. A network usually involves two types of parameters: weights of nodes and lengths of edges. Traditionally, the node weights and edge lengths of a network are assumed to be known precisely. In real transportation systems, the weights and lengths of a network may fluctuate or be inaccurate due to poor measurements. Thus, location models involving uncertainty have attracted significant research efforts [11, 12, 17, 23]. One of the most important ways for modeling network uncertainty is the minmax regret approach, introduced by Kouvelis and Yu [16]. In the model, uncertainty of network parameters is characterized by given intervals, and it is required to minimize the worst-case loss in the objective function that may occur because of the uncertain parameters.

Minmax regret location problems have received considerable attention in the past two decades. In network location theory, the shapes of facilities can be points, paths, or trees. Path- and tree-shaped facilities are called extensive facilities [18]. For point-shaped facility problems, most important ones have been studied comprehensively on the minmax regret model [3,4,5,6, 8, 9, 16, 31]. However, for extensive facility problems, there are only a few results on the minmax regret model, although there are considerable results on the classical model [7, 18, 20, 26,27,28]. In a breakthrough paper by Puerto et al. [21], polynomial algorithms were presented for the following three important path-shaped problems: the minmax regret path center, path median, and path centdian problems. Since these problems are NP-hard on general networks, their work was confined to trees. The time complexities of their algorithms are, respectively, O(n ²), O(n ⁴), and O(n ⁵ log n). In [29, 30] the upper bounds of the minmax regret path median and path centdian problems were improved to O(n ²) and O(n ⁴), respectively.

Contribution:

The focus of this paper is the minmax regret path center problem on trees. For this problem, Puerto et al.’s algorithm requires O(n ²) time. This paper presents an O(n log n)-time algorithm. The bottleneck of Puerto et al.’s algorithm is to compute the classical path centers of the given tree under n different settings of node weights. For each setting, their algorithm finds the classical path center in O(n) time. Our improvement is established on the following simple observation: the n settings of node weights are almost the same. Based on this observation, we preprocess the given tree in O(n log n) time to compute some useful auxiliary data structures; and then use the computed data structures to find the path center under each setting in O(log n) time.

Section 2 gives notation and definitions. Section 3 describes Puerto et al. algorithm [21] for finding a minmax regret path center of a tree. Section 4 presents efficient algorithms for a problem, called the entry vertex problem, and its extension. Then, using the algorithms in Sect. 4, Sect. 5 gives an improved O(n log n)-time algorithm.

2 Notation and Definitions

Let T = (V, E) be a tree, where V is the vertex set and E is the edge set. Let n = |V|. In this paper, T also denotes the set of all points of the tree. Thus, the notation x ∈ T means that x is a point along any edge of T, which may or may not be a vertex of T. Each edge e has a nonnegative length. For any two points p, q ∈ T, let P(p, q) be the unique path from p to q and d(p, q) be its length. Throughout this paper, we assume that T has been preprocessed so that d(p, q) can be answered in O(1) time for any p, q ∈ V. This preprocessing requires O(n) time [10]. For a subgraph X of T, the vertex set and edge set of X are, respectively, V(X) and E(X). For each vertex v ∈ V, the subgraph having a vertex set {v} is simply denoted by v. For any vertex v ∈ V and subgraph X of T, the distance from v to X, denoted by d(v, X), is the shortest distance from v to any point of X (i.e., d(v, X) = min _x∈X d(v, x)) and close(v, X) is the vertex or point in X nearest to v. A path in T is called a v-path, where v ∈ V, if v is one of its endpoints.

Each vertex v ∈ V is associated with an interval [$w_{v}^{ - }$, $w_{v}^{ + }$], where 0 ≤ $w_{v}^{ - }$ ≤ $w_{v}^{ + }$. The weight of each vertex v ∈ V can be any value in the interval [$w_{v}^{ - }$, $w_{v}^{ + }$]. Let Σ be the Cartesian product of intervals [$w_{v}^{ - }$, $w_{v}^{ + }$], where v ∈ V. Any element S ∈ Σ is called a scenario and represents a feasible assignment of weights to the vertices of T. For any scenario S ∈ Σ and any vertex v ∈ V, let $w_{v}^{S}$ be the weight of v under the scenario S.

Let S ∈ Σ be a scenario. For any two subgraphs X and Y of T, the eccentricity from X to Y under the scenario S is C ^S(X, Y) = max _v∈V(X) $w_{v}^{S}$ d(v, Y), which is the maximum weighted distance from any vertex in X to Y according to the scenario S. A path H that minimizes C ^S(T, H) is called a path center of T under the scenario S. The finding of a path center of T under a fixed scenario S is called the classical path center problem. We use π(S) to denote a path center of T under a scenario S.

For any path H in T, the regret of H with respect to a scenario S ∈ Σ is R ^S(H) = C ^S(T, H) − C ^S(T, π(S)) and the maximum regret of H is R ^*(H) = max _S∈Σ R ^S(H). The minmax regret path center problem is to determine a path H in T that minimizes R ^*(H). The determined path is called a minmax regret path center.

For ease of discussion, throughout this paper, we assume that each internal vertex of T has exactly three neighbors. In case this is not true, the given tree is transformed into an equivalent tree in linear time [13, 19]. Consider an internal vertex v ∈ V. There are three subtrees of T attached to v through the edges incident on v. For each (u, v) ∈ E, we denote by $T_{u}^{v}$ the subtree of T attached to v through the edge (u, v), excluding this edge and the vertex v. We define the subtrees of a path H to be the subtrees $T_{j}^{i}$ such that i is an internal node of H and j is the neighbor of i that is not on H. For any p, q ∈ V, define subtree(p, q) to be the union of the subtrees of P(p, q) (see Fig. 1). For ease of description, sometimes we will orient T into a rooted tree. In such a case, for each node v ∈ V, we use p(v) and sib(v) to denote, respectively, its parent and sibling, and use T _v to denote the subtree of T rooted at v.

Fig. 1.

Subtree $T_{u}^{v}$ and subtree(p, q).

3 Puerto, Ricca, and Scozzari’s Algorithm

Puerto et al. [21] had an O(n ²)-time algorithm for finding a minmax regret path center of a tree. This section reviews their algorithm.

Recall that π(S) denotes a path center of T under a scenario S. For any scenario S ∈ Σ, let α(S) = C ^S(T, π(S)). For each i ∈ V, let S _i be the scenario in which the weight of vertex i is $w_{i}^{ + }$ and the weight of any other vertex v is $w_{v}^{ - }$. Based on an augmented tree approach introduced by Averbakh and Berman [3], Puerto, Ricca, and Scozzari solved the minmax regret path center problem by an elegant transformation to the classical path center problem. Define an auxiliary tree T′ as follows. Let M be a number that is larger than α(S _i ) for any i ∈ V. The tree T′ is obtained from T by appending to each vertex i ∈ V a vertex i′ and an edge (i, i′) with length (M − α(S _i ))/$w_{i}^{ + }$. Specific weights are assigned to the vertices of T′. For each i ∈ V, the weight of i is zero and the weight of i′ is $w_{i}^{ + }$. Let P be a path in the auxiliary tree T′. The restriction of P to T is the path obtained from P by deleting the edges of P that are not in T. Puerto, Ricca, and Scozzari gave the following nice property for solving the minmax regret path center problem.

Lemma 1 [21].

Let P be a path center of T′. Then, the restriction of P to T is a minmax regret path center of T.

Based upon Lemma 1, Puerto, Ricca, and Scozzari solved the minmax regret path center problem in O(n ²) time as follows. First, α(S _i ) is computed for each i ∈ V. By using the linear-time algorithm in [7] for the classical path center problem on a tree, this step is done in O(n ²) time. Next, the auxiliary tree T′ is constructed, which requires O(n) time. Finally, a solution is obtained by applying the algorithm in [7] again to T′.

4 The Entry Vertex Problem

A rooted path center of a rooted tree with root r under a fixed scenario is an r-path H that minimizes the eccentricity from the tree to H. For a rooted path center, the endpoint other than the root is called its terminal, which may be a vertex or an interior point of an edge. A rooted tree may have more than one rooted path center. However, it is easy to see that the shortest one is unique and can be obtained as follows: initially set the terminal at the root and then continuously extend it toward a farthest vertex below it, until the extension does not decrease the eccentricity.

The entry vertex problem is defined as follows. Let T = (V, E) be a tree with a fixed scenario S. For any (u, v) ∈ E, let Q ^S($T_{u}^{v}$) be the shortest rooted path center of $T_{u}^{v}$ under the scenario S, where $T_{u}^{v}$ is considered as a rooted tree with root u. The entry vertex of a vertex x to a path H is the vertex on H nearest to x. For any (u, v) ∈ E and x ∈ V($T_{u}^{v}$), define Entry(x, $T_{u}^{v}$) to be a query that returns the entry vertex of x to the shortest rooted path center, Q ^S($T_{u}^{v}$), of $T_{u}^{v}$. (See Fig. 2) Note that Entry(x, $T_{u}^{v}$) may not be the same as close(x, Q ^S($T_{u}^{v}$)), since only vertices can be entry vertices. The entry vertex problem is to preprocess the tree T such that each Entry query can be answered efficiently.

Fig. 2.

Entry vertices to the shortest rooted path center of $T_{u}^{v}$.

This section shows that with an O(n log n)-time preprocessing, each Entry query can be answered in O(log n) time.

4.1 Preprocessing

A query Node(p, q, k), where p, q ∈ V and k is an integer, requests the k-th vertex on the path from p to q. For any two vertices p, q ∈ V and scenario S ∈ Σ, let M ^S(p, q) = C ^S(subtree(p, q), P(p, q)), which is the eccentricity of P(p, q) from its subtrees. We need the following two lemmas.

Lemma 2.

With an O(n)-time preprocessing, a query Node(p, q, k) can be answered in O(1) time for any p, q ∈ V and integer k.

Lemma 3.

Suppose that C ^S($T_{u}^{v}$, v) of all (u, v) ∈ E are given. Then, with an O(n)-time preprocessing, M ^S(p, q) can be computed in O(1) time for any p, q ∈ V.

Given a rooted tree in which each node is associated with a cost, a query lca(a, b) requests the least common ancestor of two vertices a, b; a query la(v, l) requests the level l ancestor of a vertex v, where the level of a vertex is the number of edges from it to the root; and a query Max(a, b) requests the largest cost of the vertices on a path P(a, b). It was shown in [1, 13] that after an O(n) time preprocessing, each lca, la, and Max query can be answered in O(1) time. Using these results, it is not difficult to prove the above two lemmas.

Using the divide-and-conquer approach, Tamir [25] gave an O(n log n)-time algorithm to compute C ^S(T, v) for all v ∈ V. Based on the same idea and the top tree data structure in [2], we can show the following.

Lemma 4.

The computation of C ^S($T_{u}^{v}$, v) for all (u, v) ∈ E can be done in O(n log n) time.

We proceed to describe the preprocessing algorithm. First, we compute C ^S($T_{u}^{v}$, v) for every (u, v) ∈ E. By Lemma 4, this step requires O(n log n) time. Next, by Lemmas 2 and 3, we preprocess T so that Node(p, q, k) and M ^S(p, q) can be obtained in O(1) time for any p, q ∈ V and integer k.

4.2 Algorithm for Queries

Consider a query Entry(x, $T_{u}^{v}$). For notational simplicity, in this section, we assume that $T_{u}^{v}$ is rooted at u. In addition, since the scenario S is fixed, we write C(·, ·), M(·, ·), and Q(·), respectively, for C ^S(·, ·), M ^S(·, ·), and Q ^S(·). Our query algorithm finds the answer in a binary search manner, mainly based upon the following.

Lemma 5.

A vertex i of $T_{u}^{v}$ is on the path Q($T_{u}^{v}$) if and only if C(T _i , i) ≥ M(v, i).

Proof.

Assume first that C(T _i , i) ≥ M(v, i). Consider an u-path H in $T_{u}^{v}$ not containing i. Since C($T_{u}^{v}$, H) ≥ C(T _i , H) > C(T _i , i) and C($T_{u}^{v}$, P(u, i)) = max{C(T _i , i), M(v, i)} = C(T _i , i), we have C($T_{u}^{v}$, H) > C($T_{u}^{v}$, P(u, i)). Thus, any u-path in $T_{u}^{v}$ not containing i is not a rooted path center. Therefore, the if-part holds.

Next, assume that i is a vertex on Q($T_{u}^{v}$). By contradiction, suppose that C(T _i , i) < M(v, i). Since Q($T_{u}^{v}$) passes through i, we have C(T _i , Q($T_{u}^{v}$)) ≤ C(T _i , i) < M(v, i). Therefore, C($T_{u}^{v}$, Q($T_{u}^{v}$)) = max{C(T _i , Q($T_{u}^{v}$)), M(v, i)} = M(v, i). Let t be any point of edge (i, p(i)) such that 0 < d(i, t) ≤ (M(v, i) − C(T _i , i))/w ^*, where w ^* is the largest weight in T _i . Consider the path P(u, t), which is shorter than Q($T_{u}^{v}$). Clearly, C(T _i , t) ≤ C(T _i , i) + d(i, t) × w ^* ≤ M(v, i). Since C(T _i , t) ≤ M(v, i), we have C($T_{u}^{v}$, P(u, t)) = max{C(T _i , t), M(v, i)} = M(v, i) = C($T_{u}^{v}$, Q($T_{u}^{v}$)), which contradicts that Q($T_{u}^{v}$) is the shortest rooted path center of $T_{u}^{v}$. Therefore, C(T _i , i) ≥ M(v, i). Consequently, the lemma holds. □

The entry vertex m = Entry(x, $T_{u}^{v}$) is found as follows. By definition, m is the first vertex on P(x, u) that is contained in Q($T_{u}^{v}$). All successors of m on P(x, u) are contained in Q($T_{u}^{v}$); and all predecessors of m on P(x, u) are not contained in Q($T_{u}^{v}$). Therefore, m can be identified by performing binary search on P(x, u). With the help of Node queries, any node on P(x, u) can be accessed in O(1) time. By Lemma 5, whether a vertex i is on Q($T_{u}^{v}$) can be checked in O(1) time by using the values of C(T _i , i) and M(v, i). After the preprocessing in Sect. 4.1, C(T _i , i) = max{C($T_{a}^{i}$, i), C($T_{b}^{i}$, i)} and M(v, i) can be computed in O(1) time for any vertex i in $T_{u}^{v}$, where a and b are the two children of i. Therefore, we have the following.

Theorem 1.

With an O(n log n)-time preprocessing, each Entry query can be answered in O(log n) time.

4.3 An Extended Problem

Our improvement on the minmax regret path center problem is based on solving an extended version of the entry vertex problem, in which it is allowed to temporarily increase the weight of a vertex during a query. For any i ∈ V and w ≥ $w_{i}^{S}$, we use S|(i, w) to denote the scenario obtained from S by increasing the weight of i to w. A query ExtendEntry(x, $T_{u}^{v}$, i, w) reports the entry vertex of x to the rooted path center of $T_{u}^{v}$ under the scenario S|(i, w), where (u, v) ∈ E, x ∈ V($T_{u}^{v}$), i ∈ V, and w ≥ $w_{i}^{S}$. That is, ExtendEntry(x, $T_{u}^{v}$, i, w) reports the entry vertex of x to the path Q ^{S|(i, w)}($T_{u}^{v}$). In the following, we show that after an O(n log n)-time preprocessing, each ExtendEntry query can also be answered in O(log n) time. Using the lca algorithm in [13], it is not difficult to prove the following lemma.

Lemma 6.

With an O(n)-time preprocessing, close(x, P(p, q)) can be computed in O(1) time for any three vertices p, q, x ∈ V.

Lemma 7.

With an O(n log n)-time preprocessing, C ^{S|(i, w)}($T_{u}^{v}$, v) and M ^{S|(i, w)}(p, q) can be computed in O(1) time for any i, p, q ∈ V, (u, v) ∈ E, and w ≥ $w_{i}^{S}$.

Proof.

As in Sect. 4.1, we preprocess T so that C ^S($T_{u}^{v}$, v) for any (u, v) ∈ E and M ^S(p, q) for any vertices p, q ∈ V can be computed in O(1) time. In addition, we preprocess T so that close(x, P(p, q)) can be accessed in O(1) time for any x, p, q ∈ V.

For any i ∈ V, (u, v) ∈ E, and w ≥ $w_{i}^{S}$, since S|(i, w) differs from S only in the weight of i, C ^{S|(i, w)}($T_{u}^{v}$, v) is computed in O(1) time as follows. First, determine whether i ∈ $T_{u}^{v}$ by checking whether close(i, P(u, v)) = u. Next, if i ∈ $T_{u}^{v}$, we set C ^{S|(i, w)}($T_{u}^{v}$, v) = max{C ^S($T_{u}^{v}$, v), w × d(i, v)}; otherwise, we set C ^{S|(i, w)}($T_{u}^{v}$, v) = C ^S($T_{u}^{v}$, v). For any i, p, q ∈ V, M ^{S|(i, w)}(p, q) is computed in O(1) time as follows. First, determine whether i is a vertex in subtree(p, q) or an internal node of P(p, q) by checking whether close(i, P(p, q)) ∉ {p, q}. Next, if i is a vertex in subtree(p, q) or an internal node of P(p, q), we set M ^{S|(i, w)}(p, q) = max{M ^S(p, q), w × d(i, close(i, P(p, q)))}; otherwise, we set M ^{S|(i, w)}(p, q) = M ^S(p, q). Consequently, the lemma holds. □

Consider a query ExtendEntry(x, $T_{u}^{v}$, i, w). According to the query algorithm in Sect. 4.2, to show that this query can be answered in O(log n) time, it suffices to show that C ^{S|(i, w)}($T_{u}^{v}$, v), M ^{S|(i, w)}(p, q), and Node(p, q, k) can be obtained in O(1) time for any i, p, q ∈ V, (u, v) ∈ E, and integer k. As a result, by combining Lemmas 2 and 7, we obtain the following.

Theorem 2.

Let T be a tree with a fixed scenario S. With an O(n log n)-time preprocessing, each ExtendEntry query can be answered in O(log n) time.

5 An Improved Algorithm for the Path Center Problem

The bottleneck of the algorithm in [21] is to compute α(S _i ) for every i ∈ V. Recall that for any scenario S ∈ Σ, α(S) denotes C ^S(T, π(S)) and for each i ∈ V, S _i denotes the scenario in which the weight of vertex i is $w_{i}^{ + }$ and the weight of any other vertex v is $w_{v}^{\text{ - }}$. In this section, we improve the upper bound of the minmax regret path center problem on a tree by showing that the computation of all α(S _i ) can be done in O(n log n) time.

Let $S^{ - }$ be the scenario in which the weight of every vertex v is $w_{v}^{ - }$. The scenario $S^{ - }$ differs from each S _i only in the weight of vertex i. Our idea is to preprocess T under the scenario $S^{ - }$, so that each α(S _i ) can be determined efficiently. Let M ^S(p, q) and Q ^S($T_{u}^{v}$) be defined the same as in Sect. 4. For any (u, v) ∈ E and scenario S, let λ^S($T_{u}^{v}$) = C ^S($T_{u}^{v}$, Q ^S($T_{u}^{v}$)), which is the eccentricity from $T_{u}^{v}$ to the rooted path center Q ^S($T_{u}^{v}$). For notational simplicity, in this section, $C^{{S^{ - } }} ( \cdot , \cdot ),C^{{S_{i} }} ( \cdot , \cdot ),M^{{S^{ - } }} ( \cdot , \cdot ),M^{{S_{i} }} ( \cdot , \cdot ),l^{{S^{ - } }} ( \cdot )$, and ${\rm{\lambda} }^{{S_{i} }}$(·) are simply denoted, respectively, by C ⁻(·, ·), C ⁱ(·, ·), M ⁻(·, ·), M ⁱ(·, ·), λ⁻(·), and λⁱ(·).

Lemma 8.

Suppose that C ⁻($T_{u}^{v}$, v) for all (u, v) ∈ E are given. In O(n) time, we can compute λ⁻($T_{u}^{v}$) for all edges (u, v) ∈ E.

Proof.

In this proof, we assume that T is under the scenario $S^{\text{ - }}$. We orient T into a rooted tree with an arbitrary root r. Since there always exists a rooted path center whose terminal is a leaf, using the dynamic programming approach, all λ⁻($T_{u}^{v}$) are computed in two phases.

• Phase 1. This phase computes λ⁻(T _x ) for all x ∈ V in a bottom-up manner as follows. If x is a leaf, we have λ⁻(T _x ) = 0. Assume that x is an internal vertex and let x ₁, x ₂ be its two children. Let H be a rooted path center of T _x . If H passes through x ₁, since λ⁻(T _x ) = C ⁻(T _x , H) = max{C ⁻(T _x1, H), C ⁻(T _x2, x)} and a rooted path center of T _x1 has the minimum eccentricity from T _x1 among all x ₁-paths, it can be concluded that λ⁻(T _x ) = max{λ⁻(T _x1), C ⁻(T _x2, x)}. Similarly, if H passes through x ₂, it can be concluded that λ⁻(T _x ) = max{C ⁻(T _x1, x), λ⁻(T _x2)}. Therefore, we compute λ⁻(T _x ) as min{max{λ⁻(T _x1), C ⁻(T _x2, x)}, max{C ⁻(T _x1, x), λ⁻(T _x2)}}.

• Phase 2. This phase computes λ⁻($T_{p(x)}^{x}$) for all x ∈ V in a top-down manner as follows. If x is the root r, we have λ⁻($T_{p(x)}^{x}$) = λ⁻(∅) = 0. Assume that x ≠ r. A rooted path center of $T_{p(x)}^{x}$ passes through either sib(x) or p(p(x)). If it passes through sib(x), we have λ⁻($T_{p(x)}^{x}$) = max{λ⁻(T _sib(x)), C ⁻($T_{p(p(x))}^{p(x)}$, p(x))}; otherwise, we have λ⁻($T_{p(x)}^{x}$) = max{C ⁻(T _sib(x), p(x)), λ⁻($T_{p(p(x))}^{p(x)}$, p(x))}. Therefore, λ⁻($T_{p(x)}^{x}$) can be computed in O(1) time.

The above computation requires O(n) time. Thus, the lemma holds. □

Lemma 9.

Suppose that the following can be accessed in O(1) time: λ⁻($T_{u}^{v}$) for any (u, v) ∈ E, C ⁱ($T_{u}^{v}$, v) for any (u, v) ∈ E and i ∈ V, and M ⁱ(p, q) for any i, p, q ∈ V; and suppose that the entry vertex of i to $Q^{{S_{i} }} (T_{u}^{v} )$ can be accessed in O (log n) time for any (u, v) ∈ E and i ∈ V. Then, λⁱ($T_{u}^{v}$) can be computed in O (log n) time for any (u, v) ∈ E and i ∈ V.

Proof.

We prove this lemma by presenting an algorithm. For ease of description, assume that $T_{u}^{v}$ is rooted at u and is under the scenario S _i . First, compute m as the entry vertex of i to $Q^{{S_{i} }} (T_{u}^{v} )$ in O (log n) time. Let m ₁, m ₂ be the two children of m. Next, in O(1) time, we find the values of C ⁱ(T _m1, m) and C ⁱ(T _m2, m). By symmetry, assume that C ⁱ(T _m1, m) ≥ C ⁱ(T _m2, m). We first establish the following claim.

Claim.

There is a rooted path center of $T_{u}^{v}$ (under S _i ) that passes through m ₁.

Proof of the Claim.

Let $P\left( {u,t} \right) = Q^{{S_{i} }} (T_{u}^{v} )$. Clearly, any u-path containing $Q^{{S_{i} }} (T_{u}^{v} )$ is a rooted path center. Thus, to prove this claim, we only need to show that the terminal t is a point of edge (m, m ₁) or is in T _m1. Since m is a vertex on $Q^{{S_{i} }} (T_{u}^{v} )$, $Q^{{S_{i} }} (T_{u}^{v} )$ can be obtained by initially setting the terminal t at m and then continuously extending it toward a farthest vertex below it, until the extension does not decrease the eccentricity. Since C ⁱ(T _m1, m) ≥ C ⁱ(T _m2, m), it is easy to conclude that at t = m an extension can decrease the eccentricity only if it is toward the vertex m ₁. Therefore, t is a point of edge (m, m ₁) or is in T _m1. Consequently, the claim follows.

We now complete the proof of the lemma. Let H be a rooted path center of $T_{u}^{v}$ that passes through m ₁. Two cases are discussed.

• Case 1: i ∈ V(T _m1).

  In this case, m ₁ is not on the shortest path center $Q^{{S_{i} }} (T_{u}^{v} )$. Otherwise, since m ₁ is closer to x than m, m is not the entry vertex of i to $Q^{{S_{i} }} (T_{u}^{v} )$. By Lemma 4, C ⁱ(T _m1, m ₁) < M ⁱ(v, m ₁). Since H passes through m ₁, we have C ⁱ(T _m1, H) ≤ C ⁱ(T _m1, m ₁) < M ⁱ(v, m ₁). Therefore, λⁱ($T_{u}^{v}$) = C ⁱ($T_{u}^{v}$, H) = max{C ⁱ(T _m1, H), C ⁱ(subtree(v, m ₁), H} = max{C ⁱ(T _m1, H), M ⁱ(v, m ₁)} = M ⁱ(v, m ₁). Consequently, in this case, we compute λⁱ($T_{u}^{v}$) = M ⁱ(v, m ₁) in O(1) time.

• Case 2: i ∉ V(T _m1).

  Since i ∉ V(T _m1), we have C ⁱ(T _m1, H) = C ⁻(T _m1, H) and thus C ⁱ($T_{u}^{v}$, H) = max{C ⁻(T _m1, H), M ⁱ(v, m ₁)}. Let H ^* be the union of P(u, m ₁) and Q ^S−(T _m1). Under S ⁻, the path Q ^S−(T _m1) has the minimum eccentricity from T _m1 among all m ₁-paths in T _m1. Consequently, it can be concluded that C ⁱ($T_{u}^{v}$, H ^*) = max{C ⁻(T _m1, H ^*), M ⁱ(v, m ₁)} ≤ C ⁱ($T_{u}^{v}$, H). Therefore, H ^* is also a rooted path center of T under S _i and thus λⁱ($T_{u}^{v}$) = max{C ⁻(T _m1, H ^*), M ⁱ(v, m ₁)} = max{λ⁻(T _m1), M ⁱ(v, m ₁)}. Consequently, in this case, we compute λⁱ($T_{u}^{v}$) = max{λ⁻(T _m1), M ⁱ(v, m ₁)} in O(1) time.

The above computation of λⁱ($T_{u}^{v}$) requires O (log n) time. Thus, the lemma holds. □

A discrete 1-center of T under a scenario S is a vertex v ∈ V that minimizes C ^S(T, v). Tamir et al. [26] gave the following.

Lemma 10 [26].

Let T be a tree with a fixed scenario and c be its discrete 1-center. Then, T has a path center that contains c.

We proceed to present an algorithm for computing α(S _i ) of all i ∈ V. Consider the computation for a fixed i ∈ V. Assume that T is under the scenario S _i . Let c be a discrete 1-center of T. By Lemma 10, there is a path center containing c. Let x, y, z be the three children of c. Without losing any generality, assume that C ⁱ($T_{x}^{c}$, c) ≥ C ⁱ($T_{y}^{c}$, c) ≥ C ⁱ($T_{z}^{c}$, c). Then, there exists a path center that passes through x and y [26]. For any path H passing through x and y, we have C ⁱ(T, H) = max{C ⁱ($T_{x}^{c}$, H), C ⁱ($T_{y}^{c}$, H), C ⁱ($T_{z}^{c}$, c)}. Let H ^* be the union of $Q^{{S_{i} }} (T_{x}^{c} )$, P(x, y), and $Q^{{S_{i} }} (T_{y}^{c} )$. The path $Q^{{S_{i} }} (T_{x}^{c} )$ has the minimum eccentricity from $T_{x}^{c}$ among all x-paths in $T_{x}^{c}$; and the path $Q^{{S_{i} }} (T_{y}^{c} )$ has the minimum eccentricity from $T_{y}^{c}$ among all y-paths in $T_{y}^{c}$. Consequently, it can be concluded that H ^* has the minimum eccentricity among all paths that pass through x and y. That is, H ^* is a path center of T. Therefore, α(S _i ) can be computed as C ⁱ(T, H ^*) = max{C ⁱ($T_{x}^{c}$, $Q^{{S_{i} }}$($T_{x}^{c}$)), C ⁱ($T_{y}^{c}$, $Q^{{S_{i} }}$($T_{y}^{c}$)), C ⁱ($T_{z}^{c}$, c)} = max{λⁱ($T_{x}^{c}$), λⁱ($T_{y}^{c}$), C ⁱ($T_{z}^{c}$, c)}.

Based upon the above discussion, an algorithm for computing all α(S _i ) is described as follows.

Since S _i  = S ⁻|(i, $w_{i}^{ + }$) for each i ∈ V, by using Lemmas 4 and 7 with S = S ⁻, Line 1 requires O(n log n) time. By definition, when T is under S ⁻, the entry vertex of x to $Q^{{S_{i} }} (T_{u}^{v} )$ is ExtendEntry(x, $T_{u}^{v}$, i, $w_{i}^{ + }$). Therefore, by using Theorem 2 with S = S ⁻, Line 2 requires O(n log n) time. By Lemma 8, Line 3 takes O(n) time. Yu et al. [31] showed that a discrete 1-center of T under S _i can be computed in O(n log n) time for every i ∈ V. Thus, Line 4 requires O(n log n) time. Consider the for-loop in Lines 5–11. Lines 7, 8, 10 take O(1) time. By Lemma 9, after the preprocessing in Lines 1, 2, and 3, the computation of λⁱ($T_{x}^{c}$) and λⁱ($T_{y}^{c}$) in Line 9 can be done in O (log n) time. Therefore, each iteration of the for-loop requires O (log n) time. As a result, we obtain the following.

Lemma 11.

We can compute α(S _i ) for all i ∈ V in O(n log n) time.

Theorem 3.

The minmax regret path center problem on a tree can be solved in O(n log n) time.