The Minimum Moving Spanning Tree Problem

Abstract

We investigate the problem of finding a spanning tree of a set of moving points in the plane that minimizes the maximum total weight (sum of Euclidean distances between edge endpoints) or the maximum bottleneck throughout the motion. The output is a single tree, i.e., it does not change combinatorially during the movement of the points. We call these trees the minimum moving spanning tree, and the minimum bottleneck moving spanning tree, respectively. We show that, although finding the minimum bottleneck moving spanning tree can be done in $O(n^2)$ time, it is NP-hard to compute the minimum moving spanning tree. We provide a simple $O(n^2)$-time 2-approximation and a $O(n \log n)$-time $(2+\varepsilon )$-approximation for the latter problem.

Supported by NSERC.

1 Introduction

The Euclidean minimum spanning tree (EMST) of a point set is the minimum weight graph that connects the given point set, where the weight of the graph is given by the sum of Euclidean distances between endpoints of edges. EMST is a classic data structure in computational geometry and it has found many uses in network design and in approximating NP-hard problems. In the visualization community, a series of methods generalize Euler diagrams to represent spatial data [2, 8, 9, 16]. These approaches represent a set by a connected colored shape containing the points in the plane that are in the given set. In order to reduce visual clutter, approaches such as Kelp Diagrams [9] and colored spanning graphs [13] try to minimize the area (or “ink”) of such colored shapes. Each shape can be considered as a generalization of the EMST of points in the set.

Motivated by visualizations of time-varying spatial data, we investigate a natural generalization of the minimum spanning tree (MST) and the minimum bottleneck spanning tree (MBST) for a set of moving points. In general it is desirable that visualizations are stable, i.e., small changes in the input should produce small changes in the output [17]. In this paper, we want to maintain all points connected throughout the motion by the same tree (the tree does not change topologically during the time frame) . Consider points in the plane moving on a straight line with constant speed over a time interval [0, 1]. The weight of an edge pq between points p and q is defined to be the Euclidean distance $\Vert pq\Vert$. Note that the weight of an edge changes over time. We define the Minimum Moving Spanning Tree (MMST) of a set of moving points to be a spanning tree that minimizes the maximum sum of weights of its edges during the time interval. Analogously, we define Minimum Bottleneck Moving Spanning Tree (MBMST) of a set of moving points to be a spanning tree that minimizes the maximum individual weight of edges in the tree during the time interval.

Apart from this motivation, the concepts of MMST and MBMST are relevant in the context of moving networks. Motivated by the increase in mobile data consumption, network architecture containing mobile nodes have been considered [14]. In this setting, the design of the topology of the networks is a challenge. Due to the mobility of the vertices, existing methods update the topology dynamically and the stability becomes important since there are costs associated with establishing new connections and handing over ongoing sessions. The MMST and MBMST offer stability in mobile networks.

Results and Organization. We study the problems of finding an MMST and an MBMST of a set of points moving linearly, each at constant speed. Section 2 provides formal definitions and proves that the distance function between points is convex in this setting. We use this property in an exact $O(n^2)$-time algorithm for the MBMST as shown in Sect. 3. Our algorithm computes the minimum bottleneck tree in a complete graph G on the moving points in which the weight of each edge is the maximum distance between the pairs of points during the time frame. In Sect. 4.1 we present an $O(n^2)$-time 2-approximation for MMST by computing the MST of G. In the full version of the paper we provide an example that shows our analysis for the approximation ratio is tight. In Sect. 4.2, we show that the MMST is equal to the minimum spanning tree of a point set in $\mathbb {R}^4$ with a non-Euclidean metric. Since this metric space has doubling dimension O(1), we obtain an $O(n \log n)$-time $(2+\varepsilon )$-approximation algorithm. Finally, we show that the problem of finding the MMST is NP-hard in Sect. 4.3 by reducing from the Partition problem.

Related work. Examples of other visualizations of time-varying spatial data are space-time cubes [15], that represent varying 2D data points with a third dimension, and motion rugs [6, 21], that reduces the dimentionality of the movement of data points to 1D, presenting a 2D static overview visualizations. The representation of time-varying geometric sets were also the theme of a recent Dagstuhl Seminar 19192 “Visual Analytics for Sets over Time and Space” [10]. In the context of algorithms dealing with time-varying data Meulemans et al. [17] introduces a metric for stability, analysing the trade-off between quality and stability of results, and applying it to the EMST of moving points. Monma and Suri [18] study the number of topological changes that occur in the EMST when one point is allowed to move.

