algorithm - 特定のネットワーク フローに単一の最小カットがあるかどうかを確認する

Question

特定のネットワーク フローに単一の最小カットがあるかどうかをチェックするアルゴリズムを探しています。

すべてのカットを検索し、最小カットが 1 つしかないかどうかを確認できるため、それが可能であることはわかっていますが、多項式で実行されるより効率的なアルゴリズムを見つけたいと考えています。

私を助けるために max-flow アルゴリズムを使用することを考えましたが、成功しませんでした。

Answer 1

そうでない場合は、重み付けされたケースを参照していると思います-すべてのエッジに1の重みを与えることで、重み付けされていないものを重み付けされたものに簡単に減らすことができます。

1 つのアプローチは、1 つの最小カットを見つけ、それを分割 U1、U2 とし、U1 からの頂点 u1 と U2 からの u2 の各ペアについて、(u1,u2) が E にあるようにすることです。重み w(u1,u1) - 同じ値の最小カットがまだあります。
最後に、最小カット値が残るようなエッジが 1 つ見つかった場合にのみ、複数の最小カットが存在します。

高レベルの擬似コード:

value,U1,U2 = min-cut(G) //value is the minimum cut value, U1,U2 are the cuts
for each u1 in U1 and u2 in U2 such that (u1,u2) is in E:
   temp <- w(u1,u2)
   w(u1,u2) <- w(u1,u2) + epsilon
   new_value,_,_ = min-cut(G)
   if (new_value == value): //2+ cuts with same value
        return true
   //roll back the changed weight
   w(u1,u2) <- temp
return false //no cuts with same value found

複雑さは ですO(E*min-cut)。ここで、min-cut は使用される最小カット アルゴリズムの複雑さです。