Complejidad del recuento de endomorfismos gráficos

Un homomorfismo de un gráfico a un gráfico G ′ = ( V ′ , E ′ ) es un mapeo f de V a V ′ tal que si x e y son adyacentes en E entonces f ( x ) y f ( y ) son adyacentes en E ' . Un endomorfismo de un gráfico $G = (V, E)$$G' = (V', E')$$f$$V$$V'$$x$$y$$E$$f(x)$$f(y)$$E'$$G$es un homomorfismo de a sí mismo; está libre de puntos fijos si no hay x tal que f ( x ) = x y no es trivial si no es la identidad.$G$$x$$f(x) = x$

Recientemente he hecho una pregunta relacionada con los automorfismos poset (y gráficos) , es decir, endomorfismos biyectivos cuyo inverso también es un endomorfismo. Encontré trabajo relacionado sobre contar (y decidir la existencia de) automorfismos, pero buscando no pude encontrar ningún resultado relacionado con endomorfismos.

De ahí mi pregunta: ¿Cuál es la complejidad, dada una gráfica , de decidir la existencia de un endomorfismo no trivial de G , o de contar el número de endomorfismos? La misma pregunta con endomorfismos sin punto fijo.$G$$G$

Creo que el argumento dado en esta respuesta se extiende a los endomorfismos y justifica que el caso de los gráficos bipartitos dirigidos, o posets, no es más fácil que el problema de los gráficos generales (el problema de los gráficos generales se reduce a este caso), pero su complejidad no parece sencillo de determinar. Se sabe que decidir la existencia de un homomorfismo de un gráfico a otro es NP-difícil (esto es claro ya que generaliza la coloración del gráfico), pero parece que restringir la búsqueda de homomorfismos de un gráfico a sí mismo podría facilitar el problema, así que esto no me ayuda a determinar la complejidad de estos problemas.

El conteo de endomorfismos o endomorfismos sin punto fijo está completo para : dado un gráfico conectado G , considere el gráfico G ', que es la unión disjunta de G y un triángulo. Entonces | Fin ( G ′ ) | = ( | Fin ( G ) | + # 3 C O L ( G ) ) ( # { triángulos en  G } + 3 3$\mathsf{FP}^{\mathsf{\# P}}$$G$$G'$$G$$|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, por lo tanto, se puede calcular utilizando dos recuentos de endomorfismo (y, por un resultado general, incluso uno solo es suficiente) y algo de post-procesamiento de tiempo múltiple. Tenga en cuenta que la cantidad de triángulos se puede contar en tiempo cúbico (o incluso multiplicación de matrices). La misma ecuación se aplica a los endomorfismos libres de punto fijo, ya que los 3 colores y los triángulos son endomorfismos libres de punto fijo de G ' .$\# 3COL$$G'$

Si desea que esté conectado, puede hacer lo siguiente. Primero, tenga en cuenta que contar los endomorfismos de gráficos de color de vértice (donde los vértices de color c solo se pueden asignar a otros vértices de color c ) es equivalente a contar los endomorfismos de gráficos, de la siguiente manera. Deje que los colores sean { 1 , . . . , C } . Para cada vértice v del color c , agregue un nuevo ciclo impar disuelto C v de tamaño al menos n + 2 c ( n = | V $G'$$c$$c$$\{1,...,C\}$$v$$c$$C_v$$n + 2c$) y conecta un vértice de C v a v . Cada endomorfismo de G corresponde a 2 n endomorfismos del nuevo gráfico (para cada ciclo, tiene dos opciones de cómo mapearlo). Tenga en cuenta que ningún vértice de G puede correlacionarse con vértices de cualquier C v , ya que los ciclos son demasiado grandes (tendría que poder ajustar un ciclo dentro de otro, lo que no puede hacer para ciclos impares).$n=|V(G)|$$C_v$$v$$G$$2^n$$G$$C_v$

Ahora, para hacer una versión de que esté conectada, comenzamos con una versión coloreada y luego aplicamos la transformación anterior. Comience como antes, agregando a G un triángulo disjunto Δ . Ahora agregue un solo vértice nuevo v 0 que esté conectado a cada vértice en G ∪ Δ . Color v 0 rojo y todos los demás vértices azules.$G'$$G$$\Delta$$v_0$$G \cup \Delta$$v_0$