A Stronger Lower Bound on Parametric Minimum Spanning Trees

Abstract

We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter $\lambda$, the number of different minimum spanning trees obtained as the parameter varies can be $\varOmega (m\log n)$.

1 Introduction

In the parametric minimum spanning tree problem [16], the input is a graph G whose edges are labeled with linear functions of a parameter $\lambda$. For any value of $\lambda$, one can obtain a spanning tree $T_\lambda$ as the minimum spanning tree of the weight functions, evaluated at $\lambda$. Varying $\lambda$ continuously from $-\infty$ to $\infty$ produces in this way a discrete sequence of trees, each of which is minimum within some range of values of $\lambda$. How many different spanning trees can belong to this sequence, for a worst case graph, and how can we construct them all efficiently? Known bounds are that the number of trees in a graph with n vertices and m edges can be $\varOmega \bigl (m\alpha (n)\bigr )$ (where $\alpha$ is the inverse Ackermann function) [9] and is always $O(mn^{1/3})$ [7]; both bounds date from the 1990s and, although far apart, have not been improved since. The sequence of trees can be constructed in time $O(mn\log n)$ [13] or in time $O(n^{2/3}\log ^{O(1)} n)$ per tree [1]; faster algorithms are also known for planar graphs [12] or for related optimization problems that construct only a single tree in the parametric sequence [6, 19]. In this paper we improve the 25-year-old lower bound on the number of parametric minimum spanning trees from $\varOmega \bigl (m\alpha (n)\bigr )$ to $\varOmega (m\log n)$.

A broad class of applications of this problem involves bicriterion optimization, where each edge of a graph has two real weights of different types (say, investment cost and eventual profit) and one wishes to find a tree optimizing a nonlinear combination of the sums of these two weights (such as the ratio of total profit to total investment cost, the return on the investment). Each spanning tree of G may be represented by a planar point whose Cartesian coordinates are the sums of its two kinds of weights, giving an exponentially large cloud of points, one per tree. The convex hull of this point cloud has as its vertices the parametric minimum spanning trees (and maximum spanning trees) for linear weight functions obtained from the pair of weight values on each edge by using these values as coefficients. (Essentially, this construction of weight functions from pairs of weights is a form of projective duality transforming points into lines, and the equivalence between the convex hull of the points representing trees into the lower envelope of lines representing their total weight is a standard reflection of that projective duality.) Any bicriterion optimization problem that can be expressed as maximizing a quasiconvex function (or minimizing a quasiconcave function) of the two kinds of total weight automatically has its optimum at a convex hull vertex, and can be solved by constructing the sequence of parametric minimum spanning trees and evaluating the combination of weights for each one [18]. Other combinatorial optimization problems that have been considered from the same parametric and bicriterion point of view include shortest paths [3,4,5, 11], optimal subtrees of rooted trees [2], minimum-weight bases of matroids [9], minimum-weight closures of directed graphs [10], and the knapsack problem [8, 15, 17].

The main idea behind our new lower bound is a recursive construction of a family of graphs (more specifically, 2-trees), formed by repeated replacement of edges by triangles (Fig. 1). We also determine the parametric weight functions of these graphs by a separate recursive construction (Fig. 3). However, this only produces an $\varOmega (n\log n)$ lower bound, because for a graph constructed in this way with n vertices, the number of edges is $2n-3$, only a constant factor larger than the number of vertices. To obtain our claimed $\varOmega (m\log n)$ lower bound we use an additional packing argument, in which we find a dense graph containing many copies of our sparse lower bound construction, each contributing its own subsequence of parametric minimum spanning trees to the total.

2 Background and Preliminaries

The minimum spanning tree of a connected undirected graph with real-valued edge weights is a tree formed as a subgraph of the given graph, having the minimum possible total edge weight. As outlined by Tarjan [22], standard methods for constructing minimum spanning trees are based on two rules, stated most simply for the case when all edge weights are distinct. The cut rule concerns cuts in the graph, partitions of the vertices into two subsets; an edge spans a cut when its two endpoints are in different subsets. The cut rule states that (for distinct edge weights) the minimum-weight edge spanning any given cut in a graph belongs to its unique minimum spanning tree. The cycle rule, on the other hand, states that (again for distinct edge weights) the maximum-weight edge in any cycle of the graph does not belong to its unique spanning tree. One consequence of these rules is that the minimum spanning tree depends only on the sorted ordering of the edge weights, rather than on more detailed properties of their numeric values.