The problem of finding the MMST and MBMST of moving points can be seen as a bicriteria optimization problem if the points move linearly (as shown in Sect. 2.2). In this context, the addition of a new criterion could lead to an NP-hard problem, such as the bi-criteria shortest path problem in weighted graphs. Garey and Johnson show that given a source and target vertices, minimizing both length and weight of a path from source to target is NP-hard [11, p. 214]. Arkin et al. analyse other criteria combined with the shortest path problem [4], such as the total turn length and different norms for path length.

Maintaining the EMST and other geometric structures of a set of moving points have been investigated by several papers since 1985 [5]. Kinetic data structures have been proposed to maintain the EMST [1, 20]. Research in this area have focused on bounds on the number of combinatorial changes in the EMST and efficient algorithms. To the best of our knowledge, the problem of finding the MMST and MBMST (a single tree that does not change during the movement of points) has not been investigated.

2 Preliminaries

In this section we formally define the minimum moving spanning tree and the minimum bottleneck moving spanning tree of a set of moving points. We then prove that, for points moving linearly, the distance function between a pair of points is convex.

2.1 Definitions

A moving point p in the plane is a continuous function $p:[0,1]\rightarrow \mathbb {R}^2$. We assume that p moves on a straight line segment in $\mathbb {R}^2$. We say that p is at p(t) at time t. We are given a set $S=\{p_1,...,p_n\}$ of moving points in the plane. A moving spanning tree T of S has S as its vertex set and weight function $w_T:[0,1]\rightarrow \mathbb {R}$ defined as $w_T(t)=\sum _{pq\in T}\Vert p(t)q(t)\Vert$. Let $\mathcal {T}(S)$ denote the set of all moving spanning trees of S. Let $w(T)=\sup _{t} w_T(t)$ be the weight of the moving spanning tree T. A minimum moving spanning tree (MMST) of S is a moving spanning tree of S with minimum weight. In other words an MMST is in

Let $b_T(t)=\sup _{pq\in T} \Vert p(t)q(t)\Vert$ denote the bottleneck of a tree T at time t. A minimum bottleneck moving spanning tree (MBMST) of S is a moving spanning tree of S that minimizes the bottleneck over all $t\in [0,1]$. In other words an MBMST is in

2.2 Convexity

Let p and q be two moving points in the plane. We assume that these points move along (possibly different) lines at (possibly different) constant velocities. Thus, for any real number t, we can write the positions of p and q at time t as

$$ p(t) = ( a_p + u_p t , b_p + v_p t ) $$

and

$$ q(t) = ( a_q + u_q t , b_q + v_q t ) , $$

where $a_p, u_p, b_p, v_p$ are constants associated with the point p. At time $t=0$, p is at $(a_p,b_p)$, and the velocity vector of p is $(u_p,v_p)$. Let $d(t)=\Vert p(t)q(t)\Vert$ denote the Euclidean distance between p and q at time t. In the next lemma we prove that d is a convex function. The convexity of d is also implied by a result of Alt and Godau [3] that the free space diagram of any two line segments is convex.

Lemma 1

The function d is convex.

Proof

It suffices to prove that the second derivative of d is non-negative for all real numbers t. We can write

$$ d(t) = \sqrt{A t^2 + Bt + C} , $$

where A, B, and C depend only on $a_p,u_p,b_p,v_p,a_q,u_q,b_q$, and $v_q$. Observe that $A \ge 0$. Since d(t) represents a distance, $A t^2 + Bt + C \ge 0$ for all t in $\mathbb {R}$. It follows that the discriminant of this quadratic function is non-positive, i.e.,

$$\begin{aligned} B^2 - 4AC \le 0 . \end{aligned}$$

(1)

Let $\alpha = -B/2A$ and $\beta = C/A - B^2/(4A^2)$. Then

$$ d(t) = \sqrt{A} \cdot \sqrt{(t-\alpha )^2 + \beta } . $$

The second derivative of the function $f(t) = \sqrt{t^2 + \beta }$ is given by

$$\begin{aligned} f''(t) = \frac{\beta }{(t^2+\beta )^{3/2}} . \end{aligned}$$

