Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

Question

I have a directed acyclic graph that has uniform edge weights. I would like to extract from this graph a spanning tree (an arborescence) with the property that the total distance between all pairs of leaf nodes (the sum of combined distances from each pair's nearest common ancestor) is minimized.

What I'm ultimately trying to accomplish is to find the best way of ordering the leaf nodes in such a way that the most closely related nodes are closest to each other in the list. If I can find the spanning tree as described, I can easily order the leaf nodes in the way I need.

Can anyone point me to a solution to this problem other than just brute force optimization?

Note that the tree that I seek does not need to span all nodes in the graph, only all leaf nodes and the root node. Also I'm willing to adopt a solution that is not globally optimal if it avoids the need for a brute force search. At the moment I'm investigating an approach involving searching and pruning paths beginning at the leaf nodes.

Answer 1

Your problem is similar to the directed Steiner tree problem. In this problem we are given a directed graph, a set of terminal vertices and a specified root. The goal is to find a minimum cost tree that connects all terminal vertices to the root.

This is not exactly what you are asking for, but perhaps a solution to such a problem (or a suitable variant) is good enough.