すべてのサイクルを削除するために有向グラフで削除するエッジの最小数はいくらですか？

Question

すべてのサイクルを削除するには、有向グラフで削除するエッジの最小数を見つける必要があります。例えばenter image description here

： - このグラフでは、3サイクルがある：

1）0-1-2-0

2）0-2-0

3）3-

1）縁部2-0及び3-3を削除：3

すべてのサイクルを除去するための2つの可能な組み合わせが存在します。

2）エッジ0-2,1-2、および3-3を削除します。

最初に2つのエッジを削除しなければならず、2番目のケースでは3つのエッジを削除する必要があります。

最初の組み合わせが解決策です。

Answer 1

この問題は、minimum feedback arc setの問題という名前でよく知られています。グラフのGとパラメータがkの場合、アークの一部を削除して、すべてのサイクルをGで中断できますか？通常のように、決定バージョンは、最小フィードバックアークセットを見つける計算よりも難しくないことに注意してください。

この問題の上記決定版はNP完全です。実際、それはRichard KarpのNP完全性問題の1つです。すなわち、NPがPに崩壊しない限り、この問題は多項式時間アルゴリズムを認めることはないと広く考えられている。あなたはウィキペディアのページから詳細を調べることができます。