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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ By symmetric links you mean two edges from a to b and b to a that have the same weight ? $\endgroup$– Suresh VenkatJul 14, 2010 at 18:06
-
$\begingroup$ 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".) $\endgroup$– Ryan WilliamsJul 15, 2010 at 1:00
-
$\begingroup$ An arborescense is a tree btw. There has to be a unique path from the root to all nodes. $\endgroup$– Suresh VenkatJul 15, 2010 at 21:30
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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". $\endgroup$ Jul 15, 2010 at 1:00
$\begingroup$
$\endgroup$
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
answered Jul 14, 2010 at 16:24