It follows from (1) that $\beta \ge 0$. Thus, $f''(t) \ge 0$ for all t in $\mathbb {R}$. Since $d(t) = \sqrt{A} \cdot f(t-\alpha )$, we have $d''(t) \ge 0$ for all t in $\mathbb {R}$, and in particular, for $t\in [0,1]$.    $\square$

The convexity of the distance function between two moving points (Lemma 1) implies the following corollary.

Corollary 1

The largest distance between two moving points is attained either at the start time or at the finish time.

Let S be a set of n moving points in the plane. For two points p and q in S, we denote by $\Vert p(0)q(0)\Vert$ and $\Vert p(1)q(1)\Vert$ the distances between p and q at times $t=0$ and $t=1$, respectively. Moreover, we denote by $|pq|_{\text {max}}$ the largest distance between p and q during time interval [0, 1]. By Corollary 1 we have

$$\begin{aligned} |pq|_{\text {max}}=\max \{\Vert p(0)q(0)\Vert , \Vert p(1)q(1)\Vert \}. \end{aligned}$$

(2)

3 Minimum Bottleneck Moving Spanning Tree

Since by Corollary 1 the largest length of an edge is attained either at time 0 or at time 1, it might be tempting to think that the MBMST of S is also attained at times 0 or 1. However the example in Fig. 1(a) shows that this may not be true. In this example we have four points a, b, c, and d that move from time 0 to time 1 as depicted in the figure. The MBST of these points at time 0 is the red tree R, and their MBST at time 1 is the blue tree B. Recall that $b_T(t)$ is the bottleneck of tree T at time t. Let $b(T)=\max _{t} b_T(t)$ be the bottleneck of T. In R the weight of ab at time 0 is 1 while its weight at time 1 is 3, and thus $b(R)=3$. In B the weight of ad at time 1 is 1 while its weigh at time 0 is 3, and thus $b(B)=3$. However, for this point set the tree $T=\{ac, cb, cd\}$ has bottleneck 2.

Fig. 1.

Four points that move from time 0 to time 1. (a) R is the MBST at time 0, and B is the MBST at time 1. (b) The graph G; green edges form an MBST of this graph. (Color figure online)

Although the above example shows that the computation of the MBMST is not straightforward, we present a simple algorithm for finding the MBMST. Let G be the complete graph on points of S where the weight w(pq) of every edge pq is the largest distance between p and q during time interval [0, 1], that is, $w(pq)=|pq|_{\text {max}}$; see Fig. 1(b).

Lemma 2

The bottleneck of an MBMST of S is not smaller than the bottleneck of an MBST of G.

Proof

Our proof is by contradiction. Let $T^*$ be an MBMST of S and let T be an MBST of G. For the sake of contradiction assume that $b(T^*)<b(T)$, where we abuse the notation for simplicity making $b(T)=\max _{pq\in T} w(pq)$ the bottleneck of T. Let pq be a bottleneck edge of T, that is $b(T)=w(pq)$. Denote by $T_p$ and $T_q$ the two subtrees obtained by removing pq from T, and denote by $V_p$ and $V_q$ the vertex sets of these subtrees. Since the vertex set of T is the same as that of $T^*$, there is an edge, say rs, in $T^*$ that connects a vertex of $V_p$ to a vertex of $V_q$. Since the bottleneck of $T^*$ is its largest edge-length in time interval [0, 1], we have that $|rs|_{\text {max}}\leqslant b(T^*)$. Since in G we have $w(rs)=|rs|_{\text {max}}$, the following inequality is valid: $w(rs)=|rs|_{\text {max}}\leqslant b(T^*)<b(T)=w(pq)$. Let $T'$ be the spanning tree of G that is obtained by connecting $T_p$ and $T_q$ by rs. Then $b(T')\leqslant b(T^*)$. If we repeat this process for all bottleneck edges of T, then we obtain a tree $T'$ whose bottleneck is strictly smaller than that of T. This contradicts the fact that T is an MBST of G.    $\square$

It is implied from Lemma 2 that any MBST of G is an MBMST of S. Since an MBST of a graph can be computed in time linear in the size of the graph [7], an MBST of G can be computed in $O(n^2)$ time. The following theorem summarizes our result in this section.

Theorem 1

A minimum bottleneck moving spanning tree of n moving points in the plane can be computed in $O(n^2)$ time.

4 Minimum Moving Spanning Tree

