Regarding the Cycle Removal Problem. This problem is actually called Feedback Arc Set (it is a set that "hits" all "feedbacks" (i.e. cycles) with arcs, i.e., edges). Its undirected variant is called Feedback Edge Set and is actually simply Minimum Spanning Tree, i.e., a problem solvable in O(m log n) time, compared to the NP-completeness for the directed case.

While the cycle removal algorithm is a fine heuristic, it can perform arbitrarily bad.