Topological view of a cyclic graph with a minimum number of broken edges

Question

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

Since my input graph is potentially large, I cannot use the exponential time algorithm. If it is impossible to calculate the optimal solution in polynomial time, what heuristic would be reasonable for this problem?

Answer 1

Eades, Lin, and Smyth have suggested Fast and efficient heuristics for feedback problem . The original article is behind the pay line, but a free copy can be obtained from here .

Theres is a topological sorting algorithm that builds the order of vertices by selecting a vertex without incoming arcs that is recursive on the graph minus a vertex and adding this vertex to the order. (Im describing the algorithm recursively, but you don't need to implement it that way.) The Eades-Lin-Smyth algorithm also considers vertices without outgoing arcs and adds them. Of course, it may happen that all vertices have an incoming and outgoing arc. In this case, select the peak with the highest difference between inbound and outbound. There is undoubtedly a place for experimentation.

Proven Worst Behavior Algorithms are based on linear programming and graphs. They are neat, but the guarantees are less than ideal (log ^ 2 n or log n log log n times as arcs arcs as needed), and I suspect that effective implementations will be quite a project.