Masalah NP-hard pada pohon

47

Beberapa masalah optimisasi yang dikenal sebagai NP-hard pada grafik umum sepele dipecahkan dalam waktu polinomial (beberapa bahkan dalam waktu linier) ketika grafik input adalah pohon. Contohnya termasuk penutup simpul minimum, set independen maksimum, isomorfisme subgraph. Sebutkan beberapa masalah optimasi alami yang tetap NP-keras pada pohon.

Siwa Kintali
sumber
1
Jukka, masih bisa diperdebatkan jika "komunitas wiki" diperlukan di sini. Masalah yang jelas-jelas dibikin dengan sedikit relevansi mungkin akan kalah.
Ryan Williams
1
Saya juga cenderung berpikir bahwa CW tidak perlu
Suresh Venkat
2
Tidak yakin apakah CW diperlukan. Saya tidak bisa memikirkan masalah apa pun dari atas kepala saya. Sepertinya poster harus dihargai karena menjawab pertanyaan ini.
Robin Kothari
5
Beberapa laporan penelitian Google acak yang menunjukkan bahwa masalah adalah NP-keras bahkan jika inputnya adalah pohon: perutean kendaraan kapasitansi , masalah latensi minimum , penjadwalan panggilan ...
Jukka Suomela
4
Ini bukan apa yang Anda minta, tetapi layak untuk disebutkan di sini: ada beberapa masalah yang mudah di pohon tetapi sulit di treewidth terikat. Misalnya, jalur edge-disjoint (Nishizeki, Vygen, Zhou '01) dan rentang matriks kendala (McDiarmid, Reed '03).
Diego de Estrada

Jawaban:

23

Anda dapat menemukan contoh masalah grafik "alami" dan "terkenal" yang sulit bahkan jika terbatas pada pohon dari referensi standar kami . Contoh:

(Ini diformulasikan sebagai masalah pohon, tetapi Anda dapat menggeneralisasikannya ke grafik arbitrer. Kemudian formulasi di atas diperoleh sebagai kasus khusus ketika Anda membatasi input ke pohon.)


Resep yang lebih umum untuk menghasilkan masalah yang sulit pada pohon: Ambil masalah NP-hard yang terkait dengan supersekuensinya , superstring , substring , dll. Kemudian tafsirkan ulang string sebagai grafik jalur berlabel. Kemudian ajukan pertanyaan analog untuk grafik umum (selanjutnya ≈ grafik minor, substring ≈ subgraph). Dan kita tahu bahwa masalahnya adalah NP-hard bahkan pada pohon (dan di jalur).


Ada juga banyak masalah yang sulit pada bintang berbobot, dengan reduksi dari masalah subset-sum. Contoh alami adalah:

  • TSP dengan dua pelancong : diberi grafik tepi-tertimbang dan batas , dapatkah kita menemukan dua jalan tertutup dan di sehingga setiap jalan memiliki berat total paling banyak , dan setiap simpul ditutupi oleh setidaknya satu berjalan?W C 1 C 2 G W GGWC1C2GWG

Sekali lagi, mudah untuk membuat variasi tema.

Jukka Suomela
sumber
Sayang sekali kompendiumnya tidak diperbarui lagi.
Anthony Labarre
Apa itu "label jalur berlabel"?
david
29

Ini NP-lengkap untuk menentukan apakah sebuah pohon dapat tertanam ke dalam kisi integer dua dimensi, dengan simpul pohon ditempatkan pada titik kisi yang berbeda dan tepi pohon ditempatkan pada tepi kisi.

Lihat misalnya Gregori, IPL 1989 .

David Eppstein
sumber
Jadi, ini menyiratkan kekerasan menggambar pohon bujursangkar? Apakah ada batas tertentu yang melindungi kekerasan?
Mohammad Al-Turkistany
2
Batasi kembali derajat: jika ada simpul dengan derajat lebih besar dari empat, maka tidak ada penyisipan kisi.
David Eppstein
Terima kasih David, sederhana untuk menyatakan masalah namun menarik.
Mohammad Al-Turkistany
Oh, pohon input juga merupakan pohon biner. Itu hebat!
Cyriac Antony
24

