Apakah "Apakah permutasi merupakan automorfisme dari sebuah grafik di set saya?" NP-lengkap?

Misalkan kita memiliki seperangkat S grafik (grafik berhingga, tetapi sejumlah tak terbatas dari mereka) dan sekelompok P permutasi yang bekerja pada S.

Instance: P permutasi di P.

Pertanyaan: Apakah ada grafik g di S yang menerima p automorfisme?

Apakah ini masalah NP-complete untuk beberapa set S?

Akan mudah untuk memeriksa bahwa grafik mengakui permutasi p (sertifikat yaitu). Selain itu, mudah untuk menemukan contoh S di mana masalahnya tidak lengkap NP, seperti S menjadi himpunan grafik lengkap, dari mana jawabannya selalu ya.

Catatan: Saya tidak begitu tertarik dengan jenis grafiknya; jika Anda suka mereka bisa tidak sederhana, terarah, berwarna, dll.

TAMBAHAN: Masalah yang saya lihat saat ini adalah mengklasifikasikan isotopisme mana yang merupakan autotopisme dari kotak Latin (yang juga dapat diartikan sebagai jenis khusus dari automorfisme grafik).

Diberi persegi Latin L (i, j) kita dapat membuat grafik dengan cara berikut:

Himpunan verteks adalah himpunan sel (i, j) dalam matriks dan
Ada perbedaan antara yang berbeda (i, j) dan (i ', j') setiap kali saya = i 'atau j = j' atau L (i, j) = L (i ', j').

