How to minimize total cost of shortest path tree

Question

I have a directed acyclic graph with positive edge-weights. It has a single source and a set of targets (vertices furthest from the source). I find the shortest paths from the source to each target. Some of these paths overlap. What I want is a shortest path tree which minimizes the total sum of weights over all edges.

For example, consider two of the targets. Given all edge weights equal, if they share a single shortest path for most of their length, then that is preferable to two mostly non-overlapping shortest paths (fewer edges in the tree equals lower overall cost).

Another example: two paths are non-overlapping for a small part of their length, with high cost for the non-overlapping paths, but low cost for the long shared path (low combined cost). On the other hand, two paths are non-overlapping for most of their length, with low costs for the non-overlapping paths, but high cost for the short shared path (also, low combined cost). There are many combinations. I want to find solutions with the lowest overall cost, given all the shortest paths from source to target.

In other words, I want the shortest, shortest-path-trees.

Does this ring any bells with anyone? Can anyone point me to relevant algorithms or analogous applications?

Cheers!

Answer 1

This problem (Steiner Tree) is NP-hard and max SNP-complete, so there are neither polynomial-time algorithms nor PTAS (arbitrarily close approximations) unless P = NP.

The MST can give a weight arbitrarily worse than optimal, unless you know some special feature of your graph (e.g. the graph is planar, or at least that the weights obey the triangle inequality). For example, if you have K_1,000,000,001 with all edge weights 1 and only one target, the optimal solution has weight 1 and the MST has weight 1,000,000,000.

If you assume that all edges between targets and all edges between the source and each target exist, you can still overshoot by an arbitrary factor. Consider the above example, but change the edge weight between the target and source to 2,000,000,000,000,000,000 (you're still off by a factor of a billion from optimal).

Of course you can transform the graph to 'remove' edge weights that are high in time O(E) or so by traversing the graph. This plus a MST of the set of targets and source gives an approximation ratio of 2.

Better approximation ratios exist. Robins & Zelikovsky have a polynomial-time algorithm that is never more than 54.94% worse than optimal: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik & Chlebikova show that approximating closer than 1.05% is NP-hard: The Steiner tree problem on graphs: Inapproximability results (doi 10.1.1.4.1339)

If your graph is planar, the situation is better. There's a fast algorithm that gives an arbitrarily-close approximation due to Borradaile, Kenyon-Mathieu & Klein (building on Erickson, Monma, & Veinott): An O(nlogn) approximation scheme for Steiner tree in planar graphs (doi 10.1.1.133.4154)