Masalah Group Steiner adalah contoh yang bagus. Input untuk masalah ini adalah graf berbobot tepi yang tidak diarahkan dan k grup simpul . Tujuannya adalah untuk menemukan pohon bobot minimum yang mengandung setidaknya satu simpul dari setiap kelompok. Sangat mudah untuk melihat bahwa masalah Set Cover adalah kasus khusus bahkan ketika G adalah bintang. Jadi masalahnya sulit untuk diperkirakan dalam faktor kecuali P = NP. Selain itu, ditunjukkan oleh Halperin dan Krauthgamer bahwa masalahnya sulit untuk diperkirakan dalam faktor untuk setiap fix kecuali NP memiliki algoritma waktu kuasi polinomial acak (NP). lihat kertas untuk pernyataan yang lebih jelas). AdaS 1 , S 2 , , S k O ( log n ) O ( log 2 - ϵ n ) ϵ > 0 O ( log 2 n )G=(V,E)S1,S2,,SkO(logn)O(log2ϵn)ϵ>0O(log2n) pendekatan pada pohon oleh Garg, Konjevod dan Ravi.

Chandra Chekuri
sumber
4
Aaah: lateks yang belum diformat !! itu menyakitkan mata :)
Suresh Venkat
Yah, saya tidak tahu bagaimana melakukan pemformatan lateks di sini :). Pointer ??
Chandra Chekuri
cukup gunakan $ .. $ seperti biasa.
Suresh Venkat
ok semuanya sudah diperbaiki sekarang.
Suresh Venkat
22

Salah satu masalah tersulit pada pohon adalah masalah bandwidth minimum. Ini adalah pada pohon dengan derajat maksimum 3. Juga NP-keras pada ulat melingkar dengan panjang rambut 1.NP

Referensi:

Michael R. Garey, Ronald L. Graham, David S.Johnson, dan Donald E. Knuth. Hasil kerumitan untuk meminimalkan bandwidth. SIAM J. Appl. Matematika., 34 (3): 477-495, 1978.

Burkhard Monien. Masalah minimisasi bandwidth untuk ulat dengan panjang rambut 3 adalah NP-lengkap. SIAM J. Algebraic Discrete Methods, 7 (4): 505-512, 1986.

W. Unger. Kompleksitas perkiraan masalah bandwidth. Dalam FOCS, halaman 82–91, 1998

Mohammad Al-Turkistany
sumber
1
Versi terkoreksi dari kertas Unger adalah hasil Hardness untuk perkiraan bandwidth , Chandan Dubey, Uriel Feige, dan Walter Unger.
Yuval Filmus
13

Masalah petugas pemadam kebakaran telah menerima cukup banyak perhatian baru-baru ini, dan (agak mengherankan) NP-hard pada pohon dengan derajat 3 maksimum . Ini sebenarnya pertanyaan yang cukup alami, dijelaskan sebagai berikut:

k

Atau varian, juga NP-hard : Apakah ada strategi untuk pemadam kebakaran di mana tidak ada daun terbakar?

Andrew D. King
sumber
8

Masalah yang orang mungkin berpikir TIDAK akan sulit di pohon, tetapi adalah, adalah masalah pembekuan-tag dalam geometri komputasi : secara singkat, masalah penjadwalan bangun untuk robot dimulai dengan bot awake 'tunggal, di mana makespan adalah ukuran biaya.

Ini dikenal sebagai NP-keras pada grafik bintang berbobot. Namun, terbuka apakah masalahnya NP-hard di pesawat. Orang mungkin berpendapat bahwa kekerasan-NP tidak datang dari 'tree-ness', tetapi dari 'metric'-ness, tetapi grafik bintang hanya memberi Anda ruang metrik yang terbatas ..

Suresh Venkat
sumber
8

TV(T)kϕ:V(T){1,,k}Tii+1KK

k

pengguna13136
sumber
8