An input to the parametric minimum spanning tree problem consists of an undirected connected graph whose edges are labeled with linear functions of a parameter $\lambda$ rather than with real numbers. For any value of $\lambda$, plugging $\lambda$ into these functions produces a system of real weights for the edges, and therefore a minimum spanning tree $T_\lambda$. Different values of $\lambda$ may produce different trees, and the task is either to obtain a complete description of which tree is minimum for each possible value of $\lambda$ or, in some versions of the problem, to find a value $\lambda$ and its tree optimizing another objective function.

If we plot the graphs of the linear functions of a parametric minimum spanning tree instance, as lines in the $(\lambda ,\text {weight})$ plane, then the geometric properties of this arrangement of lines are closely related to the combinatorial properties of the parametric minimum spanning tree problem. If no two edges have the same weight function, then all edge weights will be distinct except at a finite set of values of $\lambda$, the $\lambda$-coordinates of points where two lines in the arrangement cross. As $\lambda$ varies continuously, the sorted ordering of the weights will remain unchanged except when $\lambda$ passes through one of these crossing points, where the set of lines involved in any crossing will reverse their weight order. It follows from these considerations that the sequence of parametric minimum spanning trees is finite, and that these trees change only at certain breakpoints which are necessarily the $\lambda$-coordinates of crossings of lines. In particular, m lines have $O(m^2)$ crossings and there can be only $O(m^2)$ distinct trees in the sequence of parametric minimum spanning trees. However, a stronger bound, $O(mn^{1/3})$, is known [7].

The worst-case instances of the parametric minimum spanning tree problem, the ones with the most trees for their numbers of edges and vertices, have distinct edge weight functions whose arrangement of lines has only simple crossings, crossings of exactly two lines. For, in any other instance, perturbing the edge weight functions by a small amount will preserve the ordering of weights away from the crossings of its lines, and therefore will preserve its sequence of trees away from these crossings, while only possibly increasing the number of breakpoints near perturbed crossings of multiple lines, which become multiple simple crossings. For an instance in which the lines have only simple crossings, the only possible change to the minimum spanning tree at a breakpoint is a swap, a change to the tree in which one edge (corresponding to one of the two crossing lines at a simple crossing) is removed, and the other edge (corresponding to the other of the two crossing lines) is added in its place. For details on this correspondence between the geometry of line arrangements and the sequence of parametric minimum spanning trees, and generalizations of this correspondence to other matroids than the matroid of spanning trees, see our previous paper on this topic [9].

3 Replacing Edges by Triangles

A 2-tree is a graph obtained from the two-vertex one-edge graph $K_2$ by repeatedly adding new degree-two vertices, adjacent to pairs of adjacent earlier vertices. Equivalently, they are obtained by repeatedly replacing edges by triangles. These graphs are planar and include the maximal outerplanar graphs [20]; their subgraphs are the partial 2-trees, graphs of treewidth $\le 2$ [23]. The graphs we use in our lower bound are a special case of this construction where we apply this edge replacement process simultaneously to all edges in a smaller graph of the same type. We define the first graph $T_0$ in our sequence of graphs to be the graph $K_2$, and then for all $i>0$ we define $T_i$ to be the graph obtained by replacing all edges of $T_{i-1}$ by triangles. It seems natural to call these complete 2-trees, by analogy to complete trees (whose leaves are repeatedly replaced by stars for a given number of levels) but we have been unable to find this usage in the literature. The graphs $T_i$ for $i\le 3$ are depicted in Fig. 1.

Lemma 1

$T_i$ has $3^i$ edges and $(3^i+3)/2$ vertices.

Proof

