algorithm - 如何删除未加权有向图中的循环，以使边数最大化？

Question

设 G 是一个未加权的包含循环的有向图。我正在寻找一种算法来查找/创建所有非循环图 G'，该图由 G 中的所有顶点和 G 的边的子集组成，刚好小到足以使 G' 成为非循环图。

更正式:所需的算法使用 G 并创建一组无环图 S，其中 S 中的每个图 G' 满足以下属性:

1. G'包含G的所有顶点。
2. G' 包含 G 的边的子集，因此 G' 是无环的。
3. G' 的边数最大化。这意味着:不存在满足属性 1 和 2 的 G''，使得 G'' 包含的边比 G' 多，并且 G'' 是无环的。

背景:原始图 G 对元素之间的成对排序建模。由于图中的循环，这不能被用作对所有元素的排序。因此，最大无环图 G' 应该建模对此排序的最佳近似，尽可能多地尊重成对排序关系。

在一种天真的方法中，可以删除所有可能的边组合并在每次删除后检查非循环性。在这种情况下，有一个强分支的变体树，这意味着糟糕的时间和空间复杂性。

注意:问题可能与生成树有关，您可以将 G' 图定义为一种有向生成树。但请记住，在我的场景中，G' 中的一对边可能具有相同的起始顶点或相同的结束顶点。这与 literature 中使用的一些有向生成树的定义冲突。 .

编辑:添加了与生成树相关的直观描述、背景信息和注释。

Answer 1

这个问题叫做Feedback Arc Set .由于它是 NP-hard，因此您不太可能找到可扩展的快速算法。但是，如果您的实例很小，那么 B. Schwikowski 和 E. Speckenmeyer 的论文“On enumerating all minimal solutions of feedback problems”中的算法可能会起作用。