Grafik semacam itu disebut grafik kotak Latin (lihat misalnya artikel ini oleh Bailey dan Cameron http://designtheory.org/library/encyc/topics/lsee.pdf ). Kita dapat menginterpretasikan autotopisme persegi Latin sebagai automorfisme grafik persegi Latin. Jadi misalkan S adalah himpunan grafik persegi Latin yang dibentuk dari kuadrat Latin orde n. Jadi pertanyaan saya tertarik adalah:

Diberi p permutasi, apakah p automorfisme dari satu (atau lebih) dari grafik dalam S?

Perasaan saya adalah bahwa ini adalah pertanyaan yang sulit dijawab secara umum - Saya saat ini menulis makalah 30+ halaman tentang masalah ini (dengan 2 penulis bersama). Sebenarnya sebagian besar waktu itu mudah (sebagian besar waktu itu "tidak"), tetapi ada beberapa kasus yang sulit.

Jadi saya tertarik untuk menemukan masalah keputusan yang akan terkait dengan "klasifikasi simetri". Mereka tidak benar-benar perlu dikaitkan dengan kotak Latin, saya hanya berharap untuk menggunakan teknik ini untuk menjawab pertanyaan untuk kotak Latin.

cc.complexity-theory graph-theory np-hardness automorphism Douglas S. Stones
sumber

Saya tidak yakin apakah saya memahami masalahnya dengan benar. Bisakah Anda memberikan contoh S dan P (dan aksi grup P pada S)? Contoh yang membuat masalah nontrivial (tidak semua-ya atau semua-tidak) akan membantu untuk memahami masalah.

Tsuyoshi Ito

Dalam contoh grafik lengkap, apa yang saya tidak mengerti adalah bagaimana permutasi pada titik k bertindak pada grafik lengkap pada titik n, di mana k ≠ n (terutama jika k> n).

Tsuyoshi Ito

Saya berhasil membohongi diri sendiri dengan berpikir bahwa saya memahami masalahnya, tetapi sekarang saya memutuskan untuk tidak melakukannya. Apakah kelompok permutasi S bertindak pada grafik dalam keluarga P, atau hanya berpotensi bertindak pada grafik dalam keluarga P?

Niel de Beaudrap

Satu masalah di sini adalah bahwa kita perlu memilih satu set

yang pengujian keanggotaannya dalam NP.

S

$S$

Emil

Saya telah menambahkan sedikit lebih banyak latar belakang dalam jawabannya. Sebenarnya, secara umum, saya tidak benar-benar peduli tentang apakah grup bertindak pada S, asalkan kita bisa menjawab "apakah permutasi ini merupakan automorfisme dari grafik itu?" Dalam kasus kotak Latin, kita dapat menafsirkannya sebagai aksi kelompok.

Douglas S. Stones

Ambil bahasa apa pun (yang terdiri dari string biner). Buat himpunan dari grafik sebagai berikut: $L$ $S$

Untuk setiap string dengan , kita memiliki grafik di , dengan set node dan tepi berikut: jika bit dari adalah , maka node dan $x \in L$ $|x| = n$ $G_x = (V_x,E_x)$ $S$ $V_x = \{1,2,...,3n\}$ $i$ $x$ $0$ $3i-2$ berdekatan, jika tidak dan berdekatan. Tidak ada tepi lainnya. $3i-1$ $3i-2$ $3i$

Sekarang mari menjadi permutasi dari . Asumsikan bahwa adalah automorphism beberapa grafik dalam . Artinya, adalah automorphism dari untuk beberapa . Biarkan . Mari kita perhatikan dua kasus berikut: $p$ $\{1,2,...,3n\}$ $p$ $S$ $p$ $G_y$ $y \in L$ $i \in \{1,2,...,n\}$

, , . Maka kita harus memiliki bit of sama dengan . $p(3i-2) = 3i-1$ $p(3i-1) = 3i-2$ $p(3i) = 3i$ $i$ $y$ $0$
, , . Maka kita harus memiliki bit of sama dengan . $p(3i-2) = 3i$ $p(3i-1) = 3i-1$ $p(3i) = 3i-2$ $i$ $y$ $1$

Oleh karena itu jika kita dapat menyelesaikan pertanyaan "adalah automorfisme diberikan dari beberapa ", kita juga dapat memecahkan pertanyaan "adalah string yang diberikan dalam ". Selain itu, jika kita dapat melakukan yang sebelumnya dalam, katakanlah, waktu polinomial dalam , kita dapat melakukan yang terakhir dalam waktu polinomial dalam demikian juga. $p$ $G \in S$ $y$ $L$ $|p|$ $|y|$

Sekarang Anda bisa membiarkan menjadi masalah NP-hard favorit Anda. Atau masalah penghentian ... $L$

Jukka Suomela
sumber

Dan untuk benar-benar menjawab pertanyaan awal: Biarkan

menjadi masalah NP-lengkap, dan Anda akan memiliki

sehingga masalah automorfisme adalah NP-lengkap. Sertifikat untuk jawaban "ya" adalah

sehingga

adalah automorphism dari

, ditambah sertifikat untuk

L

$L$

S

$S$

G_{y} \in S

$G_y \in S$

p

$p$

G_{y}

$G_y$

y \in L

$y \in L$

Jukka Suomela

@Jukka: Salah satu cara untuk membuat pertanyaan lebih dekat dengan motivasi asli dari grafik kotak Latin adalah dengan mensyaratkan bahwa himpunan

dari grafik ditutup di bawah isomorfisme. Ini juga pembatasan yang wajar. Himpunan

Anda bangun dari bahasa yang arbitrer

tidak tertutup di bawah isomorfisme dan, dalam pengertian yang sangat spesifik ini, agak tidak wajar. Saya tidak melihat cara memodifikasi konstruksi Anda untuk memenuhi batasan ini, tapi saya pikir akan sangat menarik jika itu bisa dilakukan.

S

$S$

S

$S$

L

$L$

Joshua Grochow

G_{x}

$G_x$

2 i + a + 1

$2i+a+1$

i

$i$

x

$x$

a

$a$

y \in L

$y \in L$

p

$p$

2 i + a + 1

$2i+a+1$

i

$i$

y

$y$

a

$a$

p \in S_{n}

$p \in S_n$

n

$n$

n

$n$

p \in S_{n}

$p \in S_n$

n

$n$

L

$L$

Apakah "Apakah permutasi merupakan automorfisme dari sebuah grafik di set saya?" NP-lengkap?

Jawaban: