Kompleksitas “adalah grafik produk”

Pertanyaan ini muncul karena rasa ingin tahu yang murni (pertanyaan itu muncul sambil berpikir tentang melepaskan tali , tetapi saya tidak yakin apakah itu benar-benar terkait) jadi saya harap itu sesuai.

Ada berbagai produk grafik, dan saya tertarik pada salah satu dari mereka di sini. Apa kompleksitas menentukan apakah grafik isomorfik untuk produk non-sepele? (Tentunya untuk produk Cartesian, K = K ◻ 1 di mana$K$$K = K \square 1$ adalah grafik dengan satu titik.)$1$

Saya telah melihat halaman "grafik faktor" dan "faktorisasi grafik" di Wikipedia, tetapi keduanya tidak saling berhubungan. Apakah masalah ini diketahui dengan nama lain?

Periksa koran Wilfried, Imrich; Iztok, Peterin, Mengenali produk Cartesian dalam waktu linier . Matematika Diskrit., 307, 3-5, Halaman: 472--483, 2007. Saya pikir Imrich memiliki lebih banyak kertas untuk produk lain.

Beberapa produk grafik dapat dikenali dalam waktu polinomial. Seperti biasa produk Cartesian adalah yang paling mudah, dan case Cartesian juga merupakan dasar untuk algoritma untuk beberapa produk lainnya. Pengenalan produk leksikografis (komposisi) setara dengan grafik isomorfisme.

Lebih detail:

Misalkan adalah kelas dari grafik sederhana hingga, dan Γ 0 adalah kelas dari grafik sederhana hingga yang mungkin memiliki loop-diri. (Jelas Γ ⊂ Γ 0. )$\Gamma$$\Gamma_0$$\Gamma \subset \Gamma_0$

Memutuskan apakah grafik input yang terhubung memiliki faktor dalam Γ 0 dapat dilakukan dalam waktu polinomial untuk produk Cartesian dan produk yang kuat, dan juga untuk produk langsung ketika$G$$\Gamma_0$ adalah non-bipartit. Memutuskan apakah G memiliki faktor Γ dalam waktu polinomial untuk produk Cartesian, tetapi tidak mungkin dalam polinomial waktu untuk produk leksikografis. Saya tidak tahu status memutuskan apakah G memiliki faktor Γ untuk produk langsung dan kuat.$G$$G$$\Gamma$$G$$\Gamma$

Hasil yang relevan dari Imrich dan Klavžar:

Teorema 4.10. Untuk grafik yang terhubung, pada n simpul dan $G$$n$$m$ tepi dapat ditemukan faktorisasi utama sehubungan dengan produk Cartesian dalam waktu menggunakan ruang O ( m ) .$O(mn)$$O(m)$

Teorema 5.43. Dekomposisi faktor prima dari graf nonbipartit yang terhubung di berkenaan dengan produk langsung dan grafik sederhana yang terhubung berkenaan dengan produk yang kuat dapat ditentukan dalam waktu polinomial.$\Gamma_0$

Hasil untuk produk Cartesian kemudian ditingkatkan menjadi waktu dan$O(m\log n)$$O(m)$

Untuk produk leksikografis:

Teorema 6.20. Masalah keputusan apakah grafik terhubung yang diberikan adalah prima sehubungan dengan produk leksikografis setidaknya sama sulitnya dengan masalah grafik isomorfisme.

Teorema 6.21. Masalah keputusan apakah grafik terhubung yang diberikan adalah prima sehubungan dengan produk leksikografis tidak lebih sulit daripada solusi dari bilangan polinomial (dalam ) masalah isomorfisme grafik, ukuran masing-masing yang juga polinomial dalam$n$$n$

Jadi memutuskan apakah sebuah grafik adalah prima sehubungan dengan produk leksikografis setara dengan GRAF ISOMORFISME, sehubungan dengan pengurangan Turing.

Kasus produk langsung dan kuat yang memiliki faktor tanpa putaran sendiri tampaknya tidak ada dari referensi yang saya lihat. Saya akan menghargai setiap petunjuk pada makalah yang membahas kasus ini, atau petunjuk mengapa itu tidak menarik.

• Wilfried Imrich dan Sandi Klavžar, Grafik Produk: Struktur dan Pengakuan . Wiley, 2000. ISBN 0-471-37039-8.

Ada algoritma linear-waktu untuk menentukan faktor utama dari grafik yang terhubung sehubungan dengan produk Cartesian. Lihat kertas karya Imrich dan Peterin.