如何求有向图的最大无环子图的2-近似解?

将节点集划分为两个非空集A和B。考虑从A到B的边集和从B到A的边集。从较小的集合中剔除边,保留较大集合中的边(任意断开连接)。分别在A和B上递归。

结果图是非循环的,因为每个循环的节点第一次在A和B之间分割时都会被打断。我们扔掉的边的总数不大于我们保留的边的总数,所以我们扔掉了最多一半的边。

1. 从1到n任意编号节点;
3. 在正向集合和反向集合之间选择较大的集合。

正确性和近似比证明都是微不足道的。