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?

Update: I should correct/clarify one point in the problem statement. 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.

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.

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?

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?

Update: I should correct/clarify one point in the problem statement. 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.