Sorting a graph to make as many arrows point forward as possible

Question

I need to sort the nodes of a directed graph such that the number of arrows that flow backwards (against the sorting order) is minimal.

I can think of algorithms (e.g. keep swapping nodes until no swap will improve things) but I'm not sure how fast they run or whether they arrive at the best solution.

What is the name and complexity of this problem?

Answer 1

After some thought I realized that the problem can be split in two:

1. determine a largest acyclic subgraph of a graph (which is NP-hard)
2. topologically sort it (which is a lot easier)

Answer 2

Sorting nodes in order of depth can be done with a topological sort. However, this will only work with graphs that contain no cycles. Your problem sounds like there are cycles in the graph. One option would be to find the cycles (see the Tortoise and Hare algorithm for a method of doing this) and break the cycle, recording where you broke it. Then sort the nodes and re-link.

If you are doing this for visualisation purposes there is a graph rendering library called GraphViz that does something very similar to what you are describing and then lays out the nodes. It is easy to integrate and use and will render to the screen or a variety of different output formats.