Masalah subgraph terhubung berat-maksimum dalam grafik planar

Masalah subgraph terhubung maksimum-berat adalah sebagai berikut:

Input: grafik dan berat (mungkin negatif) untuk setiap titik .w i i ∈ $G=(V,E)$$w_i$$i \in V$

Keluaran: subset maksimum-berat dari simpul sedemikian sehingga terhubung.G [ S $S$$G[S]$

Masalah ini NP-hard. David S. Johnson menyebutkan pada hal. 149 dari kolom ini bahwa masalahnya tetap sulit dalam grafik planar dari tingkat tiga maksimum dengan semua bobot baik atau .- $+1$$-1$

Saya tidak dapat menemukan kertas yang dikutip - A. Vergis, manuskrip (1983)

Ada ide tentang di mana menemukan kertas itu? Atau pengurangan apa itu?

Dalam "The NP-Completeness Column: An Ongoing Guide" nomor 14, Johnson menulis "... Vergis [49]. Transformasi dari STEINER TREE IN GRAPHS [ND12] ..." . Saya tidak memiliki akses ke makalah Vergis, namun kemungkinan pengurangannya adalah sebagai berikut.

Steiner Tree (ST) dalam masalah grafik

Instance : grafik tak berarah , subset dari simpul R ⊆ V , disebut terminal node ; bilangan bulat non-negatif $G = (V,E)$$R \subseteq V$$k$

Pertanyaan : apakah ada subtree yang mencakup semua simpul R (pohon spanning untuk R ) dan yang paling banyak berisi tepi k ?$G$$R$$R$$k$

Masalahnya tetap NPC bahkan untuk grafik planar (M. Garey dan D. Johnson. Masalah Steiner tree bujursangkar adalah NP-lengkap).

Diberikan turunan dari planar ST, untuk sekarang anggaplah bahwa Anda dapat menetapkan bobot sewenang-wenang untuk node. Jika dan | E | = q , Anda dapat menetapkan bobot q + 1 ke node R dan Anda dapat menambahkan simpul tengah ke setiap tepi E dan menetapkan bobot - 1 ke dalamnya. Berat badan menetapkan 0 untuk node yang tersisa di V ∖ R . Grafik asli G memiliki spanning tree untuk R dengan paling banyak $|R|=p$$|E|=q$$q+1$$R$$E$$-1$$0$$V \setminus R$$G$$R$$k$ujung-ujungnya jika dan hanya jika dalam grafik yang ditransformasikan, Anda dapat menemukan subgraf bobot target lebih besar atau sama dengan .$W = p(q+1) - k$

Secara informal untuk mencapai jumlah Anda harus menyertakan semua simpul R dalam subgraf, dan Anda harus menyertakan paling banyak simpul tengah k (sesuai dengan tepi G ) yang memiliki bobot negatif -1 agar tetap terhubung .$p(q+1)$$R$$k$$G$

Anda dapat mengurangi derajat maks dari keseluruhan grafik menjadi tiga dengan cara ini: jika hanya mengubah setiap simpul u i ke rantai lingkaran simpul D (dan sesuaikan nilai p sesuai). Hubungkan tepi masuk ke node yang berbeda dari rantai (yang akan memiliki derajat 3).$D = \max\{deg(u_i) \mid u_i \in V\}$$u_i$$D$$p$

Dan jika Anda hanya ingin menggunakan bobot maka Anda harus: (A) menetapkan + 1 untuk semua node dari rantai bundar yang sesuai dengan node di V ∖ R , (B) mengubah setiap node tengah menjadi rantai linier node berat - 1 dan panjang l E = | V ∖ R | + 1 , dan (C) lebih memperluas rantai melingkar (dengan berat 1) sesuai dengan node R untuk setidaknya panjang l R$+1,-1$
$+1$$V\setminus R$
$-1$$l_E = |V\setminus R|+1$
$R$ ; dan set Target berat W = p l R - k l E . Secara informal, rantai yang diperluas dan target baru membuatbobot + 1 dari simpul yang terkait dengan V ∖ R (titik A) tidak relevan.$l_R = l_E( |E| + 1)$$W =pl_R - kl_E$
$+1$$V \setminus R$