スパニングツリーの問題のNP完全性証明

Question

インストラクターから尋ねられた質問のヒントを探しています。

だから私はこの決定の問題が$ sf {np text { - } complete} $です。

グラフ$ g $には、$ s = {x_1、x_2、 ldots、x_n } $の正確なセットを葉として含む$ g $のスパニングツリーがあります。この決定問題へのハミルトニアンの経路を減らすことにより、$ sf {np text { - } complete} $であることを証明できるとわかりました。

しかし、私のインストラクターもクラスで私たちに尋ねました：

$ sf {np text { - } complete} $も「$ s $の正確なセット」の代わりに、

「$ s $のセット全体を含めて、おそらく他の葉を含む」または「$ s $のサブセット」

「sのサブセット」は$ sf {np text { - } complete} $になると思いますが、証明することはできません。これを減らすことができる問題はわかりません。 「$ s $ ...のセットを含める」については、多項式時間で解決できると思います。

Answer 1

要するに、あなたの推測は正しいです。この答えの目的のために、問題の3つの問題を次のように呼びましょう。

• 等しいバージョン：グラフ$ g =（v、e）$とセット$ s subseteq v $を指定すると、$ g $がスパニングツリー$ t $を持っているかどうかを決定します。 $ s $。あなたが述べたように、これはハミルトニアン経路の問題からの減少によりNP不完全です。
• サブセットバージョン：上記のように$ g $と$ s $が与えられた場合、$ t $の葉のセットが$ s $のサブセットになるように、$ g $にスパニングツリー$ t $があるかどうかを決定します。
• スーパーセットバージョン：上記のように$ g $と$ s $が与えられた場合、$ t $の葉のセットが$ s $のスーパーセットであるように、$ g $にスパニングツリー$ t $があるかどうかを決定します。

サブセットバージョンがNPコンプリートであることを証明するために、ハミトニアの経路の問題を引き続き減らすことができます。 EqualityバージョンのNP不完全性の証明を変更してみてください。

スーパーセットバージョンを多項式時間に解決できることを証明するには、そのようなツリー$ t $が存在するために必要かつ十分な条件を見つけてください。

両方のバージョン（および木に及ぶ他のいくつかの問題）は、[SK05]で研究されています。しかし、論文の証拠を見る前に自分で問題を解決しようとする方が良いと思います。なぜなら、紙を見ることは大きなネタバレになる可能性があるからです。残念ながら、スーパーセットバージョンの多項式時間アルゴリズムを見つけようとする前に、私は論文を見ました！

---

SK05] Mohammad Sohel RahmanとMohammad Kaykobad。木に及ぶいくつかの興味深い問題の複雑さ。 情報処理レター, 、94（2）：93–97、2005年4月。doi] [著者のコピー]

Answer 2

これらのヒントは、S問題のスーパーセットの解決策に私を導くのに十分ではありませんでした - ヒントは役に立ち、正しいです。これは私を解決策に導いた私の考えの列です。

gから（vs）からsのすべての頂点を削除してから、DFSでスパニングツリーTを見つけるとどうなりますか？ gにまだ接続されていない頂点がある場合は、v1。削除されたSの頂点の少なくとも1つの役割について、それは何と言っていますか？現在、スパニングツリーにあるいくつかの頂点からV1へのパスにあること。したがって、それは葉になることはできません（葉には子供がいないので）。接続されていないノードがない場合、それはSのすべての頂点が葉になる可能性があることを意味します。もちろん、他の頂点にのみ接続するSの頂点は、スパニングツリーに接続されず、状態に違反します。したがって、チェックする2つのケースがあります。

1. sではないすべてのノードがgからsを削除してスパニングツリーを見つけた後に接続されている場合
2. Sの各ノードをスパニングツリーに直接接続できる場合。