Kekaisaran mewarnai adalah NP-keras untuk pohon.

rsGr(s,r)sCOLrGs

sCOLrs{3,,2r1}s

Jens G.
sumber
6

TSTT1TSTT1T

Masalahnya adalah NP-hard (sebenarnya, sulit untuk perkiraan) hanya ketika semua pohon input memiliki derajat tidak terbatas.

Gianluca Della Vedova
sumber
6

Pewarnaan yang harmonis dari grafik sederhana adalah pewarnaan simpul yang tepat sehingga setiap pasangan warna muncul paling banyak di satu sisi. Harmaticious Chromatic Number dari suatu grafik adalah jumlah warna yang paling sedikit dalam pewarnaan grafik yang harmonis. Masalah menemukan Harmonicious Chromatic Number ini terbukti NP-complete pada pohon oleh Edwards dan McDiarmid . Bahkan, mereka juga menunjukkan bahwa masalah tetap NP-lengkap untuk pohon radius 3.

Ashutosh Rai
sumber
5

uu

Perhatikan bahwa dalam masalah TSP terkait (dan lebih terkenal), tujuannya adalah untuk meminimalkan maksimum, daripada latensi rata-rata. Saya pikir TRP umumnya dianggap masalah yang lebih rumit (sebenarnya TSP dalam P untuk metrik pohon).

Kekerasan NP pada pohon ditunjukkan dalam RA Sitter "Masalah Latensi Minimum Apakah NP-Sulit untuk Pohon Tertimbang", ISCO 2002.

Michael Lampis
sumber
1
Itu masalah yang bagus!
Tayfun Bayar
3

Ada masalah (sangat umum) yang saya lihat sebagai bagian dari proyek: varian masalah ini tetap NP-hard bahkan pada grafik dengan dua simpul dan satu tepi, dan varian berbeda NP-hard pada pohon. Karena NP-hardness dari varian pertama jelas tidak berasal dari bentuk grafik, yang kedua mungkin lebih menarik.

SCG=(V,E)SVCVSC=sS|s|FfF|f|eEteRC×F(c,f)Rcf

sSAsfAs|f||s|PrGr=(c,f)RcsfAseDer=(c,f)DePre(c,f)De|f|te

Jika Anda tidak memerlukan semua download akan dialihkan melainkan mencoba untuk memaksimalkan jumlah dari filesizes dari download yang sedang diarahkan Anda dapat dengan mudah mengurangi bagian-sum untuk masalah ini: Anda memiliki server tunggal dengan sejumlah besar ruang, klien tunggal yang terhubung ke server dengan keunggulan dengan kapasitas yang sama dengan nilai target instance subset-sum dan untuk setiap integer dalam instance subset-sum Anda membuat file dengan ukuran yang sama; klien kemudian ingin mengunduh semua file ini.

Varian (lebih?) Yang lebih menarik untuk pertanyaan ini adalah kasus yang Anda coba untuk meminimalkan jumlah sisi yang kapasitasnya terlampaui - mungkin jaringan yang sedang kami kerjakan memodelkan kabel internet transatlantik dan mengganti kabel sangat mahal sehingga perbedaannya dalam biaya upgrade ke faktor dua lebih cepat dan upgrade ke faktor tiga lebih cepat diabaikan. Kami juga mengatakan bahwa penempatan file di server sudah diberikan dan tidak dapat dimodifikasi, jadi kami hanya melihat masalah perutean.

USP(U)uU

sSusu

Idenya adalah bahwa klien membutuhkan file yang unik untuk semua cluster server, sehingga ujung-ujungnya yang menghubungkan klien ke cluster server sudah pada batas kapasitasnya (kapasitasnya 1, file memiliki ukuran 1). Jika klien mengunduh elemen alam semesta dari gugus mana pun, ujung yang terhubung ke gugus itu menjadi kelebihan beban. Karena kita hanya perlu memperkecil jumlahnyakelebihan (dan bukan oleh seberapa banyak kita melebihi kapasitas), klien dapat mengunduh sisa elemen alam semesta yang dihosting di server cluster (jadi sisa elemen dari subset yang sesuai) tanpa penalti. Oleh karena itu ini sesuai dengan subset yang dipilih. Klien ingin mengunduh semua file di jagat raya sekali, sehingga jagat raya memang akan tercakup, dan untuk meminimalkan jumlah tepi yang kelebihan beban kita perlu meminimalkan jumlah himpunan bagian yang dipilih.

