Soptq

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

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

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

1. 对于 $G$ 中的每一个点 $u$, 在 $G_f$ 中创建 $u_{in}$ 和 $u_{out}$ ，并连接 $u_{in} \rightarrow u_{out}$。
2. 对于 $G$ 中每一条边 $e$，假设其连接了点 $u$ 和点 $v$，我们在 $G_f$ 中连接 $u_{out} \rightarrow v_{in}$ 和 $v_{out} \rightarrow u_{in}$。

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

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

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