“反馈边问题 NP-Complete 证明”

反馈边 （Feedback Arc Set）问题的描述如下。给定一个有向图 ，问是否可以移除小于等于 条边使得 中没有循环。首先这个问题显然是 NP 问题。即给定移除的 条边，我只需要先把这 条边移除，然后判断剩下的图中是否有循环就可以了。判断循环的方法为从一个点出发，记录经过的点，判断当前点是否已经走过，若走过即存在循环。而这个操作是显然可以在多项式时间内完成的。

现在，我们把顶点覆盖问题归约到反馈边问题来证明反馈边问题是 NP 难的。

考虑我们现在已经得到一个顶点覆盖问题 ，即已知 中有 个点可以覆盖图中所有边，我们通过下面的规则将其转换为一个有向图 :

1. 对于 中的每一个点 , 在 中创建 和 ，并连接 。
2. 对于 中每一条边 ，假设其连接了点 和点 ，我们在 中连接 和 。

按照以上规则，我们转换过程的示例如下。显然以上转换是可以在多项式时间内完成的。

可以看得出，对于 中的每一条边，我们在 中构造出了一个环。所以，若要消除 中的所有环，则要求消除 中的所有边。于是假设我们有一个算法 可以在多项式时间内从 中消除 个边从而达到无环，那么我们就可以利用规则在多项式时间内将 转换到 从而使 在多项式时间内可以解决顶点覆盖问题。但我们知道，顶点覆盖问题是 NP 难的，即不存在这样的算法 ，所以反馈边问题也没有办法在多项式时间内解决。所以反馈边问题是 NP 难的。

综上所述，反馈边问题是 NP 完全的。