Perhatikan bahwa konstruksi di atas menghasilkan grafik pohon, jadi ini adalah contoh masalah NP-hard pada pohon.

Alex ten Brink
sumber
3

Masalah Aliran yang Tidak Dapat Dicabut. Bahkan UFP sulit bahkan di satu sisi (Knapsack).

Arindam Pal
sumber
3

G(V,E)NP

Secara formal, masalahnya adalah:

ISOMORFISME GRAF YANG TERPASANG

T=(V,E)

{E1,E2}ET1=(V,E1)T2=(V,E2)

Kolom NP-kelengkapan mengutip naskah Graham dan Robinson yang tidak diterbitkan, "faktorisasi isomorfik IX: pohon-pohon".

DS Johnson, Kolom NP-kelengkapan: panduan berkelanjutan, Journal of Algorithms 3 (1982), 288–300

Mohammad Al-Turkistany
sumber
2

Entah bagaimana saya melewatkan masalah Nomor Achromatic di jawaban terakhir, tapi ini adalah salah satu masalah paling alami yang saya tahu, yang NP-lengkap pada pohon.

Pewarnaan lengkap dari grafik adalah pewarnaan yang tepat sehingga ada keunggulan di antara setiap pasangan kelas warna. Pewarnaan dapat dinyatakan berbeda dengan Harmonious Coloring, sebagai pewarnaan yang tepat sehingga setiap pasangan warna muncul di setidaknya satu sisi. Juga, itu dapat dinyatakan sebagai homomorfisme lengkap (atau penuh) untuk sebuah klik. Masalah Achromatic Number adalah masalah maksimalisasi , di mana kami mencari jumlah kelas warna terbesar dalam pewarnaan grafik yang lengkap.

Yannakakis dan Gravil membuktikan masalah ini sebagai NP-hard pada melengkapi Grafik Bipartit . Cairnie dan Edwards memperluas hasil itu dan menunjukkan bahwa masalahnya adalah NP-complete pada pohon .

Banyak pekerjaan yang telah dilakukan pada masalah ini di bidang Algoritma Aproksimasi [ 3 , 4 , 5 ].

Ashutosh Rai
sumber
2

nknk

pengguna1105
sumber
-1

Apakah Circuit SAT di pohon NPC ?. Simpul dalam pohon diberi label sebagai gerbang OR / AND. Daun adalah input. Tentukan apakah ada rangkaian input yang memuaskan untuk dievaluasi rangkaian ke True.

2k1

Chad Brewbaker
sumber
1
Umm, sirkuit yang berupa pohon memiliki nama: rumus. Formula SAT tentu saja NP-complete, karena 3-SAT atau bahkan CNF-SAT penuh adalah kasus khusus.
Emil Jeřábek mendukung Monica
1
Bagaimana? Semua formula adalah pohon. Jika Anda ingin membatasi beberapa variabel, itu merupakan kendala tambahan. (Saya juga berasumsi bahwa ketika Anda menulis "input", Anda benar-benar berarti "literal", sebagai Sirkuit SAT dengan hanya AND, OR, dan literal positif sepele untuk waktu polinomial untuk memulai.)
Emil Jeřábek mendukung Monica
1
((a+b)+c)+d((a+b)+c)+a
1
(pq)p
1
Ini bukan masalah mainan. Ini adalah terminologi standar, ketika ketika kita mengatakan sirkuit adalah pohon, itu tidak berarti variabel hanya muncul sekali. Dalam kasus apa pun dan terlepas dari apa yang kami sebut masalah yang Anda usulkan itu sepele seperti yang saya tulis.
Kaveh