2

この問題は次のように与えられます: DAG と number が与えられた場合、ソースからシンクへのパスの0 < p ≤ 1少なくとも一部を切断する (つまり、入ってくるアークがない) (つまり、出るアークがない) 頂点のカーディナリティが最小のセットを返します。 p）。の場合p = 1、問題は最小カットに相当します。ただし、の他の値についてはp、答えがどうなるかわかりません。

私が考えているアルゴリズムは、最初に DAG の最小カット セットを計算し、次に基準を満たすように刈り込むことです。これ自体、見つけたサブセットが実際にp与えられた特定の最小カットセットであるかどうかを確認するのは興味深いことです。このアルゴリズムの問​​題は、最終的な答えで必要のない多くのノードを計算し、実際には最初に「より大きな」問題を解決しているため、無駄が多いことです。

この問題の解決策へのポインタはありますか? min-cut の一部のアルゴリズムでは、この追加の制約を早期停止基準として設定することは可能ではないでしょうか?

削除されたパスの数を確認するために、削除によって切断されたパスの数がわかるように、各頂点にインデックスを付けて (必要に応じて更新し続ける) とします。更新中のインデックスの複雑さについて心配しないでください。最後にもう 1 つ、サイズなどに関して、結果のコンポーネントに制約はありません。

4

2 に答える 2

0

EDIT1: OP の更新を確認した後、このソリューションは 1 つのソース u と 1 つのシンク v の場合に適用されます。

EDIT2: これは実際にはヒューリスティックです。以下のコメントの反例を参照してください。

これは、次のスレッドで提供されているパスをカウントする方法に基づく O(V+E) ソリューションです (David Eisenstat によって指摘されました、ありがとう) :

DAG 内の 2 つのノード間のパスの数

最初の段階では、stalker によって提案された「後方」の方法を正確に適用します。このフェーズの最後に、次の情報を取得して保存します。

  • 各頂点 i について、i から v へのパスの数 F(i, v)

  • F(u, v)、ソース u からシンク v へのパスの数。

第 2 段階では、同じ方法で先に進みます。質問が v から u への「逆方向パス」を見つけることであるかのように、アルゴリズムをシミュレートします。最後に、次を取得します。

  • 各頂点 i について、i から u への逆方向パスの数 B(i, u)。明らかに B(i, u) = F(u, i)

  • F(u, v) に等しい B(v, u)。

第 3 段階では、頂点 i ごとに数 P(i) = F(u, i) * F(i, v) を計算します。i を通過する (u, v) パスの数が P(i) であることを証明するのは簡単です。したがって、頂点 i を削除すると、P(i) パスが削除されます。

最後の 4 番目のフェーズでは、貪欲な方法で処理を進めます。削除されたパスの総数が p*F(u, v) を超えるまで、P(i) が最も高い頂点を削除します。

次の理由から、全体的なアルゴリズムは O(V+E) です。

  • 参照投稿によると、最初の 2 つのフェーズは O(V+E) です。

  • 3 番目と 4 番目のフェーズは明らかに O(V) であるため、O(V+E)

于 2015-09-21T12:35:08.907 に答える