具有最小侵犯边数的循环图的拓扑类型

Question

我正在寻找一种方法来执行一个给定的有向非加权图上的拓扑排序，其中包含循环。结果不仅要包含顶点的排序，还要包含被给定排序所违背的边集。这组边应是最小的。

由于我的输入图可能很大，我不能使用指数时间算法。如果不可能在多项式时间内计算出最优解，那么对于给定的问题，什么启发式是合理的？

Answer 1

Eades，Lin和Smyth为反馈弧集问题提出了一个快速有效的启发式。最初的文章是在付费墙后面，但免费副本可以从这里获得。

有一种拓扑排序算法，它通过选择一个没有进入弧的顶点，在图中递归减该顶点，并将该顶点提前到该顺序来建立顶点顺序。（我是递归地描述算法，但您不必以这种方式实现它。）Eades-Lin-Smyth算法也寻找没有输出弧的顶点并追加它们。当然，所有顶点都有传入和传出的弧是可能发生的。在这种情况下，选择传入和传出之间微分最高的顶点。这里无疑有实验的空间。

具有可证明最坏情况行为的算法是基于线性规划和图割的。这些都很简洁，但保证不够理想(log^2 n或log n log log n倍于所需的弧），我怀疑高效的实现将是一个相当大的项目。