The bound on the number of edges follows from the fact that each replacement of edges by triangles triples the number of edges. The bound on the number of vertices follows easily by induction on i, using the observations that each edge of $T_{i-1}$ leads to a newly added vertex in $T_i$ and that $(3^{i-1}+3)/2+3^{i-1}=(3^i+3)/2$.    $\square$

What happens when we replace an edge by a triangle in a parametric spanning tree problem? For a non-parametric minimum spanning tree, the answer is given by the following lemma.

Lemma 2

Let graph G contain edge pq, and replace this edge by a triangle pqr to form a larger graph $G^+$. Suppose that the edges in $G^+$ have distinct edge weights, and use these weights to assign weights to the edges in G, with the following exception: in G, give edge pq the weight of the bottleneck edge in triangle pqr (the maximum-weight edge on path from p to q in the minimum spanning tree of the graph of the triangle) instead of the weight of pq. Then, the minimum spanning tree of $G{+}$ has the same set of edge weights as the minimum spanning tree of G, together with the minimum weight of a non-bottleneck edge in triangle pqr.

Fig. 1.

Recursively constructing a family of 2-trees $T_i$ (here, $i=0,1,2,3$ in left-to-right order) by repeatedly replacing every edge of $T_{i-1}$ by a triangle.

Proof

If pq is the heaviest edge in pqr then the path from p to q in the minimum spanning tree of pqr passes through r, the bottleneck edge is the heavier of the two edges on this path, and the minimum non-bottleneck edge is the lighter of its two edges. Otherwise, pq is the bottleneck edge and again the minimum non-bottleneck edge is the lighter of the two remaining edges incident to r. Applying the cut rule to the cut separating r from the rest of the graph shows that the minimum non-bottleneck edge is an edge of the minimum spanning tree of $G^+$. Since we did not include its edge weight in the weights for G, its weight is not included in the set of edge weights of the minimum spanning tree for G.

Contracting this minimum non-bottleneck edge in $G^+$ produces a multigraph with two copies of edge pq, the lighter of which is the bottleneck edge. Therefore, if we keep only the lighter of the two edges, we obtain the weighting on G as a contraction of a minimum spanning tree edge in $G^+$. This contraction preserves the set of remaining minimum spanning tree weights, as the lemma states.    $\square$

Fig. 2.

A parametric spanning tree problem on a single triangle pqr, and the graph of the bottleneck edge weight on the path from p to q in the parametric spanning tree, as a function of the parameter $\lambda$. (Color figure online)

It follows that in the parametric case, replacing an edge pq by a triangle pqr, with linear parametric weights on each triangle edge, causes that edge to behave as if it has a nonlinear piecewise linear weight function attached to it, the function mapping the parameter $\lambda$ to the bottleneck weight from p to q in triangle pqr. Figure 2 shows an example of three parametric weights on a triangle pqr and this bottleneck weight function, with the weights chosen so that the function has three breakpoints. Clearly, we can perturb these three weight functions within small neighborhoods of their coefficients, and obtain a qualitatively similar bottleneck weight function.

Fig. 3.

Recursive construction for the parametric weight functions of the graphs $T_i$, shown here as an arrangement of lines in a plane whose horizontal coordinate is the parameter $\lambda$ and whose vertical coordinate is the edge weight at that parameter value. The reversed text in the central recursive construction indicates that the construction is reversed left-to-right relative to the other two copies.

4 Weighted 2-Trees

We now describe how to assign parametric weights to the edges of $T_i$ to obtain our $\varOmega (n\log n)$ lower bound. As a base case, we may use any linear function as the weight of the single edge of $T_0$; it can have only one spanning tree, regardless of this choice. For $T_i$, with $i>0$, we perform the following steps to assign its weights:

• Construct the weight functions for the edges of $T_{i-1}$, recursively.

• Apply a linear transformation to the parameter of these weight functions (the same transformation for each edge) so that, in the arrangement of lines representing the graphs of these weight functions, all crossings occur in the interval [0, 1] of $\lambda$-coordinates. Additionally, scale these weight functions by a sufficiently small factor $\epsilon$ so that, within this interval, they are close enough to the $\lambda$-axis, for a meaning of “close enough” to be specified below.

