Given a directed graph with weighted edges, what algorithm can be used to give a sub-graph that has minimum weight, but allows movement from any vertex to any other vertex in the graph (under the assumption that paths between any two vertices always exist).
Does such an algorithm exist?
This looks to be NP-Hard: The minimum weight strongly connected spanning subgraph problem.
I believe Hamiltonian cycle problem can be reduced to it: Given a graph G(V,E), construct a digraph DG with weight 1 for edges which appear and weight 100 (|V|+1) for edges that don't. DG has a minimum weight strongly connected spanning subgraph of weight exactly |V| if and only if G has a hamiltonian cycle.
The paper here has an approximation algorithm: http://portal.acm.org/citation.cfm?id=844363