After some work on Minimum Spanning Trees and Steiner trees in combinatorial problems I came across this problem that I would like to look further in my research, but I want to know if there is an algorithm for it. I couldn't find anything in Google or Google Scholar.
Given a directed graph $G=(V,E)$ with a weight for each edge given by $w(e)$, find a subset $S \subseteq E$ of minimum cost (sum of weights) such that for every pair $u,v \in V$ of nodes, there is a path from $u$ to $v$ that traverses only edges in $S$.
A--2->B ^ | |2 |2 | v C--1->D <-3--
In the example, there is an edge from C to D of cost 1 and the opposite direction of cost 3. The solution here would be the edges CA, AB, BD and DC. This solution has cost 9.
Any variation of Prim or Kruskal fails on this problem, and I can't see any other algorithm that I could modify to work here. Also, I can't come up with any algorithm (I'm starting to suspect its NP-complete, but I am still looking for a reduction).
Can anyone tell me if this is indeed proven NP-complete or if there is a polynomial-time algorithm for this?