NP – 特殊な頂点が入力として与えられるグラフの完全な問題?

私は現在、インスタンスがグラフ内にグラフと特殊な頂点を含むグラフ理論問題に取り組んでいます。私は、問題のNP完全性を証明するとともに、異なるクラスのグラフ上のアルゴリズムを探索しようとしています。私が抱えている問題の1つは、特殊な頂点が問題の入力の一部として与えられるような類似の問題をまだ見つけていないことです。

特殊な頂点が入力の一部として与えられる問題(多項式またはNP完全)へのリンクは大きな助けになります。

ベストアンサー

一般的な縮小戦略では、いくつかのダミーの頂点/頂点を追加し、それを特定の方法で特殊な頂点に接続する新しいグラフを作成します。これにより、ソリューションが目的の方法で特殊な頂点を使用することが保証されます、
か何か)。または、ダミーの頂点を追加し、特殊な頂点以外の他のすべての頂点に接続することもできます。詳細は、NP完成を証明しようとしている特定の問題に依存します。あなたの問題について何も教えてくれていないので、それ以上のことは言えません。

ですから、問題の定義に特殊な頂点が含まれている削減パートナーを探すことには制限しないでください。代わりに元の問題に似ている削減パートナーを探し、グラフを修正して特殊な頂点を処理します。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です