Minimum Weight Directed Subgraph ensuring all pairs reachability?

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$.

For instance:

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?

1 Answer

This problem is a generalized version of the famous Minimum Spanning Strong Subdigraph or MSSS [1]. This problem is NP-hard and there are several heuristic algorithms for it. You may look at the reference given in this solution and the related papers to find out more about this problem.

Note that this problem itself is a simplified version of Minimum Equivalent Graph of a Digraph [2]. Therefore, there are some algorithms that you can use as a heuristic for this problem.

[1] Bang-Jensen, Jorgen, Jing Huang, and Anders Yeo. "Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs." SIAM Journal on Discrete Mathematics 16.2 (2003): 335-343.

[2] Martello, Silvano, and Paolo Toth. "Finding a minimum equivalent graph of a digraph." Networks 12.2 (1982): 89-100.