ICS Theory Group

ICS 269, Spring 1997: Theory Seminar

4 Apr 1997:
Parametric Minimum Spanning Trees and Constructive Solid Geometry
David Eppstein, ICS, UC Irvine

If one is given a graph in which each edge e is labeled with a linear function fe(x) =  aex +  be, one can derive a sequence of spanning trees by plugging in different values of x and computing the minimum spanning tree of the resulting function values. I have two papers on this subject: "Using Sparsification for Parametric Minimum Spanning Tree Problems" (with D. Fernández-Baca and G. Slutzki) shows how to compute this sequence in time O(mn log n), and "Geometric Lower Bounds for Parametric Matroid Optimization" derives a lower bound of Omega(m alpha(n)) on the number of trees in this sequence. However this lower bound is still quite far from the known upper bound of O(m sqrt n).

In this talk I describe ongoing work on my attempts to improve this lower bound. Instead of considering the minimum spanning tree itself, I consider the quantity

q(x) = minpath p maxedge e of p fe(x)
where the minimum is over all paths in the graph that connect two specified terminals s and t. Equivalently, this quantity is the weight of the heaviest edge of the path from s to t in the MST.

Geometrically, the shape formed by plotting q(x) against x is a lower envelope (min) of an upper envelope (max) of certain sets of lines (plots of each individual edge weight). The upper envelope of lines is a concave chain, so q(x) is the lower envelope of certain concave chains. It forms a monotone path in the line arrangement (monotone simply means that it is the plot of a function, having only one intersection with any vertical line). The convex vertices in this path correspond to minimum spanning tree changes, although the concave vertices may not.

My first attempt to prove a better lower bound on the number of minimum spanning trees starts from a construction of Matousek, who showed that monotone paths in arrangements may have complexity Omega(m5/3) (no nontrivial upper bound is known). Since Matousek's lower bound on monotone paths is larger than our known upper bound on minimum spanning trees, there are some monotone paths that do not correspond to minimum spanning tree sequences. I tried a simplified example in which m lines are partitioned into sqrt m "cables" of sqrt m lines each, with an additional m lines connecting up the intersections of pairs of cables in such a way that each intersection contributes sqrt m vertices (both convex and concave) to the monotone path. It is possible to represent this monotone path as a lower envelope of a simple family of concave chains, however when I tried to translate this family back into graph-theoretic terms I ended up with "coat-hangers" (triangles with a dangling edge) instead of paths.

Instead, I tried restricting the problem further, to paths in series-parallel graphs. Series composition corresponds to forming q(x) as the upper envelope of two paths coming from the two subgraphs being composed, and parallel composition corresponds to a lower envelope. Therefore, one can re-interpret the problem as a form of "constructive solid geometry" for monotone paths: one is given a set of monotone paths, initially just m lines, and can repeatedly perform operations that combine two paths, replacing the two by a single upper or lower envelope. How complex a path can result from this process? The bounds I currently know are exactly those for the original parametric MST problem, Omega(m alpha(n)) and O(m sqrt n).

In summary, I still haven't made progress in narrowing the gap between lower and upper bounds for parametric MSTs, but at least I've found some interesting ways of translating the problem into some geometric formulations that don't look like they should have anything to do with MSTs.