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 完全的。