 Theoretical Computer Science

# 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?