Memutuskan homomorfisme grafik

Deciding Graph Homomorphism secara umum NP-Complete.

Apakah ada hasil yang mempelajari masalah ini ketika grafik yang mendasari memiliki struktur aljabar (seperti memutuskan homomorfisme dari grafik Cayley atau Cayley coset ke grafik lain dengan beberapa struktur tertentu juga)? Selain hasil kompleksitas saya juga tertarik pada teknik aljabar dan / atau spektral yang bermanfaat.

Jika adalah kelas grafik dengan treewidth terikat, maka masalah homomorfisme dari grafik di G adalah waktu polinomial yang dapat dipecahkan. Ini dapat digeneralisasi ke properti yang lebih umum dari "grafik yang intinya telah membatasi treewidth."$\mathcal{G}$$\mathcal{G}$

Grohe membuktikan kebalikannya: jika inti dari grafik di memiliki treewidth yang tidak terikat, maka masalah homomorfisme dari G bukanlah waktu polinomial yang dapat dipecahkan (dengan asumsi F P T ≠ W [ 1 ] ). Oleh karena itu, jika Anda membatasi grafik sisi kiri ke grafik Cayley dll., Maka yang penting adalah apakah core telah terikat treewidth.$\mathcal{G}$$\mathcal{G}$$FPT\neq W[1]$

http://dl.acm.org/authorize?951212

Perhatikan bahwa ini tidak sepenuhnya menjawab pertanyaan Anda: dalam hasil Grohe, diasumsikan bahwa grafik sisi kanan sewenang-wenang. Anda tampaknya tertarik pada hasil di mana grafik sebelah kanan juga dibatasi untuk beberapa kelas grafik tertentu.

Memutuskan apakah ada grafik homomorfisma lebih mudah daripada menghitung jumlah homomorfisme grafik (berbobot).

Kasing Tertimbang

Untuk grafik target yang tidak diarahkan (yaitu jumlah homomorfisme grafik tertimbang dari grafik input G ke H ), ada teorema dikotomi.$H$$G$$H$

Jin-Yi Cai, Xi Chen, Pinyan Lu. Grafik Homomorfisme dengan Nilai Kompleks: Teorema Dikotomi .

$H$

$H$$H$

$q$$q$$q$

Kasus Tidak Tertimbang

Kasing tidak tertimbang jauh lebih sederhana. Di bawah ini, saya menyatakan Teorema 1.1 dari makalah berikut.

Martin Dyer, Catherine Greehill. Kompleksitas penghitungan homomorfisme grafik . (Juga tautan langsung ini ke PDF gratis.)

Teorema 1:

$H$$H$$H$