CODEWITHSUNDEEP
algorithmgraphdirected-acyclic-graphssubgraph
vkaul11
vkaul11

Reputation: 4214

Algorithms for maximum weighted spanning weakly connected DAG

Is there an algorithm to find maximum weight spanning DAG that is weakly connected in a directed graph where every cut has sets that are weakly connected (There is at least one directed path from one set to another)? Or it is a NP hard problem? The previous question on this topic did not specify https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph weak or strong connectivity, so I wanted to be more precise.

Upvotes: 0

Views: 1533

Answers (2)

Ravi
Ravi

Reputation: 51

Hope thisn't too late. It is easy to fail both Kruskal and Prim for the case mentioned. Consider a 2 node graph: A --> B (weight 10), B --> A (weight 6), B --> A (weight 6) (yes: two edges from B to A; nothing in the graph defn precludes that !). Kruskal would first pick the A --> B edge and gets stuck. Prim would pick one of the edges from B to A and then gets stuck. The max. weighted acyclic subgraph is one that contains both the edges from B to A. It is a subgraph and it is acyclic !

Best Ravi

Upvotes: 5

tmyklebu
tmyklebu

Reputation: 14205

Your weak connectivity condition just seems to be that the underlying undirected graph is connected. This is easy enough; you can use Kruskal or Prim or whatever your favourite minimum spanning tree algorithm is.

Minimum-weight strongly connected subgraph is NP-complete; observe that any such subgraph has at least |V| edges and that it has exactly |V| edges if and only if it is a Hamiltonian cycle.

You may want to pick a vertex to be the "root" and ask for there to be a path from every vertex to the root in your subgraph. This is the "minimum sppaning arbourescence" problem. As @matejpavouk pointed out, there is a quadratic algorithm for this due to Chu, Liu, and Edmonds.

Upvotes: 0

Related Questions