Treewidth dan Pengepakan

9

Pertanyaan saya agak kabur. Saya bertanya-tanya apakah (dan bagaimana), kita dapat menerapkan gagasan treewidth untuk mengemas masalah dalam grafik.

Saya akan senang dengan wawasan atau referensi dari penelitian sebelumnya tentang hal ini (dengan asumsi mereka ada hubungannya). Terima kasih.

ds.algorithms reference-request graph-theory graph-algorithms approximation-algorithms Nikhil
sumber

11

Saya dapat menafsirkan pertanyaan ini dengan dua cara berbeda:

1) Ketika datang ke sifat algoritmik masalah pengemasan pada grafik treewidth terikat, Teorema Courcelle menunjukkan bahwa untuk setiap diperbaiki kita dapat secara optimal menyelesaikan masalah yang dapat diungkapkan dalam Logika Pesanan Kedua Monadik dalam waktu linier pada grafik treewidth paling banyak (lihat misalnya http://dx.doi.org/10.1093/comjnl/bxm037 $k$ $k$ untuk survei tentang sifat algoritmik dari grafik terikat-treewidth). Karena banyak masalah pengemasan dapat dirumuskan dalam MSOL, ini membuktikan kemampuan penelusuran dari banyak masalah tersebut pada grafik treewidth terikat, termasuk Set Independen, Segitiga Pengepakan, Pengepakan Siklus, pengepakan salinan titik / tepi disjoint dari grafik tetap, pengemasan vertex-disjoint model minor dari beberapa grafik H tetap, dan sebagainya. Tetapi karena keterlacakan ini meluas ke semua masalah yang terdefinisi MSOL, itu tidak spesifik untuk pengemasan.

2) Ketika datang ke hubungan grafik-struktural antara pengepakan dan treewidth, berikut ini mungkin menarik. Berkat karya Robertson dan Seymour diketahui bahwa ada fungsi sedemikian rupa sehingga setiap grafik treewidth setidaknya berisi grid sebagai minor (batas asli untuk diberikan oleh Seymour dan Robertson kemudian ditingkatkan bekerja sama dengan Thomas; lihat http://www.sciencedirect.com/science/article/pii/S0095895684710732 untuk batas terbaik saat ini). Karenanya, jika Anda memiliki struktur sehingga banyak salinan dapat dikemas ke dalam $f \colon \mathbb{N} \to \mathbb{N}$ $f(r)$ $r \times r$ $f$ $S$ $S$ $r \times r$ jaringan kecil, maka Anda tahu bahwa setiap grafik treewidth besar berisi kemasan besar salinan . Sebagai contoh, sebagai kisi (untuk genap ) berisi siklus titik-terputus-putus, maka grafik trewidth mengandung setidaknya disjoint siklus. $S$ $r \times r$ $r$ $(r/2)^2$ $f(r)$ $(r/2)^2$

Bart Jansen
sumber

Bart Mungkin ini tidak relevan, tetapi apakah Anda melihat hubungan antara rekonstruksi grafik dan lebar pohonnya? Juga apakah Anda memiliki tautan ke versi gratis makalah profes Anda? (Optimasi Kombinatorial pada Grafik Treewidth Terikat)

Saeed

Makalah treewidth tersedia di Citeseer citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.107.2561 . Adapun rekonstruksi grafik: maksud Anda adalah proses di mana, mengingat multiset dari semua subgraph yang diperoleh dengan menghapus satu simpul, Anda ingin merekonstruksi grafik asli? Tampaknya Shiva Kintali baru-baru ini melihat ke pertanyaan apakah dugaan rekonstruksi grafik itu benar untuk treewidth dua: cstheory.stackexchange.com/questions/5155/… .

Bart Jansen

Terima kasih bart, ya saya melihat pertanyaan Shiva, tapi, itu untuk satu tahun yang lalu, mungkin ada hasil baru, terima kasih semuanya.

Saeed

Situs web Shiva mencantumkan dua manuskrip pada subjek, "Pada Rekonstruksi pohon-k dan pohon grafik biasa" dan "Properti Grafik Rekonstruksi Baru" dengan catatan "pdf segera hadir" ( cs.princeton.edu/~kintali/#proprecon ). Anda dapat menghubunginya secara langsung untuk menanyakan keadaan terkini.

Bart Jansen

Setelah jawaban ini, yang terbaik menuju treewidth yang diperlukan untuk memastikan jaringan kecil ditingkatkan dengan Kawarabayashi dan Kobayashi untuk di dx.doi.org/10.4230/ LIPIcs.STACS.2012.278 , dan Seymour mengklaim peningkatan menjadi pada Agustus 2012.

r \times r

$r \times r$

2^{O (r^{2} \log r)}

$2^{O(r^2\log r)}$

2^{O (r \log r)}

$2^{O(r \log r)}$

András Salamon

7

Masalah himpunan independen maksimum adalah masalah pengepakan (Anda dapat menganggapnya sebagai pengemasan bintang terpisah), dan memiliki algoritme yang terkenal dengan waktu berjalan dalam grafik dengan treewidth paling banyak . $2^k \operatorname{poly(n)}$ $k$

Janne H. Korhonen
sumber

Terima kasih Janne atas tanggapan Anda. Saya mengetahui algoritma MIS. Selain MIS, sudahkah konsep treewidths diterapkan pada pengemasan struktur lain? Juga, saya tidak sepenuhnya yakin untuk menganggap MIS sebagai pengemasan bintang-bintang yang terpisah, dapatkah Anda menjelaskan maksud Anda tentang ini? (struktur bintang mana yang Anda coba kemas, apa pengertian "bintang terputus-putus")?

Nikhil

1

Ini tidak sesederhana yang saya pikir ketika memposting jawabannya. "Pengepakan bintang-bintang yang terpisah-pisah" akan lebih tepat, dan kemudian Anda harus meminta bintang yang ditempatkan memiliki derajat sebesar mungkin. Saya tidak ingat melihat treewidth diterapkan pada masalah pengemasan yang lebih kompleks.

Janne H. Korhonen

1

Perangkat independen maksimum tentu merupakan "masalah pengepakan" dalam terminologi yang biasa; contoh lain dari masalah pengepakan adalah pencocokan maksimum. (Mereka mengemas program integer; LP relaksasi adalah LP pengemasan.)

Jukka Suomela

6

Referensi yang bagus tentang topik ini adalah artikel survei Bruce Reed di bawah ini.

Reed, B. (1997). Lebar dan kusut pohon: Ukuran konektivitas baru dan beberapa aplikasi. Survei dalam kombinatorik, 241, 87-162.

Salah satu makalah saya baru-baru ini memungkinkan seseorang untuk memotong teorema grid-minor dalam beberapa kasus melalui teorema dekomposisi treewidth. Lihat kertas di bawah ini.

Dekomposisi dan Aplikasi Grafik Treewidth Besar http://arxiv.org/abs/1304.1577

Chandra Chekuri
sumber

5

Ini juga jawaban yang tidak jelas. Ada dualitas yang mirip dengan teorema Erdos-Posa untuk grafik treewidth terikat. Lihat, misalnya Fedor V. Fomin, Saket Saurabh, Dimitrios M. Thilikos: Memperkuat properti Erdös-Pósa untuk kelas grafik kecil-tertutup. Jurnal Teori Grafik 66 (3): 235-240 (2011)

R2-D2
sumber

Treewidth dan Pengepakan

Jawaban: