如何移除无权有向图中的回路，以便使边数最大化？

Question

假设G是一个包含环的无权有向图。我正在寻找一种算法，它可以找到/创建所有无环图G'，由G中的所有顶点和G的子集组成，使G'足够小以使其成为无环图。

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

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

背景：原始图G模拟元素之间的成对排序。由于图中存在循环，因此无法将其用作所有元素的排序。因此，最大无环图G'应该尽可能好地近似表示此排序，尝试尊重尽可能多的成对排序关系。

在一种朴素的方法中，可以删除所有可能的边缘组合，并在每次删除后检查无环性。在这种情况下，会产生强分支变体树，这意味着时间和空间复杂度不佳。

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

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

- mtsz

---

您是否正在寻求枚举 G 的所有生成树的方法？http://en.wikipedia.org/wiki/Spanning_tree - mhum

@mhum：这个问题有关，但生成树是_无向_图，而我需要解决_有向_图的问题。但是感谢您的提示，我搜索了“有向生成树”，并找到了这篇论文。这将是一个新的起点。 - mtsz

至少链接的维基百科文章将生成树限制为_无向_图。但是，您可以将“有向生成树”定义为由所有顶点组成的连通有向图 - 对我来说似乎是一个有效的命名。 - mtsz

维基百科的文章只讨论了无向图，但是将其推广到有向图是很直接的。另外，要小心你提供的那篇论文；他们在谈论一个非常特定的问题限制，可能与你的情况无关。无论如何，我认为我找到了一个更适用的参考资料（作为答案发布）。 - mhum

Answer 1

这个问题被称为反馈弧集合问题。由于它是NP难的，因此很难找到可扩展的快速算法。但是，如果您的实例很小，那么B. Schwikowski和E. Speckenmeyer在论文“On enumerating all minimal solutions of feedback problems”中提出的算法可能有效。

- Falk Hüffner

---

感谢您提供这篇有趣的论文提示。它很好地总结了这类问题。因此，我接受了这个答案，因为它提供了清晰的定义并指出了可能的解决方案。正如您已经注意到的那样，对于大规模实例很难找到解决方案。在使用分支定界法(Branch and bound)方法为小实例实现求解器后，我们成功地以不同的方式对原始问题域进行了建模，从而避免了NP难度问题。 - mtsz