In this section we study the problem of computing an MMST of moving points. At the end of this section we prove that this problem is NP-hard. We start by proposing a 2-approximation algorithm for the MST problem. In the full version of the paper we show that our analysis of the approximation ratio is tight.

4.1 A 2-approximation Algorithm

Our algorithm is very simple and just computes a MST of the graph G that is constructed in Sect. 3.

Lemma 3

The weight of any MST of G is at most two times the weight of any MMST of S.

Proof

Let T be any MST of G and let $T^*$ be any MMST of S. Let $w(T^*)=\sup _{t} w_T(t)$ be the weight of the moving spanning tree $T^*$. We abuse the notation for simplicity making $w(T)=\sum _{pq\in T}w(pq)$ the weight of the spanning tree T. We are going to show that $w(T)\leqslant 2\cdot w(T^*)$. Let $T'$ be a tree that is combinatorially equivalent to $T^*$, i.e., has the same topology as $T^*$. Assign to each edge pq of $T'$ the weight $w(pq)=|pq|_{\text {max}}$. After this weight assignment, $T'$ is a spanning tree of G. Since T is a MST of G, we have $w(T)\leqslant w(T')$.

By Corollary 1 the largest distance between two points is achieved either at time 0 or at time 1. Let $E_0^*$ be the set of edges of $T^*$ whose endpoints largest distance is achieved at time 0. Define $E_1^*$ analogously. Then $w(E_0^*)\leqslant w(T^*)$ and $w(E_1^*)\leqslant w(T^*)$. Moreover, $w(T')=w(E_0^*)+w(E_1^*)$. By combining these inequalities we get

$$w(T)\leqslant w(T')=w(E_0^*)+w(E_1^*)\leqslant w(T^*)+w(T^*)=2\cdot w(T^*).$$

   $\square$

A minimum spanning tree of G can be computed in $O(n^2)$ time using Prim’s MST algorithm. The following theorem summarizes our result in this section.

Theorem 2

There is an $O(n^2)$-time 2-approximation algorithm for computing the minimum moving spanning tree of n moving points in the plane.

4.2 An $O(n \log n)$-time $(2+\varepsilon )$-approximation Algorithm

Section 4.1 showed that the weight of the minimum spanning tree of the graph G, defined in Sect. 3, gives a 2-approximation to the MMST. Since G has $\varTheta (n^2)$ edges, it takes $\varTheta (n^2)$ time to compute its MST. In this section, we prove that a $(1+\varepsilon )$-approximation to the minimum spanning tree of G can be computed in $O(n \log n)$ expected time. Thus, if we replace $\varepsilon$ by $\varepsilon /2$, we obtain a $(2+\varepsilon )$-approximation to computing the MMST of a set of linearly moving points S.

For any point p in S, define the point

$$ P = ( p(0), p(1) ) $$

in $\mathbb {R}^4$. Doing this for all points in S, we obtain a set $S'$ of n points in $\mathbb {R}^4$. For any two points P and Q in $S'$, define their distance to be

$$ \text {dist}(P,Q) = \max ( \Vert p(0) q(0) \Vert , \Vert p(1) q(1)\Vert ) . $$

Since $\text {dist}(P,Q) = w(pq)$, the minimum spanning tree of our graph G has the same weight as the minimum spanning tree (under $\text {dist})$ of the point set $S'$.

Lemma 5 below states that $\text {dist}$ satisfies the properties of a metric. Its proof uses the following lemma, which is probably well known.

Lemma 4

Let V be an arbitrary set and let $d_1 : V \times V \rightarrow \mathbb {R}$ and $d_2 : V \times V \rightarrow \mathbb {R}$ be two functions, such that both $(V,d_1)$ and $(V,d_2)$ are metric spaces. Define the function $d : V \times V \rightarrow \mathbb {R}$ by

$$ d(a,b) = \max ( d_1(a,b) , d_2(a,b) ) $$

for all a and b in V. Then (V, d) is a metric space.

Proof

It is clear that, for all a and b in V, $d(a,a) = 0$, $d(a,b) > 0$ if $a \ne b$, and $d(a,b) = d(b,a)$. It remains to prove that the triangle inequality holds.

Let a, b, and c be elements of V. Then

$$\begin{aligned} d(a,b)= & {} \max ( d_1(a,b) , d_2(a,b) ) \\\le & {} \max ( d_1(a,c) + d_1(c,b) , d_2(a,c) + d_2(c,b) ) . \end{aligned}$$

Using the inequality

$$ \max ( \alpha + \beta , \gamma + \delta ) \le \max (\alpha ,\gamma ) + \max (\beta ,\delta ) , $$

it follows that

$$\begin{aligned} d(a,b)\le & {} \max ( d_1(a,c) , d_2(a,c) ) + \max ( d_1(c,b) , d_2(c,b) ) \\= & {} d(a,c) + d(c,b) . \end{aligned}$$

   $\square$

Lemma 5

The pair $(S', {\text {dist}})$ is a metric space.

Proof

The proof follows from Lemma 4 and the definition of $\text {dist}$.    $\square$

The next lemma states that the metric space $(S',\text {dist})$ has bounded doubling dimension. We recall the definition. For any point P in $S'$ and any real number $\rho > 0$, the ball with center P and radius $\rho$ is the set

$$ \text {ball}^{\text {dist}}(P,\rho ) = \{ Q \in S' : \text {dist}(P,Q) \le \rho \} . $$

Let $\lambda$ be the smallest integer such that for every real number $\rho >0$, every ball of radius $\rho$ can be covered by at most $\lambda$ balls of radius $\rho /2$. The doubling dimension of $(S',\text {dist})$ is defined to be $\log \lambda$.

Lemma 6

The doubling dimension of the metric space $(S', {\text {dist}})$ is O(1).

Proof

Recall that $S'$ is a set of points in $\mathbb {R}^4$. We denote the Euclidean distance between two points P and Q of $S'$ by $\Vert PQ\Vert$. The Euclidean ball with center P and radius $\rho$ is denoted by $\text {ball}^e(P,\rho )$. Thus,

$$ \text {ball}^e(P,\rho ) = \{ Q \in S' : |PQ| \le \rho \} . $$

It is easy to verify that

$$\begin{aligned} \text {dist}(P,Q) \le \Vert PQ\Vert \le \sqrt{2} \cdot \text {dist}(P,Q) . \end{aligned}$$

(3)

Let P be a point in $S'$, let $\rho >0$ be a real number, and let $B^{\text {dist}} = \text {ball}^{\text {dist}}(P,\rho )$. We will prove that $B^{\text {dist}}$ can be covered by O(1) balls of radius $\rho /2$.

Let $B^e$ be the Euclidean ball with center P and radius $\rho \cdot \sqrt{2}$. It follows from (3) that

$$ B^{\text {dist}} \subseteq B^e . $$

It is well known that the doubling dimension of the Euclidean space $\mathbb {R}^4$ is bounded by a constant. Thus, by applying the definition of doubling dimension twice, we can cover $B^e$ by $k=O(1)$ Euclidean balls $B_1^e , \ldots , B_k^e$ balls, each of radius $\rho \cdot \sqrt{2} / 4 \le \rho /2$. Let these balls have centers $C_1,\ldots ,C_k$. For each $i=1,\ldots ,k$, define $B_i^{\text {dist}} = \text {ball}^{\text {dist}}(C_i,\rho /2)$. It follows from (3) that

$$ B_i^e \subseteq B_i^{\text {dist}} . $$

Thus,

$$ B^{\text {dist}} \subseteq B^e \subseteq \bigcup _{i=1}^k B_i^e \subseteq \bigcup _{i=1}^k B_i^{\text {dist}} , $$

i.e., we have covered the ball $B^{\text {dist}}$ by $k=O(1)$ balls of radius $\rho /2$.    $\square$

Lemma 7

Let $\varepsilon >0$ be a constant. In $O(n \log n)$ expected time, we can compute a $(1+\varepsilon )$-approximation to the minimum spanning tree of the metric space $(S', {\text {dist}})$.

Proof

As $(S',\text {dist})$ has a constant doubling dimension (by Lemma 6), a result of Har-Peled and Mendel [12] implies that a $(1+\varepsilon )$-spanner of $(S',\text {dist})$ with O(n) edges can be computed in $O(n \log n)$ expected time. Their algorithm assumes that any distance in the metric space can be computed in O(1) time; this is the case for our distance function $\text {dist}$.

It is known that a minimum spanning tree of a $(1+\varepsilon )$-spanner is a $(1+\varepsilon )$-approximation to the minimum spanning tree. (See, e.g., [19, Theorem 1.3.1]).

Since the spanner has O(n) edges, its minimum spanning tree can be computed in $O(n \log n)$ time using Prim’s MST algorithm combined with a binary min-heap.    $\square$

As a consequence of Lemma 7 and the fact that $\text {dist}(P,Q) = w(pq)$, we have the following theorem.

Theorem 3

In $O(n \log n)$ expected time, we can compute a $(2+\varepsilon )$-approximation for the minimum moving spanning tree of a set of linearly moving points in the plane.

4.3 NP-hardness of MMST

Inspired by Arkin et al. [4], we reduce the Partition problem, which is known to be NP-hard [11], to the MMST problem. In one formulation of the Partition problem, we are given $n>0$ positive integers $a_{0},\ldots ,a_{n-1}$ and must decide whether there is a subset $S\subseteq \{0,\ldots ,n-1\}$ such that

$$ \sum _{i\in S}a_{i}=\frac{1}{2}\sum _{i=0}^{n-1}a_{i}. $$

Construction. We construct an instance of a decision version of the MMST problem defined as follows. First we let $\ell =\max \{a_{0},\ldots ,a_{n-1}\}$ and then, for each $i\in \{0,\ldots ,n-1\}$, we put the following points into our set P of moving points (Fig. 2):

• $A_{i}$, stationary at $(i\ell ,0)$;

• $B_{i}$, stationary at $(i\ell ,\ell )$;

• $C_{i}$, moving from $(i\ell ,\ell )$ to $(i\ell ,\ell +a_{i})$;

• $D_{i}$, stationary at $(i\ell ,\ell +a_{i})$; and

• $E_{i}$, moving from $(i\ell ,\ell +a_{i})$ to $(i\ell ,\ell )$.

We then ask whether there is a moving spanning tree T with

$$w(T) \le (2n-1)\ell +\frac{3}{2}\sum _{i=0}^{n-1}a_{i}.$$

Fig. 2.

The positions of the points in P at time $t=1/4$ when $n=4$ and $(a_{0},a_{1},a_{2},a_{3})=(1,2,4,3)$. The velocities of $C_{2}$, $E_{2}$, $C_{3}$ and $E_{3}$ are depicted.

Theorem 4

The decision version of the MMST problem is weakly NP-hard.

Proof

Let T be a moving spanning tree on vertex set P. Recall that $w_{T}(t)$ denotes the weight of T at time t. By Lemma 1, $w_{T}$ is a convex function and the weight of T is indeed $w(T)=\max \bigl \{ w_{T}(0),w_{T}(1)\bigr \}$.

Let $K_{0}$ be the set of edges $A_{i}B_{i}$ for $i\in \{0,\ldots ,n-1\}$ and $A_{i}A_{i+1}$ for $i\in \{0,\ldots ,n-2\}$ and let $K_{1}$ be the set of edges among $B_{i}$, $C_{i}$, $D_{i}$ and $E_{i}$ for each $i\in \{0,\ldots ,n-1\}$ together with $K_{0}$ (Fig. 3). We claim that there is a moving spanning tree $T^{*}$ of minimum cost, i.e., an optimal solution to the MMST problem, whose edges are all in $K_{1}$. Assume the contrary for contradiction. Let T be an MMST whose intersection with $K_{1}$ is maximum. By assumption, T has at least an edge $e\not \in K_1$. We now consider the two components obtained from deleting e from T. There must be at least one edge $e'\in K_1$ between the two components, since $K_{1}$ spans P. However, at any point in time, every edge in $K_{1}$ weights at most $\ell$ while every edge outside of $K_{1}$ weights at least $\ell$, so if we bridge the two components with $e'$, we will be left with a spanning tree $T'$ with $w(T')\le w(T)$ and with a larger intersection with $K_{1}$, contradicting the definition of T.

Fig. 3.

The (topological) edges in $K_{0}$ (dashed) and in $K_{1}\setminus K_{0}$ (solid).

As every edge in $K_{0}$ is a bridge in the graph $(P,K_{1})$, the spanning tree $T^{*}$ must contain $K_{0}$, so $T^{*}$ consists of $K_{0}$ and, for each $i\in \{0,\ldots ,n-1\}$, of a subtree $T_{i}$ spanning $\{B_{i},C_{i},D_{i},E_{i}\}$. The weights $w_{T_{i}}(0)$ and $w_{T_{i}}(1)$ must both be a multiple of $a_{i}$ since so are the Euclidean distances between the vertices of $T_{i}$ at these two times. There are two notable ways to build $T_{i}$: one is $T_{i}=\{B_{i}C_{i},C_{i}D_{i},D_{i}E_{i}\}$, which satisfies $w_{T_{i}}(0)=a_{i}$ and $w_{T_{i}}(1)=2a_{i}$ and is thus called the (1, 2)-tree; and the other is $T_{i}=\{B_{i}E_{i},E_{i}D_{i},D_{i}C_{i}\}$, which satisfies $w_{T_{i}}(0)=2a_{i}$ and $w_{T_{i}}(1)=a_{i}$ and is thus called the (2, 1)-tree.

We shall show that the (1, 2)-tree or the (2, 1)-tree have minimum weight among all moving spanning trees of $\{B_{i},C_{i},D_{i},E_{i}\}$. Indeed, $T_{i}$ is made of three edges and, since there are no three edges with weight zero at time 0, as can be seen in Fig. 4, we must have $w_{T_{i}}(0)\ge a_{i}$ and, similarly, $w_{T_{i}}(1)\ge a_{i}$. Furthermore, each edge between $B_{i}$, $C_{i}$, $D_{i}$ and $E_{i}$ adds up to at least $a_{i}$ in terms of their weight at time 0 and at time 1. Therefore, $w_{T_{i}}(0)+w_{T_{i}}(1)\ge 3a_{i}$, so either $w_{T_{i}}(0)\ge 2a_{i}$, , or $w_{T_{i}}(1)\ge 2a_{i}$ . As a result, we may assume, without loss of generality, that $T_{i}$ is either the (1, 2)-tree or the (2, 1)-tree.

Fig. 4.

Edges between $B_{i}$, $C_{i}$, $D_{i}$ and $E_{i}$ labeled with their weights at times 0 and 1.

Let now $S^{*}\subseteq \{0,\ldots ,n-1\}$ be the set of indices i such that $T_{i}$ is the corresponding (2, 1)-tree. As $|K_{0}|=2n-1$, we have

$$ w_{T^{*}}(0)=(2n-1)\ell +\sum _{i=0}^{n-1}a_{i}+\sum _{i\in S^{*}}a_{i}, $$

while

$$ w_{T^{*}}(1)=(2n-1)\ell +\sum _{i=0}^{n-1}a_{i}+\sum _{i\in \{0,\ldots ,n-1\}\setminus S^{*}}a_{i}. $$

Therefore, the cost of $T^{*}$ is

$$ (2n-1)\ell +\sum _{i=0}^{n-1}a_{i}+\max \left\{ \sum _{i\in S^{*}}a_{i},\sum _{i\in \{0,\ldots ,n-1\}\setminus S^{*}}a_{i}\right\} . $$

Because

$$ \sum _{i\in S^{*}}a_{i}\ge \frac{1}{2}\sum _{i=0}^{n-1}a_{i}\qquad \text {or}\qquad \sum _{i\in \{0,\ldots ,n-1\}\setminus S^{*}}a_{i}\ge \frac{1}{2}\sum _{i=0}^{n-1}a_{i}, $$

then the following holds

$$\begin{aligned} w(T^*) \ge (2n-1)\ell +\frac{3}{2}\sum _{i=0}^{n-1}a_{i}. \end{aligned}$$

(4)

We claim that (4) holds with equality if and only if our instance of the Partition problem has a solution, i.e., there is a set $S\subseteq \{0,\ldots ,n-1\}$ such that the sum of $a_{i}$ for $i\in S$ is half of $a_{0}+\cdots +a_{n-1}$. Indeed, if the equality holds, we can simply let $S=S^{*}$. To show the converse, we build a tree T from the solution S of the Partition problem. This tree contains $K_{0}$, the corresponding (2, 1)-trees for i in S and the corresponding (1, 2)-trees for $i\in \{0,\ldots ,n-1\}\setminus S$, resulting in a weight of

$$\begin{aligned} w(T)=(2n-1)\ell +\frac{3}{2}\sum _{i=0}^{n-1}a_{i}. \end{aligned}$$

Because $T^{*}$ is an MMST, $w(T^*)\le w(T)$, so the equality holds.    $\square$