Topological sort of cyclic graph with minimum number of violated edges

Question

I am looking for a way to perform a topological sorting on a given directed unweighted graph, that contains cycles. The result should not only contain the ordering of vertices, but also the set of edges, that are violated by the given ordering. This set of edges shall be minimal.

As my input graph is potentially large, I cannot use an exponential time algorithm. If it's impossible to compute an optimal solution in polynomial time, what heuristic would be reasonable for the given problem?

Ames

Is this not feedback arc set? You can get the order by topologically sorting the residual DAG. – Reger

Also do you want a minimal solution (each and every removed arc would complete a cycle in the DAG) or a minimum solution (as few arcs removed as possible)? – Reger

@DavidEisenstat actually I don't care too much if it's one arc more or less, I simply have to handle them separately. If some algorithm takes twice the runtime and only finds a solution with few arcs less, it won't be economical. The problem seems to be feedback arc set, but that's NP hard in this case, so we'll need an approximation. – Ames

Answer 1

Eades, Lin, and Smyth proposed A fast and effective heuristic for the feedback arc set problem. The original article is behind a paywall, but a free copy is available from here.

There’s an algorithm for topological sorting that builds the vertex order by selecting a vertex with no incoming arcs, recursing on the graph minus the vertex, and prepending that vertex to the order. (I’m describing the algorithm recursively, but you don’t have to implement it that way.) The Eades–Lin–Smyth algorithm looks also for vertices with no outgoing arcs and appends them. Of course, it can happen that all vertices have incoming and outgoing arcs. In this case, select the vertex with the highest differential between incoming and outgoing. There is undoubtedly room for experimentation here.

The algorithms with provable worst-case behavior are based on linear programming and graph cuts. These are neat, but the guarantees are less than ideal (log^2 n or log n log log n times as many arcs as needed), and I suspect that efficient implementations would be quite a project.

Reger

This question still receives a bunch of views every now and then and I just came across it with the paper at hand, so if anyone is interested in the approximation algorithms David mentions in the last paragraph, he might be referring to "Divide-and-Conquer Approximation Algorithms via Spreading Metrics" by Even, Naor, Rao, Schieber, Journal of the ACM, Vol. 47, No. 4, July 2000, pp. 585–616, which does the log n log log n approximation even for weighted digraphs. – Landmeier

An earlier log^2 n approximation for the unweighted minimum feedback arc set problem (where we minimize the number of edges to remove) which is based on linear programming can be found in "Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms", Leighton, Rao, Journal of the ACM, Vol. 46, No. 6, November 1999, pp. 787–832. – Landmeier

Answer 2

Inspired by Arnauds answer and other interesting topological sorting algorithms have I created the cyclic-toposort project and published it on github. cyclic_toposort does exactly what you desire in that it quickly sorts a directed cyclic graph providing the minimal amount of violating edges. It optionally also provides the maximum groupings of nodes that are on the same topological level (and can therefore be activated at the same time) if desired.

If the problem is still relevant to you then I would be happy if you check out my project and let me know what you think!

This project was useful to my own neural network topology research, so I had to create something like this anyway. I am answering your question this late in case anyone else stumbles upon this thread in search for the same question.

Ingar