CSP dengan lebar hypertree fraksional tak terbatas

$\acute{\rm a}$$H$$H$$\in PTIME$

Definisi, dll.

Untuk survei hebat dekomposisi dan treewidth pohon standar, lihat di sini (Terima kasih sebelumnya, JeffE!).

Biarkan $H$ menjadi hypergraph.

Kemudian untuk H hypergraph $H$dan pemetaan $\gamma : E(H) \rightarrow [0,\infty)$ ,

$B(\gamma) =$ { $v \in V(H) : \sum_{e \in V(H), v \in e} \gamma(e) \ge 1$ }.

Selain itu, biarkan bobot ( $\gamma$ ) = $\sum_{e \in E}\gamma(e)$ .

Kemudian dekomposisi hypertree fraksional $H$ adalah triple $(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$ , di mana:

• $(T, (B_t)_{t \in V(T)})$ adalah dekomposisi pohon $H$ , dan
• $(\gamma_t)_{t \in V(T)}$ adalah keluarga pemetaan dari $E(H)$ hingga $[0, \infty)$ st untuk setiap $t \in V(T), B_t \subseteq B(\gamma_t)$ .

Kemudian kita mengatakan lebar dari adalah {berat }.$(T, (B_t)_{t \in V(T)}, (\gamma_t)_{t \in V(T)})$$\max$$(\gamma_t), t \in V(T)$

Akhirnya, lebar hypertree pecahan dari , FHW ( ), adalah minimal lebar atas semua kemungkinan dekomposisi hypertree pecahan .$H$$H$$H$

Pertanyaan

Seperti yang dinyatakan di atas, jika lebar hypertree fraksional dari grafik yang mendasari CSP dibatasi oleh konstanta, maka ada algoritma waktu polinomial untuk menyelesaikan CSP. Namun, itu dibiarkan sebagai masalah terbuka pada akhir makalah terkait apakah ada keluarga polinomial waktu dipecahkan contoh CSP memiliki lebar hypertree tak terbatas. (Saya juga harus menunjukkan, pertanyaan ini sepenuhnya diselesaikan dalam kasus treewidth terikat vs tidak terikat ( kutipan ACM ) dengan asumsi bahwa .) Karena ada beberapa waktu sejak makalah yang ditautkan pertama kali, ditambah saya relatif tidak mengetahui keadaan umum sub-bidang ini, pertanyaan saya adalah:$FPT \ne W[1]$

Apakah sesuatu yang diketahui tentang (in) tractability dari CSP lebih grafik dengan lebar hypertree pecahan tak terbatas?

Anda ditautkan ke dua makalah, keduanya dengan dugaan. Saya kira Anda maksud dugaan 2007 Grohe.

Pertanyaan ini dijawab pada tahun 2008:

Teorema 5. CSP (C , _) dalam NP, tetapi tidak dalam P atau NP-complete (kecuali P = NP). Selain itu, himpunan C dapat diputuskan dalam waktu polinomial deterministik.$_0$$_0$

• Manuel Bodirsky dan Martin Grohe, Non-dikotomi dalam Constraint Satisfaction Complexity , ICALP 2008. doi: 10.1007 / 978-3-540-70583-3_16 ( PDF )

Idenya adalah untuk meledakkan lubang dalam ukuran contoh CLIQUE, dengan teknik diagonalisasi tertunda yang sama yang diperkenalkan oleh Ladner untuk teorinya. Perhatikan bahwa himpunan C berisi klik-klik besar yang sewenang-wenang, dan lebar hypertree fraksional dari -clique adalah . Jadi dimungkinkan untuk memiliki CSP dalam bentuk CSP (A, _) yang memiliki kompleksitas menengah, di mana A memiliki lebar hiperree pecahan yang tidak terbatas. Ini menjawab dugaan Grohe dalam negatif.$_0$$n$$n/2$

Pada konferensi yang sama, Chen, Thurley, dan Weyer memiliki sebuah makalah dengan hasil yang serupa, tetapi itu membutuhkan embeddings yang kuat sehingga secara teknis bukan bentuk yang tepat untuk dugaan tersebut.

• Yijia Chen, Marc Thurley, dan Mark Weyer, Memahami Kompleksitas Isomorfisme Subgraph Terinduksi , ICALP 2008. doi: 10.1007 / 978-3-540-70575-8_48 ( PDF )

Akhirnya, setiap kelas instance CSP dapat ditransformasikan menjadi representasi dengan lebar hipertensi pecahan kasus terburuk. Dalam banyak kasus, transformasi ini dibatasi secara polinomial dan dapat dilakukan dalam waktu polinomial. Ini berarti bahwa mudah untuk menghasilkan CSP dengan lebar fraksional pecahan yang tidak terbatas, bahkan kesetaraan homomorfik modulo. CSP ini tidak akan berbentuk CSP (A, _) karena struktur targetnya spesial, tetapi mereka memberikan alasan yang rapi mengapa CSP yang didefinisikan dengan membatasi hanya struktur sumbernya tidak terlalu menarik: seringkali hanya terlalu mudah untuk menyembunyikan struktur mirip pohon instance CSP dengan mengubah representasi sehingga struktur sumber memiliki lebar yang besar. (Ini dibahas dalam bab 7 dari tesis saya .)