# Algorithms for maximum weighted spanning (connected) dag (directed acyclic graph)

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.

• By symmetric links you mean two edges from a to b and b to a that have the same weight ? – Suresh Venkat Jul 14 '10 at 18:06
• Here, "connected" is ambiguous. Do you mean "weakly connected" (if you were to "unorient" the edges, the remaining undirected graph is connected)? Or do you mean that there is a node s such that from s you can reach all nodes in the graph? (This is an "arborescence".) – Ryan Williams Jul 15 '10 at 1:00
• An arborescense is a tree btw. There has to be a unique path from the root to all nodes. – Suresh Venkat Jul 15 '10 at 21:30

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 [1].

Divide-and-conquer approximation algorithms via spreading metrics G. Even, S. Naor, S. Rao, B. Shrieber Journal of the ACM, 2000.

• Note that feedback arc set is NP-hard. And it does look to be about the same problem, but that really depends on what the questioner means by "connected". – Ryan Williams Jul 15 '10 at 1:00

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 91-99