检测最小边数以打破所有循环的算法

Question

是否有一种算法将有向图作为输入，并作为输出给出最小数量的边以“中断”以防止循环？

例如，上图中的循环是:

• A、B、C、D
• A、B、E
• E、G、H、F

以及打破所有边的最小边数:

• >
  1. A - B，打破 2 个循环
• >
  1. E - G，打破 1 个循环

当循环彼此嵌套并共享边时，情况会变得更加复杂。

我目前的方法是找到所有循环，按最常见的边分组，按 desc 排序，并按该顺序打破它们，同时循环仍未从之前的迭代中被打破。

我已经尝试了几种方法，但它们都因折断边的数量而异 - 我正在寻找理论上可能的最小值。

是否有执行此操作的既定算法？

Answer 1

这是 NP-hard Minimum Feedback Arc Set problem .维基百科没有指出适用于中小型图的确切算法，所以让我推荐一个。

使用整数规划求解器库，例如 OR-Tools ，我们为每条弧制定一个具有0-1变量的整数规划，其中0表示保留弧，1表示删除弧。目标是最小化这些变量的总和。

现在，我们需要指定约束条件，但通常情况下，循环的数量可能呈指数级增长，随着图形的增长，这会很快使求解器不堪重负。相反，请执行以下操作:

1. 求解整数规划(最初，没有约束)。
2. 使用广度优先搜索在保留的边中找到最短环(如果有)。
3. 如果存在循环，则添加一个约束条件，即对应变量之和必须大于等于1，然后返回步骤1。否则，当前解为最优解。