Membuat dekomposisi pohon lebar minimum bersandar pada waktu polinomial

Seperti diketahui, dekomposisi pohon pada grafik terdiri dari pohon dengan kantung terkait untuk setiap simpul , yang memenuhi kondisi berikut: $G$ $T$ $T_v \subseteq V(G)$ $v \in V(T)$

Setiap simpul dari terjadi di beberapa kantong . $G$ $T$
Untuk setiap tepi ada tas yang berisi kedua titik tepi. $G$
Untuk setiap simpul , kantung yang berisi menginduksi subtree terhubung . $v \in V(G)$ $v$ $T$

Kami juga dapat meminta kondisi berikut ini, yang disebut leanness , dari dekomposisi kami:

Untuk setiap pasangan tas , dari , jika dan dengan , lalu a) ada jalur -vertex-disjoint di , atau b) pohon berisi tepi pada jalur dari simpul ke simpul sedemikian sehingga dan set memotong semua jalur di . $T_a$ $T_b$ $T$ $A \subseteq T_a$ $B \subseteq T_b$ $|A| = |B| = k$ $k$ $A-B$ $G$ $T$ $pq$ $a$ $b$ $|V(T_p) \cap V(T_q)| \leq k$ $V(T_p) \cap V(T_q)$ $A-B$ $G$

Robin Thomas menunjukkan bahwa selalu ada dekomposisi pohon dengan lebar minimum yang juga ramping, dan bukti sederhana dari fakta ini telah diberikan oleh beberapa penulis, misalnya oleh Patrick Bellenbaum & Reinhard Diestel .

Yang saya tertarik adalah sebagai berikut: diberi grafik dan dekomposisi pohon lebar minimum , dapatkah kita menemukan dekomposisi pohon ramping lebar-lebar dalam waktu polinomial? $G$ $G$ $G$

Dua bukti yang disebutkan tidak menghasilkan konstruktifitas yang efisien. Dalam makalah Bellenbaum dan Diestel disebutkan bahwa "Bukti pendek lain (lebih konstruktif) dari teorema Thomas telah diberikan dalam P. Bellenbaum, Schlanke Baumzerlegungen von Graphen, Diplomarbeit, Universitat Hamburg 2000." Sayangnya, saya belum dapat menemukan manuskrip itu di internet dan bahasa Jerman saya tidak terlalu bagus.

ds.algorithms graph-theory graph-algorithms treewidth Bart Jansen
sumber

Pertanyaan yang bagus Menemukan dekomposisi pohon-lebar minimum adalah NP-Hard sehingga masalah Anda agak buruk (muncul). Dugaan saya adalah bahwa seseorang dapat meminta ini untuk kasus treewidth terbatas atau dalam pengertian perkiraan.

Chandra Chekuri

Tetapi dalam kasusnya dia diberi dekomposisi pohon selebar min dan dia ingin algoritma membuatnya ramping.

Suresh Venkat

@ SureshVenkat: Saya menyadari bahwa dia diberi dekomposisi pohon selebar min, tetapi bagaimana Anda dapat memverifikasi bahwa itu benar? Selain itu, dekomposisi pohon ramping beradaptasi secara lokal dengan treewidth dari berbagai bagian grafik sehingga memiliki dekomposisi pohon dari grafik global yang optimal tidak menghindari masalah menemukan treewidth dari potongan lokal yang sulit.

Chandra Chekuri

Dekomposisi pohon yang halus (di mana semua kantong memiliki ukuran yang sama dan dua kantong yang berdekatan berbeda dengan tepat satu titik) jauh lebih mudah ditangani daripada dekomposisi pohon umum, dan mudah untuk melihat bahwa selalu ada dekomposisi pohon dengan lebar minimum yang mulus . Jadi mungkin Anda bisa mendapatkan konstruksi yang efisien dengan membatasi salah satu konstruksi yang diketahui ini. Apakah selalu ada dekomposisi pohon dengan lebar minimum yang mulus dan ramping?

Diego de Estrada

@ChandraChekuri Saya menganggap masalah verifikasi hilang jika Anda menyebutnya sebagai masalah janji, tapi saya melihat maksud Anda tentang memiliki satu dekomposisi pohon yang belum tentu memberi Anda cukup info untuk beradaptasi. Tetapi pertanyaan berikut ini mungkin masuk akal: apakah ada cara untuk "secara lokal" memodifikasi dekomposisi pohon yang diberikan untuk membuatnya "bersandar" tanpa meningkatkan treewidth?

Suresh Venkat

Berikut adalah alasan formal mengapa masalahnya tidak dapat dipecahkan secara poli-waktu kecuali P = NP. Kita tahu bahwa menemukan treewidth dari grafik yang diberikan adalah NP-Hard. Mengingat grafik kita dapat menambahkan sebuah klik menguraikan ukuran untuk membuat grafik baru . Sebuah pohon-dekomposisi min-lebar dapat diperoleh sebagai berikut: memiliki dua node dengan satu tas berisi semua node dari clique dan yang lainnya berisi semua node . Sekarang membuat ini pohon-dekomposisi ramping akan membutuhkan menemukan dekomposisi ramping-pohon grafik asli yang akan, sebagai oleh-produk, memberikan treewidth dari . $G$ $V(G)+1$ $G'$ $G'$ $G$ $G$ $G$

Chandra Chekuri
sumber

Poin bagus. Apakah Anda tahu jika ada yang diketahui tentang algoritma waktu parameter dan / atau cukup eksponensial untuk menemukan dekomposisi lean tree?

Bart Jansen

Membuat dekomposisi pohon lebar minimum bersandar pada waktu polinomial

Jawaban: