{'fraction_non_alphanumeric': 0.05428498337170632, 'fraction_numerical': 0.011051419800460476, 'mean_word_length': 3.90243290694758, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Parametric Fermat-Weber and tropical supertrees

We study a parametric version of the Fermat-Weber problem with respect to an asymmetric distance function, which occurs naturally in tropical geometry. Our results yield a method for constructing phylogenetic supertrees.


Introduction
The Fermat-Weber problem is a classical location problem that seeks a point whose average distance to a finite set of sites is minimal; such a point is called a Fermat-Weber point. The history of the problem can be traced back to Fermat and gained popularity in applied context under the work of Weber; see [3, Chapter II] for a historical account. In [7] we looked at the Fermat-Weber problem for an asymmetric tropical distance function. In this paper, we focus on a parametric version of the tropical Fermat-Weber problem; see [4] for a survey on general parametric location problems. More precisely, we consider the case where each site moves along a line, and we study how the set of Fermat-Weber points changes. The results in [7] heavily exploit the known structure of tropically convex sets in terms of regular subdivisions of products of simplices [9]; see also [11, §6.3]. Here we analyze the relevant secondary fans in more detail, by looking at the variation of regular subdivisions with respect to changing the height function. In this way we show that the Fermat-Weber set asymptotically stabilizes from a combinatorial point of view. Further, we give an explicit bound for that stabilization to occur. This is our first contribution.
Our study of tropical Fermat-Weber points is motivated by phylogenetics [17]. That field of computational biology is concerned with organizing ancestral relations in biological data into trees. In our scenario, the taxa, which are the individual points in a given data set, are associated with the leaves of a tree; the root marks the most recent common ancestor. A basic problem, which occurs in practice, asks to compile the information from several trees into a single tree. In the easier case the individual trees all share the same taxa, and the resulting tree is called a consensus tree. Due to the tremendous interest in phylogenomics methods, and also to differing demands in different application scenarios, many methods were developed over the last few decades [12]. They all output only estimates of the true phylogeny and thus it is necessary to evaluate the confidence of the results. Apart from Bayesian methods, where posterior distributions yield measures for confidence, the usual approach is to use bootstrapping generating solution sets. In any case, assessment usual involves consideration of many phylogenetic trees and the search for a consensus. Similarly, trees resulting from distinct methods, for a fixed number of taxa, often disagree, and again finding a consensus is of central interest. Since this turns out to be a nontrivial task, computing consensus trees became a topic of its own [5,18,6].
In [7] we constructed a consensus tree as a Fermat-Weber point in tree space. In a more general setting, the input trees may have distinct sets of taxa; e.g., see [13]. Here the resulting tree is called a supertree, and our second contribution is a new method for their construction. These tropical supertrees arise from combining the tropical consensus trees from [7] with our new parametric solution of the tropical Fermat-Weber problem and the big-M method in optimization. The latter technique explores the behavior of the feasible domain of an optimization problem at infinity by computing with sufficiently large real values; see, e.g., [16, §11.2].

Parametric tropical medians
Before we can look at algorithms for phylogenetics, we need to investigate specific questions concerning covector decompositions in tropical convexity; see [11, §6.3]. Later metric trees will occur as points in a suitable tropical projective torus, and a tropical supertree is a tree in a certain cell in the covector decomposition generated by those points.
A nonempty set S ⊆ R n is tropically convex (with respect to max) if z lies in S, where z i = max(λ + x i , µ + y i ), for all x, y ∈ S and λ, µ ∈ R. Each tropically convex subset of R n contains R1, and hence it makes sense to consider tropically convex sets in the quotient R n /R1, which is the tropical projective torus; here 1 denotes the all ones vector. The tropical convex hull of S is the smallest tropically convex set containing S, and a tropical polytope is the tropical convex hull of finitely many points in R n /R1. It may happen that a tropical polytope is a convex subset in the ordinary sense; then it is a polytrope; cf. [11, §6.5]. Any finite point set V ⊂ R n /R1 induces a polyhedral decomposition of R n /R1, the covector decomposition CovDec(V ), such that the bounded cells comprise the tropical convex hull tconv(V ). Each cell of the covector decomposition is a polytrope. The matrix V in R m×n may also be seen as a lifting function on the product of simplices ∆ m−1 × ∆ n−1 . This gives rise to a regular subdivision, Σ(V ); see [11, §1.2] for a brief introduction and [8] for more comprehensive information. It turns out that Σ(V ) is dual to CovDec(V ) [11,Corollary 6.15].
We consider the asymmetric tropical distance function d n on R n , which we define as This descends to the quotient R n /R1. The function d n is the convex distance function induced by the standard simplex ∆ n−1 = conv(e 1 , . . . , e n ), where the vectors e i form the standard basis of R n . Since the polytope ∆ n−1 has codimension one in R n , passing to R n /R1 is natural. The crucial algorithmic ingredient is the following optimization problem that we studied in [7]. Given a set, V , of m points in R n /R1 we want to find a point x ∈ R n /R1 such that v∈V d n (v, x) is minimal. Such a point, in general, is not unique, and the set of all minimizers is the asymmetric tropical Fermat-Weber set, denoted FW(V ). We can identify minimizers by looking at the unique cell of Σ(V ) that contains the vertex barycenter ( 1 m 1, 1 n 1) of ∆ m−1 ×∆ n−1 . We name it the central cell of Σ(V ) and its dual in CovDec(V ) the central covector cell. We recall the following result. Our first goal is to generalize Theorem 1 to the situation where the point configuration V depends on a parameter. To this end we consider points u 1 , . . . , u m , w 1 , . . . , w m ∈ R n , and we call the m affine lines in R n an affine family of point configurations, depending on a real parameter M. The affine lines (2) may be seen as an affine family in and v i is the ith row. Our refined goal is now to describe the Fermat-Weber set FW(V (M)) for M sufficiently large. Following standard practice, and to avoid cumbersome notation, we intentionally blur the line between M as a real number and M as a formal parameter. The name "M" is chosen as a hint to the big-M method in optimization; see, e.g., [16, §11.2]. We may view an affine family as a set of points, where each point travels along an affine line (into the positive direction).
To understand the behavior of CovDec(V (M)) with the change of M we make use of the duality to the regular subdivision Σ(V (M)) of ∆ m−1 × ∆ n−1 . There are only finitely many regular subdivisions of ∆ m−1 × ∆ n−1 , and the lifting function corresponding to any fixed subdivision, Σ, form a relatively open polyhedral cone, called the relative open secondary cone of Σ. It follows that the height functions on ∆ m−1 × ∆ n−1 give rise to a complete polyhedral fan in the vector space R m×n ; this is the secondary fan of ∆ m−1 × ∆ n−1 . The finiteness of the secondary fan implies that there exists M 0 ∈ R such that for all real M 1 , M 2 > M 0 the point configurations V (M 1 ) and V (M 2 ) lie in the same secondary cone, and thus Σ(V (M 1 )) = Σ(V (M 2 )). We say that the regular subdivisions Σ(V (M)) stabilize for M ≫ 0, and we use the same term for other polyhedra or polyhedral complexes depending on M.
Let C be a covector cell of CovDec(V (M)) and C ∨ its dual cell in Σ(V (M)). We can identify the cell C ∨ with a bipartite graph G(C) if and only if the vertex (e i , e j ) belongs to C; cf. [11, §4.7]. The graph bipartite G(C) is called the covector graph of the cell C. We emphasize that for every x ∈ C and every edge In order to understand how the Fermat-Weber set FW(V (M)) behaves with changing M, it suffices to track the tropical vertices. By [11,Theorem 6.38] any polytrope in R n /R1 has at most n tropical vertices. Each tropical vertex, t i (M), can be obtained by maximizing the linear functional n · e i − 1 on the Fermat-Weber set FW(V (M)), where i ∈ [n]; see [11,Theorem 3.26]. Note that duplicates may occur when FW(V (M)) is not full-dimensional. For our application to phylogenetics below, we want to pick a point in the relative interior of FW(V (M)) consistently. In [7] we chose the ordinary average of the tropical vertices, i.e., the average of the distinct values of the set {t i (M) | i ∈ [n]}. The latter point is the tropical median of the configuration V (M). The following result is the desired parametric version of Theorem 1.

Proposition 2. The combinatorial types of covector decompositions
Moreover, for all M > M 0 , the tropical vertices of FW(V (M)) and the tropical median depend affinely on M. That is, there exist p i , q i ∈ R n /R1, for i ∈ [n], such that t i (M) = p i + Mq i for all M > M 0 , and a similar statement holds for the tropical median.
It is worth pointing out that the same M 0 works for the covector decomposition, the tropical vertices and the tropical median.
Proof. Since the regular subdivisions Σ(V (M)) stabilize for M ≫ 0, it follows that the combinatorial types of covector decompositions CovDec(V (M)) stabilize for M ≫ 0, as they are dual to Σ(V (M)). According to Theorem 1, the Fermat-Weber set FW(V (M)) corresponds to the central cell of CovDec(V (M)), so the stabilization of the covector decomposition implies that all tropical vertices of FW(V (M)) share the same covector graph for M sufficiently large.
Consider the tropical vertex x = x(M) = t i (M), for some i ∈ [n], and let G be its covector graph for M ≫ 0. Since x is a vertex of CovDec(V (M)), by [11,Corollary 6.26], the graph G is connected. So there exists a walk W in G visiting every coordinate node of G. To complete our proof we will proceed inductively along the walk W .
To this end we fix x p = 0 for the first coordinate node p ∈ [n] which occurs in W , and our goal is to recover all the other coordinates of x by moving along the walk W . Let x r be a coordinate yet unknown, but we already have the value x q of the coordinate node q which occurs before r in W . By the induction hypothesis, we assume that  Here we pick representatives in x + R1 such that x 1 + x 2 + x 3 = 0, as in [7]. Then FW(V (M)) agrees with tconv max (V (M)) for M ≫ 0, and so the tropical median is the average of the input points: For computations it is useful to have an explicit threshold M 0 such that CovDec(V (M)) has the same combinatorial type for any M > M 0 . To this end it will turn out to be helpful to gather specific information on the complexity of the secondary fan of the products of simplices ∆ m−1 ×∆ n−1 . For a (not necessarily regular) triangulation Σ of ∆ m−1 × ∆ n−1 we define We return to studying our affine family V (M) = U +M ·W with U ∈ R m×n , but we now restrict W ∈ Z m×n to be integral. We denote the Euclidean scalar product of matrices as A, B = i,j a ij b ij = Tr(A ⊤ B), and A ∞ = max i,j |a ij | is the ∞-norm, while B 1 = i,j |b ij | is the 1-norm. Our first main result is the following quantitative version of Proposition 2. Proof. We follow the argument of Proposition 2 and pay attention to complexity issues.
The argument employs the linear hyperplane arrangement in R m×n formed by the facets of the maximal secondary cones of ∆ m−1 × ∆ n−1 . Those cones bijectively correspond to the regular triangulations. Let Φ be such a facet, which is the common intersection of exactly two maximal secondary cones. The secondary fan is the normal fan of the secondary polytope, and hence a normal vector of Φ is the same as a scaled edge of the secondary polytope. The direction of such an edge is given by the difference of two GKZ-vectors. Thus it follows from Lemma 4 that there is a primitive normal vector, A = (a ij ) i,j ∈ Z m×n , of Φ such that |a ij | ≤ m+n

This yields
where the last inequality holds because | A, W | is a positive integer. That contradicts M 2 > M 0 , and this completes the proof.

Constructing supertrees
Now we are ready to explain our method for constructing supertrees. They will arise as parameterized tropical medians of suitably modified equidistant trees. We start out by describing our setup. A rooted metric tree is equidistant if the distance from the root to any leaf is the same. The distance from the root to any leaf is the height of the tree. The latter quantity equals half of the maximal distance between any two leaves. The leaves are labeled, and these labels are called taxa. Now we consider a collection T = {T 1 , . . . , T m } of equidistant rooted metric trees, with labeled leaves, and we write L(T k ) for the taxa of the tree T k . The combined set of taxa is L = m k=1 L(T k ), and we let n = |L| be the cardinality of L. For consistency, we assume that the m trees in T share the same height.
A dissimilarity map is a symmetric matrix D = (D ij ) i,j with zero diagonal. This is an ultrametric if D is nonnegative, and additionally the ultrametric inequality D ik ≤ max(D ij , D jk ) is satisfied for all taxa i, j, k. It is known that the ultrametrics are precisely the dissimilarity functions among the leaves of equidistant trees [17,Theorem 7.2.5].
For each tree T ℓ we define an ultrametric D (ℓ) (M) = (D (ℓ) ij ) i,j on the set L by setting Here we assume that M ≫ 0 is a sufficiently large real number, so that D (ℓ) (M) is, indeed, an ultrametric. Due to Theorem 1, the Fermat-Weber set FW(T ), where each tree T ℓ is represented by its ultrametric D (ℓ) (M), is a polytrope in the tropical projective torus R L 2 /R1. Ardila and Klivans [2] showed that the space of equidistant metric trees, T(L), is max-tropically convex. So, in view of Theorem 1, FW(T ) is actually contained in the subset T(L). Further, by Proposition 2, the tropical vertices of FW(T ) depend affinely on M for M ≫ 0, whence they trace out a ray in T(L). The Fermat-Weber set FW(T ) is convex in the ordinary sense when we view R L 2 /R1 as a real vector space. Therefore, FW(T ) contains the tropical median, which is defined as the ordinary average of the (at most n 2 ) tropical vertices. We call the tropical median, c(T ), in T(L) the tropical supertree of T . The dissimilarity map associated with c(T ) depends on M ≫ 0, but we will show that the tree topology does not. This will become our second main result. Before we proceed, we need additional terminology from phylogenetics. Three pairwise distinct taxa i, j, k ∈ L form a rooted triplet, denoted ij|k, of a rooted phylogenetic tree T on L if the lowest common ancestor, lca T (i, j) of i and j is not an ancestor of k. If T is corresponds to the ultrametric D, then ij|k is a rooted triplet if and only if D ij < D ik . We write r(T ) (or r(D)) for the set of all rooted triplets. Page, Yoshida, and Zhang [15,Theorem 3.2] showed that any two trees in the relative interior of a covector cell share the same topology. We use the techniques from [17, §6.4] to prove a vast generalization of their result. Proposition 6. Let S be an arbitrary convex subset of T(L), in the ordinary sense. Then any two points in the relative interior of S are equidistant trees with the same topology.
Proof. By [17,Theorem 6.4.1] the tree topology is determined by the set of rooted triplets. That is, it suffices to prove that r(D) = r(E) for any two ultrametrics D, E ∈ relint(S). To this end let ij|k ∈ r(D), i.e., D ij < D ik = D jk .
Our first goal is to prove that ik|j and jk|i are not contained in r(E). The condition ij|k ∈ r(D) is symmetric in i and j, whence it suffices to show (ik|j) ∈ r(E). We assume the contrary, which is equivalent to E jk = E ij > E ik . Due to the convexity of S, the point F = 1 2 (D + E) belongs to S ⊂ T(L). Yet this is not an ultrametric as and, similarly, F jk > F ik . We conclude that either (ij|k) ∈ r(E) or E ij = E ik = E jk , and we need to exclude the latter case. Again we argue by contradiction. So we assume that E ij = E ik = E jk . Then we consider F = E + ǫ(E − D), which lies in relint(S) for some sufficiently small ǫ > 0. This yields F jk = F ik < F ij , which violates the ultrametric inequality. Hence, we infer that (ij|k) ∈ r(E) and thus r(D) ⊆ r(E). The reverse inclusion follows from exchanging D with E.  It follows from the construction that the tropical supertree of trees with the same set of taxa is exactly the tropical median consensus tree from [7, §5]. This is the case if and only if each edge length is strictly smaller than the parameter M.
Theorem 7 includes an effective method to construct supertrees; this is listed as Algorithm 1. We want to assess its worst case complexity. The value for M selected in the algorithm is a generous upper bound of the bound from Theorem 5; it can be computed in O(mn 2 ) time. Extending the tree distances to the combined set of all taxa L needs also O(mn 2 ) operations. The dominating step is the construction of the tropical median consensus tree at the very end of the procedure; this is [7,Theorem 17]. The worst case running time is of order O(n 4 m log 2 m) by [7,Corollary 15]. The key idea of that algorithm is to reduce computing tropical medians to a transportation problem, which can be solved by the network simplex algorithm [1, §11.5]. We summarize our findings as follows.  Note that (4) defines an open tropical half-space [11,Chapter 6]. Consequently, the set T(L; X < Y ) of trees with the nesting X < Y is tropically convex. Note that rooted triplets are particular cases of nestings. A supertree method is called Pareto on nestings is the output tree displays any nesting that appears in all the input trees; cf. [18].
Proposition 9. The tropical supertree method is Pareto on nestings.
Proof. Consider any nesting X < Y which appears in all the input trees T 1 , . . . , T m . Then the corresponding ultrametrics D (1) (M), . . . , D (m) (M) on L, the combined set of taxa, lie in T(L; X < Y ). As T(L; X < Y ) is tropically convex, the tropical supertree c(M) lies in T(L; X < Y ) for M sufficiently large. This shows that c(M) displays the nesting X < Y . Figure 1 shows a tropical supertree generated from three trees on a total of five taxa.

Conclusion
The proof of Theorem 5, about the dependence of the tropical Fermat-Weber set FW(V (M)) on the parameter M, exploits basic complexity bounds concerning triangulations of products of simplices. It seems worth-while to have a closer look at the secondary fan: Applied to phylogenetic trees, the answer to the question above will also give a better understanding of the possible tree topologies of the tropical supertree c(M) as M varies. If M is seen as a measure of uncertainty, the knowledge of tree topologies before stabilization might strengthen or reveal new relationships between the taxa.
In view of [2] the restriction to equidistant trees is natural in the tropical setting. Yet from an application point of view this is quite restrictive.
Question 11. Does the tropical supertree method admit a natural generalization to non-equidistant trees?