Apa yang memisahkan masalah global yang mudah dari masalah global yang sulit pada grafik treewidth terikat?

Banyak masalah grafik yang sulit dipecahkan dalam waktu polinomial pada grafik treewidth terikat . Memang, buku teks biasanya menggunakan eg set independet sebagai contoh, yang merupakan masalah lokal . Secara kasar, masalah lokal adalah masalah yang solusinya dapat diverifikasi dengan memeriksa beberapa lingkungan kecil dari setiap titik.

Yang menarik, bahkan masalah (seperti jalur Hamilton) yang bersifat global masih dapat diselesaikan secara efisien untuk grafik treewidth yang dibatasi. Untuk masalah seperti itu, algoritma pemrograman dinamis biasa harus melacak semua cara di mana solusi dapat melintasi pemisah yang sesuai dari dekomposisi pohon (lihat misalnya [1]). Algoritma acak (berdasarkan apa yang disebut cut'n'count) diberikan pada [1], dan algoritma yang ditingkatkan (bahkan deterministik) dikembangkan dalam [2].

Saya tidak tahu apakah adil untuk mengatakan bahwa banyak, tetapi setidaknya beberapa masalah global dapat diselesaikan secara efisien untuk grafik treewidth terikat. Jadi bagaimana dengan masalah yang tetap sulit pada grafik seperti itu? Saya berasumsi mereka juga bersifat global, tetapi apa lagi? Apa yang memisahkan masalah-masalah global yang sulit ini dari masalah-masalah global yang dapat diselesaikan secara efisien? Misalnya, bagaimana dan mengapa metode yang dikenal gagal memberi kita algoritma yang efisien untuk mereka?

Misalnya, seseorang dapat mempertimbangkan masalah berikut:

Tepi precoloring ekstensi Mengingat grafik dengan beberapa tepi berwarna, memutuskan apakah pewarnaan ini dapat diperpanjang untuk tepat -edge-mewarnai grafik .k $G$$k$$G$

Ekstensi edge precoloring (dan varian pewarnaan edge list-nya) adalah NP-lengkap untuk grafik paralel-seri bipartit [3] (grafik tersebut paling banyak 2).

Pewarnaan jumlah penjumlahan minimum Diberikan grafik $G=(V,E)$ , temukan pewarnaan tepi $\chi : E \to \mathbb{N}$ sedemikian rupa sehingga jika $e_1$ dan $e_2$ memiliki simpul umum, maka $\chi(e_1) \neq \chi(e_2)$ . Tujuannya adalah untuk meminimalkan $E'_\chi(E) = \sum_{e \in E} \chi(e)$ , jumlah pewarnaan.

Dengan kata lain, kita harus menetapkan bilangan bulat positif ke tepi grafik sehingga tepi yang berdekatan menerima bilangan bulat yang berbeda dan jumlah angka yang ditetapkan minimal. Masalah ini NP-hard untuk parsial 2-pohon [4] (yaitu grafik treewidth paling banyak 2).

Masalah-masalah sulit lainnya termasuk masalah edge-disjoint paths, masalah subgraph isomorphism, dan masalah bandwidth (lihat misalnya [5] dan referensi di dalamnya). Untuk masalah yang tetap sulit bahkan di pohon, lihat pertanyaan ini .

