Suppose I have a weighted directed graph, often with symmetric links. I was to compute a maximum weight spanning DAG subgraph that is connected. I can't find any references to anything like this, an it's not obviously trivial to me.
To me, this sounds like the maximization version of the minimum feedback arc set problem. The feedback arc set problem is believed to be NP-Hard, and also APX-hard. For general graphs, I believe there is a O(log n log log n) approximation algorithm in .
Divide-and-conquer approximation algorithms via spreading metrics G. Even, S. Naor, S. Rao, B. Shrieber Journal of the ACM, 2000.