Kelengkapan merentang pohon

Pohon rentang dari suatu grafik disebut pohon kelengkapan jika rangkaian daunnya menginduksi subgraf lengkap dalam grafik host. Diberikan grafik dan bilangan k k , apa kompleksitas memutuskan jika G berisi pohon kelengkapan dengan paling banyak k daun?$G$$k$$G$$k$

Alasan untuk mengajukan pertanyaan ini adalah bahwa masalah terkait untuk pohon independensi adalah NP-lengkap, di sini pohon independensi adalah spanning tree sedemikian rupa sehingga set daunnya merupakan set independen dalam grafik host.

Alasan lain adalah pertanyaan ini (dan jawaban yang sesuai). Ternyata setiap pohon rentang adalah pohon kelengkapan jika dan hanya jika G adalah grafik atau siklus lengkap. $G$$G$

Dalam grafik bebas segitiga, pohon kelengkapan harus berupa siklus Hamilton (minus salah satu tepinya). ISGCI mengatakan siklus Hamiltonian adalah NP-lengkap dalam grafik bebas segitiga. Oleh karena itu, demikian juga menemukan pohon kelengkapan (terlepas dari batasan jumlah maksimum daun).

Saya tidak bisa mengalahkan David dalam keanggunan jawabannya. Tetapi setelah menghabiskan banyak waktu untuk memikirkan masalah ini, saya ingin mengkhianati solusi saya untuk Anda;)

Biarkan menjadi interger tetap. Diberikan G , buat H sebagai berikut: Ambil dua salinan G 1 , G 2 dan klik Q pada k simpul x , x 1 , x 2 , … , x k - 1 , simpul baru y , perbaiki simpul v 1 ∈ G 1 dan sebuah simpul v 2 ∈ G 2 . H diperoleh dari$k \ge 2$$G$$H$$G_1$$G_2$$Q$$k$$x, x_1, x_2, \ldots, x_{k-1}$$y$$v_1 \in G_1$$v_2 \in G_2$$H$ dan y dengan menggabungkan x ke v 1 , bergabung dengan x 1 , x 2 , … , x k - 1 ke v 2 dan bergabung dengan semua tetangga dari v 1 di G 1 dan semua tetangga dari v 2 di G 2 sampai y .$G_1, G_2, Q$$y$$x$$v_1$$x_1, x_2, \ldots, x_{k-1}$$v_2$$v_1$$G_1$$v_2$$G_2$$y$

Maka dapat dengan mudah dilihat bahwa memiliki siklus Hamilton jika dan hanya jika H memiliki pohon kelengkapan dengan paling banyak k daun.$G$$H$$k$