Maximal Minimum Weight DAGs

Question

In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well known.

Questions:

• is there a name for maximally directed-cycle-free subgraphs of minimal arc-weight sum?
• which algorithms are used for their calculation and what is the complexity of their calculation?

$$ $$ In view of the replies of Brendan and Tony, I see the need for clarification and a slight modification of my question:

One of the properties of MSTs is, due to the matroid-property, that for every pair of vertices $(p,q)\in V\times V\ \ \wedge\ \ e_{qp}\in E\ \ $ it is true, that for every path between p and q in the MST, we have
$$\max_{i\in\{p,pred(q)\}}w(e_{i,succ(i)})\ \le\ w(e_{qp})$$ this is so because the greedy strategy of always adding the shortest edge, that doesn't complete a cycle, yields the global minimum of edge-weight sums.

However, as has been pointed out by Brendan, DAGs are not necessarily matroids; I would therefore give up the requirement of minimal arc-weight sum and restrict my question to DAGs that are the outcome of the same greedy strategy as in the construction of MSTs, i.e. always add the shortest arc that doesn't complete a directed cycle.
The outcome should be DAGs for which the same inequality between the weights of path-arcs and the exterior arc augmenting it to a directed cycle should hold.

New Questions Besides the question for the name of such DAGs, the algorithmic questions would boil down to efficiently detecting the completion of a directed cycle and, whether the naiv application of the MST-construction algorithms (Prim, Kruskal, Boruvka) would yield the same DAG.

Answer 1

The case where all arcs have the same weight is the feedback arc set problem, which is NP-complete. Allowing arcs of different weight can't make it easier.

Answer 2

Note that the maximal acyclic arc sets of a digraph do not form a matroid as they do in the undirected case. Thus, the maximality condition is slightly strange, since maximal acyclic arc sets do not necessarily all have the same size.

Every acyclic digraph $D$ has a topological ordering. That is, there is an ordering of the vertices such that for all arcs $(u,v) \in A(D)$, $u$ comes before $v$ in the ordering. Thus, if $T$ is a maximal acyclic arc set, then $T$ is precisely the set of forward arcs of some ordering of $V(D)$. Thus, a naive way to find $T$ is to enumerate the set of backward arcs over all orderings of $V(D)$. Among all the backward arc sets that are minimal (under inclusion), take the one with the highest total weight. The complement of this set is what you want.

I suspect that you cannot do much better than this naive approach and that the problem is NP-hard.