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

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.

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer
    
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.