在有向圖中要刪除所有循環的最小邊數是多少？

Question

我們必須找出有向圖中要刪除的最小邊數，以刪除所有的循環。 enter image description here

例如： - 在該曲線圖中，有3個循環：

1）0-1-2-0

2）0-2-0

3）3- 3

有兩種可能的組合，以除去所有的循環：

1）刪除邊2-0和3-3。

2）刪除邊緣0-2,1-2和3-3。

在第一種情況下，我們必須刪除2個邊，第二種情況下，我們必須刪除3個邊。

第一種組合是解決方案。

Answer 1

此問題是衆所周知的名稱minimum feedback arc set問題。問題的決定版本說：給定圖G和參數k，我們可以通過刪除最多k弧段中的一組弧線來打破G中的所有循環嗎？請注意，像往常一樣，決策版本並不比尋找最小反饋弧集的計算更難。

這個問題的上述決定版本是NP完全的。事實上，這是理查德卡普21個NP完整性問題之一。也就是說，除非NP崩潰到普遍認爲不可能的P - 這個問題不會承認多項式時間算法。你可以從維基百科頁面查看詳細信息。