Theoretical Computer Science
- cc.complexity-theory graph-theory np-hardness
- Updated Tue, 21 Jun 2022 03:04:27 GMT
-
Non-rooted MST of directed graph
I've found a problem that boils down to this: I need to find the non-rooted MST of a directed weighted graph. In other words, I need to find the minimal set of edges such that from any one node in the graph you can get to all others.
This is similar to the rooted MST digraph problem, which the chu-liu algorithm solves quite nicely. My intuition is to calculate the rooted MST for all nodes using chu-liu and then merge each, removing redundancies along the way. However, I don't believe that that would be optimal.
Has anybody been working on this? Can you point me towards some papers that I should read?
Thanks.
Solution
If I understand your question correctly you aren't looking for a tree, or an arborescence, but rather a minimum weight set of arcs that suffice to keep the graph strongly connected.
Your problem is NP-complete by reduction from Hamiltonian cycle problem. Given an input undirected graph that you wish to find the Hamiltonian cycle of create a directed graph by replacing each edge with a pair of oppositely directed arcs. Give all arcs weight 1. This directed graph has a set of arcs that leave the graph strongly connected with weight at most the number of vertices if and only if it has a Hamiltonian cycle.
You can get a two-approximation by picking an arbitrary root, finding the minimum weight spanning tree with arcs pointing towards the root, finding the minimum weight spanning tree with arcs pointing away from the root, and then unioning the two sets of arcs.
I don't recognize this problem off the top of my head but have you tried looking in the various NP-complete problem directories for it?
Comments (5)
- +1 – In this problem, you're allowed to visit a vertex as many times as you want. Correct me if I'm wrong, but the Hamiltonian cycle requires you visit each vertex only once. Remove that stipulation, and it's no longer NP-complete, correct? — Oct 12, 2010 at 13:41
- +2 – Hamiltonian cycle does require you to visit each vertex exactly once. An equivalent formulation of Hamiltonian cycle is a cycle which visits each of the $n$ vertices at least once and uses at most $n$ edges. This equivalent formulation is helpful for understanding my reduction. — Oct 12, 2010 at 14:46
- +3 – Nate: I think you're missing the point. Warren's using Ham cycle for the reduction TO your problem to show NP-hardness. He's not trying to give you an algorithm. — Oct 12, 2010 at 15:30
- +2 – As you say a spanning subgraph may or may not be a Hamiltonian cycle. However a spanning subgraph of length $n$ must necessarily be a Hamiltonian cycle. Therefore there is a spanning subgraph of length $n$ if and only if there is a Hamiltonian cycle. If this still doesn't make sense I'm not sure what else to say other than suggesting that you look in some textbook for example NP-hardness proofs, try to write a similar proof for this problem, and if that fails discuss this problem with a theory-minded person face to face. — Oct 12, 2010 at 18:07
- +2 – Perhaps it would help if you read the literature on the minimum strongly connected spanning subgraph problem (start with a Google search). A quick glance at that literature suggests that that problem is NP-complete and that it is the same as your problem. Please either tell us how your problem differs from the minimum strongly connected spanning subgraph problem, or else locate an NP-completeness proof in the literature, point us to it, and let us know which specific step of the proof you don't understand. — Oct 12, 2010 at 22:55