Perangkat lunak untuk menguji homomorfisme grafik

Saya punya grafik $G_k$ dan $H_k$ dengan $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ dengan $k\in\Bbb N$yang lulus pemeriksaan kewarasan seperti lemma tanpa homomorfisme. Apakah ada alat gratis dan mudah digunakan untuk menguji homomorfisme grafik$G$ untuk $H$?

Cara terbaik (dalam hal kemalasan) adalah dengan menggunakan alat Sage yang tersedia secara bebas yang memiliki dukungan terbaik untuk teori grafik.

Contoh

sage: G = graphs.PetersenGraph()
sage: G.has_homomorphism_to(graphs.CycleGraph(5))
False
sage: G.has_homomorphism_to(graphs.CompleteGraph(5))
{0: 0, 1: 1, 2: 0, 3: 1, 4: 2, 5: 1, 6: 0, 7: 2, 8: 2, 9: 1}

Salah satu pendekatan akan menggunakan solver SAT.

Memperkenalkan variabel boolean $x_{t,v}$ untuk setiap titik $t$ dari $G$ dan setiap titik $v$ dari $H$. Intuisinya adalah itu$x_{t,v}$ akan benar jika peta homomorfisme $t \mapsto v$. (Tentu saja, jika Anda memiliki kandidat set simpul yang lebih kecil$t$bisa memetakan ke - mungkin dipersempit menggunakan pertimbangan derajat atau kriteria lokal lainnya - maka Anda dapat mengurangi jumlah variabel boolean sesuai. Jenis preprocessing ini dapat meningkatkan efisiensi pendekatan ini secara signifikan.)

Selanjutnya, tambahkan dua jenis klausa / batasan:

• Tambahkan beberapa klausa yang mengharuskan pemetaan ini membentuk homomorfisme grafik. Khususnya, untuk setiap sisi$(t,u) \in E(G)$, tambahkan kendala

  $$\bigvee_{(v,w) \in E(H)} (x_{t,v} \land x_{u,w}).$$

  (Anda dapat mengonversikan ini ke 3CNF menggunakan transformasi Tseitin standar.)

• Tambahkan beberapa klausa untuk mengharuskan setiap simpul $t$ dari $G$ peta ke tepat satu titik $v$ dari $H$. Ada sejumlah metode standar untuk menyandikan batasan ini. Salah satu cara sederhana adalah, untuk setiap simpul$t \in V(G)$, tambahkan klausa

  $$\bigvee_{v \in V(H)} x_{t,v}$$

  dan klausa

  $$\bigwedge_{v,w \in V(H)} (\neg x_{t,v} \lor \neg x_{t,w}).$$

Kemudian, Anda dapat menggunakan pemecah SAT standar apa pun. Saya tidak tahu seberapa baik itu akan berhasil dalam prakteknya, tetapi Anda bisa mencobanya dan melihat bagaimana hasilnya.

Dalam literatur penelitian, masalah grafik homomorfisme telah dipelajari secara ekstensif untuk grafik dengan sifat khusus (misalnya, di mana $H$ adalah klik, whre $H$telah terikat treewidth, dan sebagainya). Jika Anda mengetahui sesuatu yang istimewa tentang struktur grafik Anda, dimungkinkan untuk menemukan algoritma yang lebih baik untuk masalah Anda. Untuk grafik umum, masalah ini dikenal sebagai NP-hard.