title: How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?
body: <p>Let G be an unweighted directed graph containing cycles. I'm looking for an algorithm which finds/creates all acyclic graphs G', composed of all vertices in G and a subset of edges of G, just small enough to make G' acyclic.</p>
  
  <p>More formal: The desired algorithm consumes G and creates a set of acyclic graphs S, where each graph G' in S satisfies following properties:</p>
  
  <ol>
  <li>G' contains all vertices of G.</li>
  <li>G' contains a subset of edges of G, such that G' is acyclic.</li>
  <li>The number of edges of G' is maximised. Which means: There is no G'' satisfying properties 1 and 2, such that G'' contains more edges then G' and G'' is acyclic.</li>
  </ol>
  
  <p>Background: The original graph G models a pairwise ordering between elements. This can't be exploited as an ordering over all elements due to cycles in the graph. The maximal acyclic graphs G' therefore should model a best-possible approximation to this ordering, trying to respect as much of the pairwise ordering relation as possible.</p>
  
  <p>In a naive approach, one could remove all possible combinations of edges and check for acyclicity after each removal. In this case there is a strongly branching tree of variations meaning bad time and space complexity.</p>
  
  <p>Note: The problem may be related to a spanning tree, and you could define the G' graphs as a kind of <em>directed</em> spanning tree. But keep in mind that in my scenario a pair of edges in G' may have the same starting or the same ending vertex. This conflicts with some definitions of directed spanning trees used in <a href="http://research.nii.ac.jp/~uno/papers/isaac96web.pdf">literature</a>.</p>
  
  <p>EDIT: Added intuitive description, background information and note related to spanning trees.</p>