= Solution
To find a <minimum-weight acyclic subgraph>, filter to the subgraph $G_-$ containing only \b[strictly negative-weight <edges>], and run <Kruskal's algorithm> on those <edges>, accepting an <edge> exactly when it joins different current components. Return the resulting <forest>, with any omitted <vertices> regarded as isolated. Zero-weight <edges> may be omitted without worsening the objective.
To prove correctness, first remove all nonnegative <edges> from any feasible <acyclic graph>; removing them preserves acyclicity and cannot increase weight. Thus an optimum using only negative <edges> exists. Inside a connected component of $G_-$, any <forest> not yet connected can be extended by a negative crossing <edge>: some such <edge> exists because the original component is connected. Adding it preserves acyclicity and strictly reduces total weight. Consequently an optimum must span each component of $G_-$, and its restriction there must be a <minimum spanning tree>. <Kruskal's algorithm> finds exactly the resulting <minimum spanning forest> of $G_-$. This proves optimality among all acyclic subgraphs, including disconnected ones.
With $m_-$ negative <edges>, filtering costs $O(|V|+|E|)$, sorting costs $O(m_-\log(m_-+1))$, and the <union-find> operations take $O((|V|+m_-)\alpha(|V|))$ time. A standard overall bound is \b[$O(|V|+|E|\log(|E|+1))$ time]. If there are no negative <edges>, the empty <edge> set is optimal.
Back to article page
