How to minimize the total cost of the shortest tree path

Question

I have a directed acyclic graph with positive weights. It has a single source and a set of targets (vertices farthest from the source). I find the shortest paths from the source to each goal. Some of these paths overlap. What I want is the shortest path tree that minimizes the total weight of all the edges.

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

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

In other words, I need the shortest, shortest paths.

Does anyone ring with this ring? Can someone point me to the appropriate algorithms or similar applications?

Hooray!

Answer 1

This problem ( Steiner Tree ) is NP-hard and max SNP-complete; therefore, there are no polynomial time algorithms or PTAS (arbitrarily close approximations) if P = NP.

MST can give weight arbitrarily worse than optimal if you do not know any feature of your graph (for example, the graph is flat 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 goal, the optimal solution has a weight of 1, and MST has a mass of 1,000,000,000.

If you assume that all the edges between the targets and all the edges between the source and each target exist, you can still exceed an arbitrary coefficient. Consider the above example, but change the edge weight between the target and the original to 2,000,000,000,000,000,000 (you are still one billion from the optimal).

Of course, you can transform the graph to “remove” the weights of the edges that have a large O (E) time or so by going through the graph. This plus the MST of a set of targets and source gives an approximation coefficient of 2.

There are better approximation coefficients. Robins and Zelikovsky have a polynomial time algorithm that never exceeds 54.94% worse than optimal: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Khlebik and Khlebikova show that the approximation is closer to 1.05% NP-hard: The Steiner tree problem on the graphs: results of inadequacy (doi 10.1.1.4.1339)

If your schedule is flat, the situation is better. There's a fast algorithm that gives an arbitrarily close approximation due to Borradaile, Kenyon-Mathieu and Klein (building on Erickson, Monme and Veynote): An O (nlogn) for the Steiner tree in flat graphs (doi 10.1.1.133.4154)

Answer 2

If you have only positive costs, and you minimize, just use the Dijkstra algorithm .