5

次の決定問題を解決するアルゴリズムはありますか?

G遷移行列で定義された強連結加重有向グラフ が与えられた場合、G負のサイクルを持たない強連結スパンサブグラフは存在するか?

の強連結スパニング サブグラフは、 と同じ頂点を共有するGの強連結サブグラフです。強く連結されたスパニングサブグラフの定義については、このペーパーを参照してください。この論文では、最小の強連結サブグラフ問題の近似を示しています。GG

この問題に対する素朴なアプローチは、フォード-ベルマンまたはフロイド-ウォーシャル アルゴリズムを使用してグラフの負のサイクルを見つけ、このサイクルからエッジを削除し、グラフがまだ強く接続されている間に繰り返すことです。しかし、この素朴なアプローチは時間の複雑性に欠けます。これは、Ford-bellman アルゴリズムを実行して強い接続性を何度も確認する可能性があるためです。さらに、このアルゴリズムがすべてのインスタンスで正しいかどうかを証明することはできません。

この決定問題が多項式時間で解決できるかどうか、またどのようなアルゴリズムで解決できるかを教えてくれる専門家をここで見つけたいと思っています。よろしくお願いします。

4

2 に答える 2

0

これは、多項式時間で負のサイクルを持たない強く結合するスパニング サブグラフを見つける合理的な可能性を持つ単純なソリューションです。しかし、それを見つけることが保証されているわけではありません。

すべての重みを負にします。Ford-Bellman または Floyd-Warshall を使用して、負のサイクルを見つけます。これは実際には、元のグラフでは正のサイクルです。

ここで、サイクル内の 1 つの頂点を選択し、他の頂点をそれに収縮させます。削除された頂点に接続する/から接続するエッジは、そのエッジに沿って循環し、保持するエッジに移動することを表すものに置き換えられます。2 つの頂点間に複数のエッジが存在する場合は、最良のエッジのみを保持してください。

新しい小さいグラフで演習を繰り返します。

このアルゴリズムは保証された多項式時間で実行されます (各反復は多項式時間で実行され、少なくとも 1 つの頂点が削除されます)。グラフをポイントまで縮小できた場合は、プロセスを逆方向にたどって、負のサイクルのない強く接続されたスパニング グラフを実際に見つけたことがわかります。

ただし、これに失敗した場合、存在しないという保証はありません。あなたはそれを見つけられなかっただけです。

(保証されたアルゴリズムはNP完全になると思います。)

于 2019-12-30T21:50:30.530 に答える