How to remove cycles in an unweighted directed graph, such that the number of edges is maximised?

Question

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.

More formal: The desired algorithm consumes G and creates a set of acyclic graphs S, where each graph G' in S satisfies following properties:

1. G' contains all vertices of G.
2. G' contains a subset of edges of G, such that G' is acyclic.
3. 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.

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.

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.

Note: The problem may be related to a spanning tree, and you could define the G' graphs as a kind of directed 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 literature.

EDIT: Added intuitive description, background information and note related to spanning trees.

Tamayo

Are you looking to enumerate all the spanning trees of G? en.wikipedia.org/wiki/Spanning_tree – Gassing

@mhum: The problem is related, but spanning trees are undirected graphs, whereas i need a solution for directed graphs. But thanks to your hint, i googled "directed spanning tree" and found this paper. It will be a new starting point. – Tamayo

At least the linked wikipedia article restricts spanning trees as to undirected graphs. But you could define "directed spanning tree" as a connected directed graph composed of all vertices - seems like a valid naming to me. – Tamayo

The wiki article only talks about undirected graphs but the generalization to directed graphs is straightforward. Also, be careful with the paper you linked to; they're talking about a very particular restriction of the problem that's probably not relevant to your situation. In any case, I think I've found a more applicable reference (posted as an answer). – Gassing

Answer 1

This problem is called Feedback Arc Set. Since it is NP-hard, it is unlikely that you will find a scalable fast algorithm. However, if your instances are small, then algorithms such as the one from the paper “On enumerating all minimal solutions of feedback problems” by B. Schwikowski and E. Speckenmeyer might work.

Highsmith

Thanks for the hint to this interesting paper. That sums up this family of problems nicely. I therefor accept this answer because it provides clear definition and hints out possible solutions. As you noted already, it is hard to find solutions for large instances. After implementing a solver for small instances using a branch and bound method approach, we managed to model the original problem domain differently, so the NP-hardness could be omitted. – Tamayo