• Construct $T_i$ by replacing each edge pq in $T_{i-1}$ by a triangle pqr, with a new vertex for each triangle. Color the three edges of each triangle red, blue, and green, as in Fig. 2(left), with pq colored green and the other two edges colored red and blue (choosing arbitrarily which one to color red and which one to color blue).

• Give each edge of $T_i$ a transformed copy of the weight function of the corresponding edge of $T_{i-1}$, transformed as follows:

  • For a green edge pq, corresponding to an edge of $T_{i-1}$ with weight function $f(\lambda )$, give pq the weight function $f(\lambda -4.5)+3$. This transformation shifts the part of the weight function where the crossings with other green edges occur to be close to the right green segment of Fig. 2(right).

  • For a red edge pr, corresponding to an edge pq of $T_{i-1}$ with weight function $f(\lambda )$, give pr the weight function $f(3.75-\lambda )+\lambda -1$. This transformation shifts the part of the weight function where the crossings with other red edges occur to be close to the red segment of Fig. 2(right), and (by negating $\lambda$ in the argument to f) reverses the ordering of the crossings within that region.

  • For a blue edge qr, corresponding to an edge pq of $T_{i-1}$ with weight function $f(\lambda )$, give qr the weight function $f(\lambda -1.25)+4-\lambda$. This transformation shifts the part of the weight function where the crossings with other red edges occur to be close to the blue segment of Fig. 2(right).

• Perturb all of the weight functions, if necessary, so that all crossings of two weight functions have different $\lambda$-coordinates, without changing the left-to-right ordering of the crossings between any one weight function and the rest of them.

This construction is depicted schematically, in the $(\lambda ,\text {weight})$ plane, in Fig. 3. We are now ready to define what it means for the weight scaling factor $\epsilon$ to be small enough, so that the scaled weight functions are “close enough” to the $\lambda$ axis: as shown in the figure, the left-to-right ordering of the crossings of the lines graphing the weight functions should be:

• 1. All crossings of blue with green lines

• 2. All crossings of two blue lines, in one copy of the recursive construction

• 3. All crossings of blue with red lines

• 4. All crossings of two red lines, in a second (reversed) copy of the recursive construction

• 5. All crossings of red with green lines

• 6. All crossings of two green lines, in the third copy of the recursive construction

Our construction automatically places all monochromatic crossings into disjoint unit-length intervals with these orderings. The bichromatic crossings of Fig. 2 are separated from these unit-length intervals by a horizontal distance of at least 0.25, and sufficiently small values of $\epsilon$ will cause the bichromatic crossings of $T_i$ to be close to the positions of the crossings with the same color in Fig. 2. Therefore, by choosing $\epsilon$ small enough, we can ensure that the crossing ordering described above is obtained. Figure 4 depicts this construction for $T_2$.

We observe that, within each of the unit-length intervals containing a copy of the recursive construction, the bottleneck edges for each triangle pqr in the construction of $T_i$ are exactly the ones of the color for that copy of the recursive construction, and that within these intervals, the minimum non-bottleneck edge in each triangle does not change. Therefore, by Lemma 2, the changes in the sequence of parametric minimum spanning trees within these intervals exactly correspond to the changes in the trees of $T_{i-1}$ from the recursive construction.

Fig. 4.

$T_2$ (upper right) as parametrically weighted in our construction, with the graphs of each weight function shown as lines in the $(\lambda ,w)$ plane (upper right), and the resulting sequence of 12 parametric minimum spanning trees (bottom). The marked yellow crossings of pairs of lines correspond to breakpoints in the sequence of trees. (Color figure online)

Lemma 3

For weights constructed as above, the number of distinct parametric minimum spanning trees for $T_i$ is at least as large as

$$ N(i)=\frac{i3^i}{2}+\frac{3^i+3}{4}. $$

Proof

We prove by induction on i that the number of trees is at least as large as the solution to the recurrence

$$ N(i) = 3N(i-1) + \frac{3^i-3}{2}. $$