[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, JM, & Wojtaszczyk, JO (2011, Oktober). Memecahkan masalah konektivitas yang diparameterisasi oleh treewidth dalam waktu eksponensial tunggal. Dalam Yayasan Ilmu Komputer (FOCS), Simposium Tahunan ke-52 IEEE 2011 tentang (hlm. 150-159). IEEE.

[2] Bodlaender, HL, Cygan, M., Kratsch, S., & Nederlof, J. (2013). Algoritma waktu eksponensial tunggal deterministik untuk masalah konektivitas diparameterisasi oleh treewidth. Dalam Automata, Bahasa, dan Pemrograman (hlm. 196-207). Springer Berlin Heidelberg.

[3] Marx, D. (2005). NP-kelengkapan pewarnaan daftar dan ekstensi precoloring di tepi grafik planar. Jurnal Teori Grafik, 49 (4), 313-324.

[4] Marx, D. (2009). Hasil kerumitan untuk pewarnaan tepi jumlah minimum. Matematika Terapan Diskrit, 157 (5), 1034-1045.

[5] Nishizeki, T., Vygen, J., & Zhou, X. (2001). Masalah edge-disjoint paths adalah NP-complete untuk grafik seri-paralel. Matematika Terapan Diskrit, 115 (1), 177-186.

Kebanyakan algoritma untuk grafik treewidth terikat didasarkan pada beberapa bentuk pemrograman dinamis. Agar algoritma ini efisien, kita perlu mengikat jumlah status dalam tabel pemrograman dinamis: jika Anda ingin algoritma waktu polinomial, maka Anda memerlukan jumlah polinomial status (misalnya, n ^ tw), jika Anda ingin menunjukkan bahwa masalahnya adalah FPT, Anda biasanya ingin menunjukkan bahwa jumlah negara adalah beberapa fungsi treewidth. Jumlah negara biasanya sesuai dengan jumlah berbagai jenis solusi parsial ketika memecah grafik di beberapa pemisah kecil. Dengan demikian masalah mudah pada grafik terikat-treewidth biasanya karena solusi parsial berinteraksi dengan dunia luar melalui jumlah simpul terbatas hanya memiliki jumlah jenis terbatas. Sebagai contoh, dalam masalah himpunan independen jenis solusi parsial hanya bergantung pada simpul batas mana yang dipilih. Dalam masalah siklus Hamiltonian, jenis solusi parsial dijelaskan oleh bagaimana subpath dari solusi parsial cocok dengan simpul-simpul batas satu sama lain. Varian dari Courcelle's Teorem memberikan kondisi yang cukup untuk masalah untuk memiliki properti yang sebagian solusi hanya memiliki jumlah tipe terbatas.

Jika masalah sulit pada grafik terikat-treewidth, maka biasanya karena salah satu dari tiga alasan berikut.

1. Ada interaksi dalam masalah yang tidak ditangkap oleh grafik. Sebagai contoh, Steiner Forest NP-keras pada grafik treewidth 3, secara intuitif karena pasangan sumber-tujuan menciptakan interaksi antara simpul yang tidak berdekatan.

Elisabeth Gassner: Masalah Hutan Steiner ditinjau kembali. J. Discrete Algorithms 8 (2): 154-163 (2010)

Mohammad Hussein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx: Skema Perkiraan untuk Hutan Steiner pada Grafik Planar dan Grafik Treewidth Terikat. J. ACM 58 (5): 21 (2011)

2. Masalahnya didefinisikan di tepi grafik. Kemudian bahkan jika suatu bagian dari grafik dilampirkan pada sisa grafik melalui sejumlah simpul yang dibatasi, mungkin ada banyak tepi yang bersinggungan dengan beberapa simpul tersebut dan kemudian keadaan dari solusi parsial dapat dijelaskan hanya dengan menggambarkan keadaan dari semua tepi ini. Inilah yang membuat masalah dalam [3,4] sulit.

3. Setiap simpul dapat memiliki sejumlah besar keadaan yang berbeda. Sebagai contoh, Capacitated Vertex Cover adalah W [1] -sekarang diparameterisasi oleh treewidth, secara intuitif karena deskripsi dari solusi parsial tidak hanya menyatakan simpul mana dari pemisah yang dipilih, tetapi juga menyatakan berapa kali setiap simpul dari pemisah dipilih. digunakan untuk menutupi tepi.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Dominasi Berkapasitas dan Penutupan: Perspektif Parameter. IWPEC 2008: 78-90

Saran saya adalah untuk melihat dengan hati-hati pada teorema Courcelle , bahwa masalah yang dapat diungkapkan dalam (ekstensi tertentu) logika urutan kedua monadik memiliki algoritma FPT ketika diparameterisasi oleh treewidth. Kecurigaan saya adalah bahwa ini mencakup banyak atau sebagian besar contoh masalah FPT yang diketahui untuk grafik ini. Dalam pandangan ini, perbedaan lokal / global Anda tampaknya terkait erat dengan perbedaan antara masalah yang dapat diekspresikan dalam MSO eksistensial vs masalah yang memiliki tingkat kuantifikasi yang lebih tinggi dalam formulasi MSO mereka. Untuk kembali ke pertanyaan Anda yang sebenarnya, kurangnya formulasi MSO (yang dapat dibuktikan tanpa syarat dalam banyak kasus menggunakan ide-ide yang terkait dengan teorema Myhill-Nerode ) akan menjadi bukti terhadap kurangnya algoritma FPT (lebih sulit untuk dibuktikan tanpa asumsi teoretis kompleksitas).

Saya pikir salah satu contohnya adalah masalah cut paling jarang. Masalah pemotongan sparest yang seragam dapat dipecahkan pada grafik lebar pohon yang dibatasi tetapi masalah tebang sparest yang tertimbang bahkan tidak dapat diperkirakan (lebih baik dari 17/16) dalam grafik treewidth yang dibatasi.

Ada banyak varian masalah pemotongan yang paling jarang tetapi salah satu yang terkenal adalah sebagai berikut.

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

Bahan utama terbuat dari dua hal:

1. Fungsi tambahan, seperti di sini fungsi bobot. Namun masih ada beberapa masalah dengan fungsi bobot yang tidak terlalu sulit dalam grafik lebar pohon tak berarah.

2. Sifat masalah pemotongan paling jarang. Sebenarnya keberadaan lebih dari satu ketergantungan untuk pemrograman dinamis dalam definisi masalah. Secara intuitif solusi yang baik adalah yang kita partisi grafik (dengan menghapus beberapa tepi) menjadi dua ukuran yang hampir sama, di sisi lain di partisi ini kita menghapus sebagai jumlah tepi paling sedikit yang kita gunakan. Alasan mengapa masalah ini sulit dalam grafik treewidth terikat adalah bahwa kita harus menerapkan pemrograman dinamis dalam dua arah, tetapi kedua arah bergantung satu sama lain.

Secara umum, jika masalahnya sedemikian rupa sehingga membutuhkan lebih dari satu dimensi untuk pemrograman dinamis dan juga dimensi-dimensi tersebut saling tergantung satu sama lain, maka masalahnya berpotensi menjadi sulit dalam grafik lebar pohon yang dibatasi. Kita bisa melihat pola ini di kedua masalah dalam pertanyaan serta untuk masalah pemotongan paling jarang. (Pada masalah pertama kita ingin menjaga pewarnaan sebelumnya di sisi lain menjaga pewarnaan sekecil mungkin, dalam masalah kedua jelas ada dua fungsi yang saling tergantung)