Kompleksitas penghitungan endomorfisme grafik

Sebuah homomorfisma dari grafik untuk grafik G ' = ( V ' , E ' ) adalah pemetaan f dari V ke V ' sehingga jika x dan y yang berdekatan di E maka f ( x ) dan f ( y ) berbatasan dengan E ′ . Sebuah endomorfisma dari grafik $G = (V, E)$$G' = (V', E')$$f$$V$$V'$$x$$y$$E$$f(x)$$f(y)$$E'$$G$adalah homomorfisme dari ke dirinya sendiri; itu adalah fixed-point-free jika tidak ada x sedemikian rupa sehingga f ( x ) = x dan tidak-sepele jika bukan identitas.$G$$x$$f(x) = x$

Baru-baru ini saya mengajukan pertanyaan terkait automorfisme poset (dan grafik) , yaitu endomorfisme bijective yang kebalikannya juga merupakan endomorfisme. Saya menemukan pekerjaan terkait tentang menghitung (dan memutuskan keberadaan) automorfisma, tetapi mencari saya tidak dapat menemukan hasil yang terkait dengan endomorfisme.

Maka pertanyaan saya: Apa kompleksitasnya, diberikan grafik , untuk menentukan keberadaan endomorfisme G yang tidak sepele , atau menghitung jumlah endomorfisme? Pertanyaan yang sama dengan endomorfisme bebas-titik-tetap.$G$$G$

Saya pikir argumen yang diberikan dalam jawaban ini meluas ke endomorfisme dan membenarkan bahwa kasus grafik bipartit diarahkan, atau poset, tidak lebih mudah daripada masalah untuk grafik umum (masalah untuk grafik umum mengurangi kasus ini), tetapi kompleksitasnya tidak tampaknya mudah untuk ditentukan. Diketahui bahwa memutuskan keberadaan homomorfisme dari satu grafik ke grafik lainnya adalah NP-hard (ini jelas karena menggeneralisasikan pewarnaan grafik), tetapi sepertinya membatasi pencarian untuk homomorfisme dari grafik ke dirinya sendiri mungkin membuat masalah lebih mudah, jadi ini tidak membantu saya menentukan kompleksitas masalah ini.

Menghitung endomorfisme atau endomorfisme bebas-titik-tetap sudah lengkap untuk : diberi grafik G yang terhubung , perhatikan grafik G ′ yang merupakan gabungan pisah G dan segitiga. Lalu | End ( G ′ ) | = ( | Akhir ( G ) | + # 3 C O L ( G ) ) ( # { segitiga dalam  G } + 3 3$\mathsf{FP}^{\mathsf{\# P}}$$G$$G'$$G$$|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, jadi dapat dihitung menggunakan dua jumlah endomorfisme (dan dengan hasil umum, bahkan hanya satu yang mencukupi) dan beberapa proses pasca-waktu poli-waktu. Perhatikan bahwa jumlah segitiga dapat dihitung dalam waktu kubik (atau bahkan perkalian matriks). Persamaan yang sama berlaku untuk endomorphisms bebas fixed-point, sejak 3-pewarna dan segitiga yang endomorphisms fixed-point-bebas dari G ' .$\# 3COL$$G'$

Jika Anda ingin terhubung, Anda dapat melakukan hal berikut. Catatan pertama bahwa penghitungan endomorfisma grafik berwarna titik (di mana simpul-simpul warna c hanya dapat dipetakan ke simpul-simpul warna c lainnya ) sama dengan menghitung grafik endomorfisme, sebagai berikut. Biarkan warna menjadi { 1 , . . . , C } . Untuk setiap vertex v warna c , menambahkan dalam menguraikan baru aneh siklus C v ukuran minimal n + 2 c ( n = | V $G'$$c$$c$$\{1,...,C\}$$v$$c$$C_v$$n + 2c$), Dan menghubungkan satu titik dari C v ke v . Setiap endomorfisma G berhubungan dengan 2 n endomorfisme dari grafik baru (untuk setiap siklus, Anda memiliki dua pilihan cara memetakannya). Perhatikan bahwa tidak ada simpul dari G dapat memetakan ke simpul dari setiap C v , karena siklus terlalu besar (Anda harus bisa muat satu siklus dalam lainnya, yang Anda tidak bisa untuk siklus aneh).$n=|V(G)|$$C_v$$v$$G$$2^n$$G$$C_v$

$G'$$G$$\Delta$$v_0$$G \cup \Delta$$v_0$