Apakah ada algoritma yang efisien untuk menentukan apakah suatu grafik memiliki automorfisme non-sepele?

Saya sedang mengerjakan masalah yang terkait dengan kotak Latin, dan saya ingin metode untuk apa yang intinya bermuara pada masalah keputusan:

Input : Grafis terbatas, sederhana G.
Output : YESjika G memiliki automorfisme non-sepele, NOjika tidak.

Karenanya...

Pertanyaan : Apakah ada algoritma yang efisien untuk menentukan apakah suatu grafik memiliki automorfisme non-sepele?

Kita dapat menggunakan Nauty atau Bliss (dan mungkin beberapa paket lain) untuk menghitung seluruh kelompok automorfisme, tetapi saya tidak membutuhkannya; yang saya perlu menentukan adalah apakah itu sepele atau tidak.

Ada kemungkinan masalah keputusan ini secara teoritis setara dalam kompleksitas untuk "menghitung seluruh kelompok automorfisme" dalam beberapa cara. Saya tidak yakin.

Untuk tujuan saya, "efisien" pada dasarnya berarti "lebih cepat dalam praktek daripada menghitung seluruh kelompok automorfisme", tetapi saya juga tertarik pada teori di baliknya.

algorithms graphs graph-theory reference-request Rebecca J. Stones
sumber

Ini setara dengan isomorfisme grafik.

Yuval Filmus

@YuvalFilmus Sejauh yang saya ketahui, tidak ada pengurangan yang diketahui dari "Is

isomorphic menjadi

" menjadi "Apakah

memiliki automorfisme nontrivial." Jelas, jika

maka serikat pekerja menguraikan mereka memiliki automorphism trivial (pertukaran

dan

) tetapi setiap automorphism trivial dari

juga akan menjadi automorphism trivial dari

G_{1}

$G_1$

G_{2}

$G_2$

G

$G$

G_{1} ≃ G_{2}

$G_1\simeq G_2$

G_{1}

$G_1$

G_{2}

$G_2$

G_{1}

$G_1$

G_{1} + G_{2}

$G_1+G_2$

David Richerby

Mengenai pertanyaan terakhir Anda, jika diberi oracle ke GA seseorang dapat, dalam waktu polinomial, menemukan seperangkat pembangkit dari kelompok automorfisme, maka GI Turing dapat direduksi menjadi GA, yang saya tidak yakin diketahui.

Ariel

@ DavidRicherby Bagaimana dengan makalah berikut? sciencedirect.com/science/article/pii/…

Yuval Filmus

@YuvalFilmus OK, jadi Anda menggunakan pengurangan Turing dan saya menggunakan banyak-satu pengurangan. Dan saya kira pengurangan Turing lebih relevan untuk seseorang yang benar-benar mencoba untuk menyelesaikan masalah.

David Richerby

Jawaban:

Karena Anda juga tertarik dengan teori di baliknya, saya akan memberikan Anda algoritma waktu semu-polinomial untuk masalah Anda.

Untuk setiap pasangan simpul $u\neq v$ (dengan derajat yang sama) dalam $G$ , kami mencoba melihat apakah mungkin untuk menukar $u$ dan $v$ .

Untuk melakukan ini, buat salinan $G$ , sebut saja $G'$ . Sekarang, hapus $u$ dari $G$ , hapus (salinan) $v$ dari $G'$ .

Kemudian, untuk setiap $w\in N(u)$ tempelkan padanya jalan yang sangat panjang, tetapi hanya panjang secara polinomi .

Kemudian, untuk setiap (salinan) $w\in N(copy\ of\ v)$ lampirkan padanya jalan yang sangat panjang, tetapi hanya panjang secara polinomi .

Semua yang disebutkan di atas jalan yang sangat panjang, tetapi panjang secara polinomi , harus dari panjang yang sama.

Sebut algoritma Babai pada input dari pasangan grafik yang baru diproduksi ini.

Jika untuk setiap pasangan $(u, v)$ , kami memiliki jawaban $YES$ dari Babai, jawab $YES$ dan hentikan.

Jika tidak ada yang mengembalikan jawaban $YES$ , jawab $NO$ dan hentikan.

Jelas, melampirkan ke semua simpul di $N(u)$ dan $N(v)$ memaksa grafik isomorfisme mekanisme kerja dalam Babai dari algoritme untuk hanya memetakan simpul di $N(u)$ ke $N(v)$ . Dengan demikian, jika jawabannya Babai adalah $YES$ maka kita dapat dengan aman pasang di belakang $u$ dan $v$ memiliki automorphism non-sepele $G$ , karena $G'$ adalah salinan dari $G$ .

Kompleksitas run-time masih kuasi-poli.

Thinh D. Nguyen
sumber