Comparing and computing distances between phylogenetic trees are important biological problems, especially for models where edge lengths play an important role. The geodesic distance measure between two phylogenetic trees with edge lengths is the length of the shortest path between them in the continuous tree space introduced by Billera, Holmes, and Vogtmann. This tree space provides a powerful tool for studying and comparing phylogenetic trees, both in exhibiting a natural distance measure and in providing a euclidean-like structure for solving optimization problems on trees. An important open problem is to find a polynomial time algorithm for finding geodesics in tree space. This paper gives such an algorithm, which starts with a simple initial path and moves through a series of successively shorter paths until the geodesic is attained.

Abstract The Shortest Path with Recourse Problem involves finding the shortest expected‐length paths in a directed network, each of whose arcs have stochastic traversal lengths (or delays) that become known only upon arrival at the tail of that arc. The traveler starts at a given source node and makes routing decisions at each node in such a way that the expected distance to a given sink node is minimized. We develop an extension of Dijkstra's algorithm to solve the version of the problem where arclengths are nonnegative and reset after each arc traversal. All known no‐reset versions of the problem are NP‐hard. We make a partial extension to the case where negative arclengths are present. © 2003 Wiley Periodicals, Inc.

This paper considers counting problems associated with K-spanning and K-disconnecting sets for a specified terminal set K in an undirected graph G. In particular, we consider the problems of computing the number of Steiner trees and minK-cuts for G, as well as K-spanning and K-disconnecting sets of cardinality close to the minimum values. Among other things, these numbers are critical to the efficient approximation of K-connected reliability measures in stochastic networks. Although the counting problems considered in this paper are NP-hard in general, a large number of methods for finding shortest paths, min cuts, and Steiner trees in graphs can be extended to efficiently countK-spanning and K-disconnecting sets in important special cases.

Abstract This paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. In each model, the arcs randomly and independently take on two possible states–an “operating” state and a “failed” state–corresponding to two different capacity/task‐time values, and the network is required to maintain a specified “threshold” max‐flow/project‐completion‐time value. In general, this problem is NP‐hard. We address the special case in which the difference between the lower and higher arc lengths is constant for every arc in the network. For these special cases, we show that if the underlying system is 1‐critical, i.e., minimally able to withstand a single component failure, then the probability that the system can maintain the required threshold for the flow and planar project scheduling model is computable in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path or, equivalently, that the set of failed elements in a given partial order comprises a chain in that order. We also show how the basic approach can be used to generate bounds for systems that are “almost critical”.

Abstract This paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.

Abstract An exact cut in a source‐sink network is a set of arcs which interesects each source‐sink path in exactly one arc. This paper investigates the problem of finding a maximum weight exact cut in a network. The problem is shown to be polynomially equivalent to that of determining the relevant arcs (arcs on at least one source‐sink path) in the network and is NP‐hard for general directed networks. There are, however, several important classes of network—including undirected networks—for which polynominal time algorithms do exist to solve the maximum weight exact cut problem.

Abstract We investigate the role convexity plays in the efficient solution to the Steiner tree problem. In general terms, we show that a Steiner tree problem is always computationally easier to solve when the points to be connected lie on the boundary of a “convex” region. For the Steiner tree problem on graphs and the rectilinear Steiner tree problem, we give definitions of “convexity” for which this condition is sufficient to allow a polynomial algorithm for finding the optimal Steiner tree. For the classical Steiner tree problem, we show that for the standard definition of convexity, this condition is sufficient to allow a fully polynomial approximation scheme.

We consider the problem of constructing a Steiner minimal tree connecting a given set K of points and lying inside a polygonally bounded, not necessarily simply connected region R in the plane. We first define the path-convex hull of K in R, which is a “sufficiently small” subregion of R guaranteed to contain the Steiner minimal tree. We then give an $\varepsilon $-approximation scheme to find the Steiner minimal tree in R by reducing it to a Steiner tree problem on a “visibility graph” associated with K and the path-convex hull of R. This will be a fully polynomial approximation scheme when K is restricted to lie on a small number of interior points and boundary polygons of R. Several techniques are given which further reduce the region in which the Steiner minimal tree is known to lie, and which extend known results for the Steiner minimal tree problem without obstacles.

We show that the problem of computing source-sink reliability is NP-hard, in fact # P-complete, even for undirected and acyclic directed source-sink planar graphs having vertex degree at most three. Thus the source-sink reliability problem is unlikely to have an efficient algorithm, even when the graph can be laid out on a rectilinear grid.

Abstract In this article, computational procedures are presented for generating bounds on measures of network reliability. The two measures considered, reachability and connectedness, are the probability that there is an operating path from a node to all other nodes in a directed (respectively undirected) stochastic network. Our bounds, which are given in terms of polynomials in p , the common arc failure probability, are based on recent bounding results developed by the authors for the class of shellable independence systems. Two pairs of bounds are given: weaker bounds whose computation time is bounded by a polynomial in the size of the network and tighter bounds whose computation time is bounded by a polynomial in the size of the network and the number of minimum‐cardinality network cuts. Computational results are also given which evaluate the quality of the bounds. The generation of the bounds involves several interesting path and cut counting problems.

Several enumeration and reliability problems are shown to be # P-complete, and hence, at least as hard as NP-complete problems. Included are important problems in network reliability analysis, namely, computing the probability that a graph is connected and counting the number of minimum cardinality $(s,t)$-cuts or directed network cuts. Also shown to be # P-complete are counting vertex covers in a bipartite graph, counting antichains in a partial order, and approximating the probability that a graph is connected and the probability that a pair of vertices is connected.