Dekomposisi grafik untuk menggabungkan fungsi "lokal" dari pelabelan titik

\sum_{x} \prod_{i j \in E} f (x_{i}, x_{j})

$\sum_x \prod_{ij \in E} f(x_i,x_j)$

max_{x} \prod_{i j \in E} f (x_{i}, x_{j})

$\max_x \prod_{ij \in E} f(x_i,x_j)$

Di mana maks atau jumlah diambil alih semua pelabelan , produk diambil dari semua sisi untuk grafik dan adalah fungsi arbitrer. Kuantitas ini mudah ditemukan untuk grafik lebar pohon yang dibatasi dan pada umumnya NP-hard untuk grafik planar. Jumlah pewarnaan yang tepat, set independen maksimum dan jumlah subgraph Euler adalah contoh khusus dari masalah di atas. Saya tertarik dengan skema perkiraan waktu polinomial untuk masalah semacam ini, terutama untuk grafik planar. Dekomposisi grafik apa yang berguna? $V$ $E$ $G=\{V,E\}$ $f$

Sunting 11/1 : Sebagai contoh, saya bertanya-tanya tentang dekomposisi yang mungkin analog dengan ekspansi cluster fisika statistik (yaitu, ekspansi Mayer). Ketika $f$ mewakili interaksi yang lemah, ekspansi seperti itu bertemu, yang berarti bahwa Anda dapat mencapai akurasi yang diberikan dengan ketentuan ekspansi $k$ terlepas dari ukuran grafik. Bukankah ini menyiratkan keberadaan PTAS untuk kuantitas?

Pembaruan 02/11/2011

Ekspansi suhu tinggi menulis ulang fungsi partisi $Z$ sebagai penjumlahan dari istilah di mana syarat tatanan yang lebih tinggi bergantung pada interaksi tatanan yang lebih tinggi. Ketika "korelasi peluruhan", istilah orde tinggi meluruh cukup cepat sehingga hampir semua massa $Z$ terkandung dalam jumlah terbatas dari orde rendah.

Sebagai contoh untuk model Ising pertimbangkan ekspresi fungsi partisi berikut

Z = \sum_{x \in X} \exp J \sum_{i j \in E} x_{i} x_{j} = c \sum_{A \in C} (\tanh J)^{| A |}

$Z=\sum_\mathbf{x\in \mathcal{X}} \exp J \sum_{ij \in E} x_i x_j = c \sum_{A\in C} (\tanh J)^{|A|}$

Di sini konstanta sederhana, adalah himpunan subgraf Euler dari grafik kita,adalah jumlah sisi dalam graf . $c$ $C$ $|A|$ $A$

Kami memiliki fungsi partisi yang ditulis ulang sebagai penjumlahan dari subgraph di mana setiap istilah dalam penjumlahan tersebut secara eksponensial dihukum oleh ukuran subgraph tersebut. Sekarang istilah grup dengan eksponen yang sama bersama-sama dan perkiraan dengan mengambil istilah pertama . Ketika jumlah subgraf Euler ukuran tidak tumbuh terlalu cepat, kesalahan perkiraan kami meluruh secara eksponensial dengan . $Z$ $k$ $p$ $k$

Penghitungan perkiraan sulit secara umum, tetapi mudah untuk contoh "pembusukan korelasi". Misalnya, dalam kasus model Ising, ada pembusukan korelasi ketika tumbuh lebih lambat daripada mana adalah jumlah subgraf Euler ukuran . Saya percaya dalam kasus seperti itu, memotong ekspansi suhu tinggi memberikan PTAS untuk $f(k)$ $(\tanh J)^k$ $f(k)$ $k$ $Z$

Contoh lain adalah penghitungan set independen berbobot - ini dapat digunakan untuk grafik apa pun jika beratnya cukup rendah karena Anda dapat membuat masalah tersebut menunjukkan peluruhan korelasi. Kuantitas kemudian diperkirakan dengan menghitung set independen di wilayah ukuran terbatas. Saya percaya hasil STOC'06 Dror Weitz menyiratkan bahwa penghitungan set independen yang tidak berbobot dimungkinkan untuk setiap grafik dengan derajat maksimum 4.

Saya telah menemukan dua keluarga dekomposisi "lokal" - antara grafik cluster dan grafik wilayah Kikuchi. Karena dekomposisi pada dasarnya memberitahu Anda untuk melipatgandakan jumlah di wilayah, dan membaginya dengan jumlah di wilayah yang tumpang tindih. Metode grafik wilayah Kikuchi meningkatkan hal ini dengan memperhitungkan bahwa tumpang tindih wilayah dapat dengan sendirinya tumpang tindih, menggunakan jenis koreksi "inklusi-pengecualian".

Pendekatan alternatif adalah menguraikan masalah menjadi bagian-bagian global yang dapat ditelusuri, seperti dalam, "Variational Inference over Combinatorial Spaces". Namun, dekomposisi lokal memungkinkan Anda untuk mengontrol kualitas perkiraan dengan memilih ukuran wilayah

ds.algorithms graph-theory graph-algorithms approximation-algorithms counting-complexity Yaroslav Bulatov
sumber

Apa yang ingin saya katakan terlalu panjang untuk (tetapi harus benar-benar) komentar.

Jika saya membaca pertanyaan dengan benar, Anda menginginkan FPRAS (skema perkiraan acak lengkap polinomial) untuk salah satu dari jumlah di atas, yang masing-masing mencakup berbagai masalah # P-complete sebagai kasus khusus. Secara khusus, Anda menginginkan FPRAS umum dalam kasus grafik planar, dengan menggunakan ekspansi cluster.

Saya ragu bahwa ini dimungkinkan karena fakta bahwa NP-kelengkapan masalah keberadaan (misalnya pewarnaan yang tepat) menyiratkan bahwa masalah penghitungan yang sesuai (misalnya jumlah pewarnaan yang tepat) selesai di # P sehubungan dengan AP-reducibility (aproksimasi- melestarikan). Lihat Dyer, Goldberg, Greenhill dan Jerrum, Algorithmica (2004) 38: 471-500.

Tapi mungkin saya salah membaca pertanyaan.

(Sebenarnya, apakah Anda bisa menjelaskan kepada yang belum tahu arti dari ekspansi suhu tinggi?)

RJK
sumber

Saya telah menjawab pertanyaan saya

Yaroslav Bulatov

@Yaroslav: Terima kasih atas klarifikasi yang luas! BTW, menurut "wilayah" maksud Anda "simpul bagian"? (Inilah yang saya lihat ketika saya melihat Heske, JAIR 26 (2006), 153-190.) Jadi sebenarnya Anda mencari FPRAS tertentu (yaitu, dengan pilihan f tertentu) untuk kelas tertentu (seperti gelar di paling 4) dari grafik planar menggunakan apa yang Anda sebut sebagai "dekomposisi grafik" (yang merupakan istilah yang sangat kelebihan beban, agar adil). Apakah itu benar?

RJK

Ya, region adalah himpunan bagian verteks, dan saya tertarik pada PTAS untuk kelas grafik "traktable". BTW, berikut ini adalah contoh dekomposisi kluster untuk menghitung set independen yang saya pikir dapat diubah menjadi PTAS untuk contoh dengan pembusukan korelasi - yaroslavvb.blogspot.com/2011/02/…

Yaroslav Bulatov

Dekomposisi grafik untuk menggabungkan fungsi "lokal" dari pelabelan titik

Jawaban: