Mengapa pohon spanning k-problem NP selesai?

Masalah pohon spanning terikat adalah di mana Anda memiliki grafik tidak terarah dan Anda harus memutuskan apakah memiliki spanning tree sedemikian rupa sehingga setiap simpul memiliki derajat paling banyak .$k$$G(V,E)$$k$

Saya menyadari bahwa untuk kasus , ini adalah masalah jalur Hamilton. Namun saya mengalami masalah dengan kasus di mana . Saya mencoba berpikir tentang hal itu dalam arti bahwa Anda dapat menambahkan lebih banyak node ke pohon spanning yang ada di mana dan mungkin karena basisnya adalah NP lengkap, menambahkan hal-hal pada akan membuatnya NP-lengkap juga, tetapi itu tampaknya tidak Baik. Saya CS belajar sendiri dan mengalami masalah dengan teori, jadi bantuan apa pun akan dihargai!$k=2$$k>2$$k=2$

Pertanyaan telah ditanyakan sebelumnya pada stackoverflow , di mana juga telah dijawab. Idenya adalah untuk menghubungkan setiap simpul ke simpul baru . Grafik baru memiliki pohon spanning terikat jika grafik asli memiliki jalur hamiltonian.$k-2$$k$

Mohit Singh dan Lap Chi Lau memberikan algoritma polytime yang menemukan pohon spanning jika pohon spanning ada. Jadi kita dapat menentukan tingkat minimum dari spanning tree hingga ketidakpastian .$(k+1)$$k$$1$

Pemahaman saya adalah jika Anda memiliki algoritma yang dapat menyelesaikan masalah pohon spanning k-terikat dengan k apa pun, Anda dapat menggunakan algoritma itu untuk memecahkan kasus khusus dengan k = 2, yang pada dasarnya adalah jalur Hamiltonian. Jadi, jika algoritma Anda dapat mencapai waktu polinomial, maka dapat digunakan untuk menyelesaikan jalur Hamilton dalam waktu polinomial, yang setara dengan menyelesaikan masalah np-complete dalam waktu polinomial. Jadi problem spanning tree tree harus np-complete. Perhatikan bahwa ini adalah gagasan umum, bukan bukti lengkap.

Perhatikan juga bahwa menjadi np-complete tidak berarti bahwa tidak ada algoritma waktu polinomial yang dapat menyelesaikan masalah. Belum ada yang membuktikan ini. Ini hanya berarti bahwa semua masalah yang lengkap np sama-sama sulit dan jika seseorang dapat diselesaikan dalam waktu polinomial maka semua dapat diselesaikan dalam waktu polinomial.