To prove this, it is easier to count the number of breakpoints, values of $\lambda$ at which the tree structure changes; the number of trees is the number of breakpoints plus one. In each copy of the recursive construction, this number of breakpoints is exactly $N(i-1)-1$, so the total number of breakpoints appearing in these three copies is $3N(i-1)-3$.

Additional breakpoints happen within the ranges of values for $\lambda$ at which (in the $(\lambda ,\text {weight})$ plane) pairs of lines of two different colors cross. Because of the reversal of the red copy of the recursive construction, the minimum spanning trees immediately to the left and right of these regions of bichromatic crossings correspond to the same trees in $T_{i-1}$: the bottleneck edges that are included in these minimum spanning trees come from the same triangles, but with different colors. In the regions where the green lines cross lines of other colors, the minimum non-bottleneck edge in each triangle does not change, so each green bottleneck edge in the minimum spanning tree must be exchanged for a red or blue one. Each change to a tree within this crossing region removes a single edge from the minimum spanning tree and replaces it with another single edge, the two edges whose two lines cross at the $\lambda$-coordinate of that change. Therefore, no matter what sequence of changes is performed, to exchange all green bottleneck edges for all red or blue ones requires a number of crossings equal to the number of edges in the minimum spanning tree of $T_{i-1}$, which is $(3^{i-1}+1)/2$ by Lemma 1. We get this number of breakpoints at the region where the green and blue lines cross, and the same number at the region where the red and green lines cross.

The analysis of the number of breakpoints at the region where the blue and red lines cross is similar, but slightly different. Immediately to the left and right of this region, the bottleneck edge in each triangle and the minimum non-bottleneck edge in the triangle are red and blue, but in a different order to the left and to the right. Therefore, in triangles where the bottleneck edge is part of the minimum spanning tree (as is always the minimum non-bottleneck edge), nothing changes. However, in triangles where the bottleneck edge is not part of the minimum spanning tree, there is a change, to the minimum non-bottleneck edge, from before this crossing region to after it. These triangles correspond to edges of $T_{i-1}$ which do not belong to the minimum spanning tree (for the parameter values in this range), of which there are $(3^{i-1}-1)/2$ by Lemma 1. By the same argument as before, the crossing region must contain at least this many breakpoints.

Adding together the $3N(i-1)-3$ breakpoints from the recursive copies, the $(3^{i-1}+1)/2$ breakpoints for the green–red and green–blue crossing regions, the $(3^{i-1}-1)/2$ breakpoints for the red–blue crossing region, and $+1$ to convert numbers of breakpoints to numbers of distinct trees, and simplifying, gives the right hand side of the recurrence. A straightforward induction shows that the solution to the recurrence is the formula given in the statement of the lemma.    $\square$

For $i=0,1,2,\dots$ the number of trees given by this formula is

$$ 1, 3, 12, 48, 183, 669, 2370, 8202, 27885, 93495 \dots $$

For instance, $T_1$ has three trees with the weighting given in Fig. 2: the bottleneck function shown in the figure has four linear pieces, but the red and blue pieces both correspond to the same tree, with a different edge on the path pqr as the bottleneck edge. Figure 4 shows the 12 trees for $T_2$.

5 Packing into Dense Graphs

The lower bound obtained from Lemma 3 applies only to sparse graphs, where the numbers of vertices and edges are within constant factors of each other. However, we want a bound that applies more generally, for graphs with significantly more edges than vertices. The other direction, for graphs with significantly fewer edges than vertices, is less interesting. To achieve many fewer edges than vertices, it is necessary to allow disconnected graphs, and consider minimum spanning forests instead of minimum spanning trees; but with these modifications one can obtain a lower bound simply by adding isolated vertices to the construction of Lemma 3.

To achieve many more edges than vertices, we use the following construction for packing many instances of a sparse lower bound graph into a single denser graph. It does not require any detailed knowledge of the structure of the sparse graph.

Fig. 5.

