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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

To me, this sounds like the maximization version of the minimum feedback arc set problem. The feedback arc set problem is believed to be NPHard, and also APXhard. For general graphs, I believe there is a O(log n log log n) approximation algorithm in [1]. Divideandconquer approximation algorithms via spreading metrics G. Even, S. Naor, S. Rao, B. Shrieber Journal of the ACM, 2000. 


You might try: Exact arborescences, matchings and cycles by Francisco Barahona and William R. Pulleyblank Discrete Applied Mathematics Volume 16, Issue 2, February 1987, Pages 9199 

