Bukti kelengkapan NP dari masalah spanning tree

Saya mencari beberapa petunjuk dalam pertanyaan yang diajukan oleh instruktur saya.

Jadi saya baru tahu masalah keputusan ini adalah :$\sf{NP\text{-}complete}$

Dalam grafik , apakah ada spanning tree dalam G yang berisi sekumpulan S = { x 1 , x 2 , … , x n } sebagai daun. Saya menemukan bahwa kita dapat membuktikan bahwa itu adalah N P - c o m p l e t e dengan mengurangi jalur Hamilton ke masalah keputusan ini.$G$$G$$S=\{x_1, x_2,\ldots, x_n\}$$\sf{NP\text{-}complete}$

Tetapi instruktur saya juga bertanya kepada kami di kelas:

apakah itu juga jika alih-alih "set tepat S ", kita lakukan$\sf{NP\text{-}complete}$$S$

"Sertakan seluruh rangkaian dan mungkin daun lain" atau "bagian dari S "$S$$S$

Saya pikir "subset dari S" akan menjadi , tapi saya tidak bisa membuktikannya, saya tidak tahu masalah apa yang bisa saya kurangi untuk ini. Adapun "termasuk set S ..." Saya pikir itu bisa diselesaikan dalam waktu polinomial.$\sf{NP\text{-}complete}$$S$

Singkatnya, tebakan Anda benar. Untuk tujuan jawaban ini, sebut tiga masalah yang dimaksud sebagai berikut:

• Kesetaraan versi: Mengingat grafik dan satu set S ⊆ V , memutuskan apakah G memiliki pohon rentang T sehingga set daun di T sama dengan S . Seperti yang Anda nyatakan, ini NP-lengkap dengan pengurangan dari masalah jalur Hamilton.$G = (V, E)$$S \subseteq V$$G$$T$$T$$S$
• Versi Subset: Mengingat dan S seperti di atas, memutuskan apakah G memiliki pohon rentang T sehingga set daun di T adalah bagian dari S .$G$$S$$G$$T$$T$$S$
• Superset versi: Mengingat dan S seperti di atas, memutuskan apakah G memiliki pohon rentang T sehingga set daun di T merupakan superset dari S .$G$$S$$G$$T$$T$$S$

Untuk membuktikan bahwa versi subsetnya adalah NP-complete, Anda masih bisa mengurangi masalah jalur Hamitonian. Cobalah untuk memodifikasi bukti kelengkapan NP versi kesetaraan.

Untuk membuktikan bahwa versi superset dapat diselesaikan dalam waktu polinomial, cobalah untuk menemukan kondisi yang diperlukan dan cukup untuk pohon seperti itu untuk ada.$T$

Kedua versi (serta beberapa masalah lain tentang spanning tree) dipelajari dalam [SK05]. Tapi saya kira itu lebih baik jika Anda mencoba menyelesaikan masalah sendiri sebelum melihat bukti di koran, karena melihat kertas bisa menjadi spoiler besar. Sayangnya saya telah melihat kertas sebelum mencoba mencari algoritma waktu polinomial untuk versi superset!

[SK05] Mohammad Sohel Rahman dan Mohammad Kaykobad. Kompleksitas beberapa masalah menarik pada spanning tree. Information Processing Letters , 94 (2): 93–97, April 2005. [ doi ] [ copy penulis ]

Petunjuk ini tidak cukup untuk membawa saya ke solusi untuk superset masalah S - meskipun petunjuk itu membantu dan benar. Ini adalah kereta pemikiran yang membuat saya mendapatkan solusi.

Apa yang terjadi jika Anda menghapus semua simpul di S dari G, (VS), dan kemudian menemukan spanning tree T dengan DFS? Jika ada simpul yang belum terhubung di G, katakanlah v1; apa yang dikatakan tentang peran setidaknya satu simpul dalam S yang telah dihapus? Itu terletak di jalan ke v1 dari beberapa titik yang saat ini di pohon spanning. Jadi, tidak mungkin daun (karena daun tidak punya anak). Jika tidak ada simpul yang tidak terhubung, itu berarti setiap simpul di S dapat berupa daun asalkan memiliki ujung yang mengarah ke pohon spanning. Verteks dalam S yang hanya terhubung ke simpul lain di S tentu saja tidak akan memiliki koneksi ke spanning tree dan akan melanggar kondisi. Jadi, ada dua kasus yang harus diperiksa:

1. Jika semua node tidak dalam S terhubung setelah menghapus S dari G dan menemukan spanning tree
2. Jika setiap node di S dapat dihubungkan langsung ke spanning tree.