The construction of Lemma 4, applied to a graph G with four vertices and four edges (left), with the parameter $k=3$. The central graph is a subdivision of each edge of this graph into a four-edge path, with vertices labeled as shown, and the graph on the right is the final construction H, with the colors and textures of edges indicating the partition of its edges into four subgraphs $H_0$ (thin black edges), $H_1$ (thick yellow edges), $H_2$ (dotted blue edges), and $H_3$ (dashed red edges). (Color figure online)

Lemma 4

Let G be a parametrically weighted graph with N vertices and M edges, whose sequence of parametric minimum spanning trees has length T, and let k be a positive integer satisfying $k\le M$. Then there is a parametrically weighted graph H with $N+3M$ vertices and $(2k+2)M$ edges whose sequence of parametric minimum spanning trees has length at least 2kT.

Proof

We construct H from G in the following steps, illustrated in Fig. 5.

• Number the edges of G as $e_0, e_2,\dots e_{M-1}$ arbitrarily.

• Subdivide each edge $e_i$ of G, connecting two vertices u and v, into a four-edge path u–$a_i$–$b_i$–$c_i$–v. (It is arbitrary which vertex of this path we call $a_i$ and which we call $c_i$.)

• Add additional edges from $b_i$ to $a_j$ and $c_j$, for each i and each $j=i+1,i+2,\dots i+k-1\bmod {M}$.

Given this construction, we define subgraphs $H_j$ as follows:

• $H_0$ consists of all edges connecting vertices of G to new vertices $a_i$ or $c_i$.

• $H_j$ consists of all edges from $b_i$ to $a_{i+j-1}$ or $c_{i+j-1}$, for all i, with indexes taken modulo m.

Then, for $i=1,2,\dots k$, the graph $H_0\cup H_i$ is isomorphic to a subdivision of G, with $H_0\cup H_1$ being the subdivision we used to construct H and the others obtained in the same way but with permuted connections.

Fig. 6.

An arrangement of lines for the weight functions of Lemma 4 with $k=3$. The small rectangles indicate transformed neighborhoods of the unit $\lambda$-interval, containing all crossings of the bundle of lines associated with each subgraph.

As in Lemma 3, we flatten the arrangement of lines for the weighting of G so that its crossings all lie within a small neighborhood of the unit interval of the $\lambda$-axis, without changing its sequence of parametric minimum spanning trees. We then apply linear transformations to the system of weights for the edges in each copy $H_j$ with $j>0$, as detailed below, while using small-enough weights for all edges in $H_0$ so that these edges belong to all minimum spanning trees for parameters in the range covered by the transformed unit intervals shown in Fig. 6. More specifically, for each $j>0$ we use one transformed copy of the weights in G for the a–b edges in $H_j$, and a second transformed copy for the b–c edges, arranged so that the transformed unit intervals containing the crossings within each copy project to disjoint intervals of the $\lambda$-axis, and so that all crossings of the a–b edges appear above all lines for the b–c edges and vice versa. Therefore, in the graph $H_0\cup H_j$, the parametric trees in the parameter range where the a–b edges cross each other consist of all b–c edges (because those have smaller weight than the a–b edges in each path) together with a subset of the a–b edges corresponding to a spanning tree of G. Because we copied and transformed the weights of G for the a–b edges in this parameter range, we obtain T distinct trees of this type. To arrange the a–b and b–c parameter weights for $H_i$ in this fashion, we transform them so that the a–b weights lie near the line $w=3-\lambda$, with crossings in the range $\lambda \in [1,2]$, and so that the b–c weights lie near the line $w=\lambda -3$, with crossings in the range $\lambda \in [4,5]$. Then, we transform and flatten these combined weights of $H_i$, so that they again lie near the $\lambda$-axis with all crossings of edges of either type in the range [0, 1].

