Złożoność liczenia endomorfizmów grafowych

Homomorfizm z wykresu$G = (V, E)$na wykresie jest odwzorowaniem od do taki sposób, że jeśli i są obok siebie w czym i sąsiadują z . Endomorfizm grafu jest homomorfizmem od do siebie; nie ma ustalonego punktu, jeśli nie ma takiego, że i nie jest trywialne, jeśli nie jest to tożsamość.$G' = (V', E')$$f$$V$$V'$$x$$y$$E$$f(x)$$f(y)$$E'$$G$$G$$x$$f(x) = x$

Niedawno zadawane pytania związane z poset (wykres) i automorfizmy , czyli bijective endomorfizm których Converse są również endomorfizm. Znalazłem pokrewną pracę na temat liczenia (i decydowania o istnieniu) automorfizmów, ale szukając, nie mogłem znaleźć żadnych wyników związanych z endomorfizmami.

Stąd moje pytanie: jaka jest złożoność, biorąc pod uwagę wykres $G$ , decydowania o istnieniu nietrywialnego endomorfizmu $G$ lub liczenia liczby endomorfizmów? To samo pytanie z endomorfizmami stałopunktowymi.

Myślę, że argument podany w tej odpowiedzi rozciąga się na endomorfizmy i uzasadnia, że ​​przypadek ukierunkowanych dwustronnych grafów lub zestawów nie jest łatwiejszy niż problem dla grafów ogólnych (problem dla grafów ogólnych ogranicza się do tego przypadku), ale jego złożoność nie wydaje się łatwe do ustalenia. Wiadomo, że decyzja o istnieniu homomorfizmu z jednego wykresu na drugi jest trudna do NP (jest to jasne, ponieważ uogólnia kolorowanie wykresu), ale wydaje się, że ograniczenie wyszukiwania do homomorfizmów z wykresu do samego siebie może ułatwić problem, więc to nie pomaga mi określić złożoności tych problemów.

Liczenie endomorfizmów lub endomorfizmów bez ustalonych punktów jest zakończone dla$\mathsf{FP}^{\mathsf{\# P}}$ : biorąc pod uwagę podłączony wykres$G$rozważ wykres $G'$ który jest rozłącznym związkiem $G$i trójkąt. Następnie$|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, więc $\# 3COL$można obliczyć przy użyciu dwóch zliczeń endomorfizmu (i ogólnego wyniku wystarczy nawet tylko jeden) i pewnej ilości post-przetwarzania końcowego. Zauważ, że liczbę trójkątów można policzyć w czasie sześciennym (lub nawet mnożeniu macierzy). To samo równanie odnosi się do endomorfizmów swobodnych w punktach stałych, ponieważ trójkolorowe i trójkąty są endomorfizmami stałopunktowymi w punktach stałych$G'$.

Jeśli chciałbyś $G'$aby się połączyć, możesz wykonać następujące czynności. Najpierw zauważ, że licząc endomorfizmy wykresów w kolorze wierzchołków (gdzie wierzchołki kolorów$c$ można odwzorować tylko na inne wierzchołki koloru $c$) jest równoważne liczeniu endomorfizmów grafowych, jak następuje. Niech kolory będą$\{1,...,C\}$. Dla każdego wierzchołka$v$ koloru $c$, dodaj nowy rozłączny cykl nieparzysty$C_v$ co najmniej wielkości $n + 2c$ ($n=|V(G)|$) i połącz jeden wierzchołek $C_v$ do $v$. Każdy endomorfizm$G$ koresponduje z $2^n$endomorfizmy nowego wykresu (dla każdego cyklu masz dwie możliwości, jak go zmapować). Zauważ, że nie ma wierzchołków$G$ może mapować do wierzchołków dowolnego $C_v$, ponieważ cykle są zbyt duże (musiałbyś być w stanie zmieścić jeden cykl w innym, czego nie można zrobić w przypadku cykli nieparzystych).

Teraz, aby stworzyć wersję $G'$który jest podłączony, zaczynamy od wersji kolorowej, a następnie stosujemy powyższą transformację. Zacznij jak poprzednio, dodając do$G$ rozłączny trójkąt $\Delta$. Teraz dodaj jeden nowy wierzchołek$v_0$ który jest podłączony do każdego wierzchołka w $G \cup \Delta$. Kolor$v_0$ czerwony i wszystkie pozostałe wierzchołki niebieskie.