We arrange the sets of lines associated with $H_1$, $H_2$, etc., so that the lines from each $H_j$ pass above the crossings for each other $H_j'$, $j\ne j'$, and so that the range of parameters within which $H_j$ has the lowest lines contains the two subranges where its a–b lines cross and where its b–c lines cross, again as shown in the figure. We may do this by finding a convex-downward polygonal chain with k sides (for instance the upper part of a regular 2k-gon), in which all sides project to a range of $\lambda$-coordinates of more than unit length, and by transforming the weights of each $H_i$ so that the unit interval of the $\lambda$-axis, near which all crossings of these weights occur, is transformed to the interior of one of the sides of this polygonal chain. Figure 6 shows the weights for three subgraphs $H_1$, $H_2$, and $H_3$, transformed in this way so that they are near the upper three sides of a hexagon. The weights for $H_0$ can be chosen to be near a horizontal line, below all crossings of the other weight functions, as also shown in the figure.

Therefore, within these subranges, the parametric minimum spanning trees for all of H will be the same as the trees for $H_0\cup H_j$, because $H_0\cup H_j$ spans H and has lower edge weights than any of the remaining edges. With this arrangement, we get 2kT distinct parametric minimum spanning trees, 2T for each $H_j$ with $j>0$, as well as additional trees that are not counted in the lemma.    $\square$

With this, we are ready to prove our main result:

Theorem 1

There exists a constant C such that the following is true. Let n and m be integers with $n>0$ and $2n-3\le m\le \genfrac(){0.0pt}1{m}{2}$. Then there exists a parametrically weighted graph with n vertices and m edges, with at least $Cm\log n$ parametric minimum spanning trees.

Proof

Let $G=T_i$, $N=(3^i+3)/2$, and $M=3^i$, with i chosen as large as possible so that $N+3M\le n$ and $4M\le m$, and choose k as large as possible so that $(2k+2)M\le m$; then $N=\varTheta (n)$ and $M=\varTheta (m/n)$. Apply Lemma 3 to give weights to G so that it has $\varOmega (n\log n)$ parametric minimum spanning trees, and apply Lemma 4 to construct a parametrically weighted graph H with $N+3M$ vertices and $(2k+2)M$ edges that has $\varOmega (m\log n)$ parametric minimum spanning trees. If necessary, add leaf vertices to H to increase its number of vertices to n, and then add high-weight edges to increase its number of edges to m without affecting this sequence of parametric spanning trees.    $\square$

6 Conclusions

We have shown that the number of parametric minimum spanning trees can be $\varOmega (m\log n)$ in the worst case, improving a 25-year-old $\varOmega \bigl (m\alpha (n)\bigr )$ lower bound. Because of the structure of the graphs used in our lower bound construction, the new lower bound applies as well to the special cases of planar graphs and of bounded-treewidth graphs, both of which can have $\varOmega (n\log n)$ parametric minimum spanning trees. However, our new lower bound is still far from the $O(mn^{1/3})$ upper bound, so there is plenty of room for additional improvement.

Another related question concerns the parametric bottleneck shortest path problem, a parametric version of the problem of finding a path between two specified vertices that minimizes the maximum edge weight on the path. In the non-parametric version of the problem, a minimum spanning tree path is an optimal path, although faster algorithms are possible and the problem is also of interest in the case of directed graphs [14]. The same problem is also known in the equivalent maximin form as the widest path problem, where an optimal solution can be found as a maximum spanning tree path [21]. The parametric versions of these problems differ somewhat: a breakpoint in the piecewise linear parametric minimum spanning tree function (the function mapping the parameter value $\lambda$ to the weight of its minimum spanning tree) might not be a breakpoint in the bottleneck shortest path problem (the maximum weight of an edge on the bottleneck shortest path problem) or vice versa. However, the bottleneck breakpoints that look locally like the minimum of two linear functions do correspond to breakpoints of the minimum spanning tree problem. For this reason, any asymptotic lower bound on the parametric bottleneck shortest path problem would also be a lower bound for parametric minimum spanning trees, and any asymptotic upper bound on the parametric minimum spanning tree problem (including the known $O(mn^{1/3})$ bound) is also an upper bound on parametric bottleneck shortest paths. In fact, our previous $\varOmega \bigl (m\alpha (n)\bigr )$ lower bound also applies to parametric bottleneck shortest paths, but our new $\varOmega (m\log n)$ bound does not. Can we strengthen the $\varOmega \bigl (m\alpha (n)\bigr )$ bound for this problem?