Complexité du comptage des endomorphismes des graphes

Un homomorphisme d'un graphe à un graphe est un mappage de à tel que si et sont adjacents dans alors et sont adjacents dans . Un endomorphisme d'un graphe est un homomorphisme de à lui-même; il est sans virgule fixe s'il n'y a pas de tel que et il n'est pas trivial si ce n'est l'identité.$G = (V, E)$$G' = (V', E')$$f$$V$$V'$$x$$y$$E$$f(x)$$f(y)$$E'$$G$$G$$x$$f(x) = x$

J'ai récemment posé une question relative aux automorphismes de posets (et de graphes) , c'est-à-dire les endomorphismes bijectifs dont l'inverse est également un endomorphisme. J'ai trouvé des travaux sur le comptage (et la détermination de l'existence) des automorphismes, mais en cherchant, je n'ai trouvé aucun résultat lié aux endomorphismes.

D'où ma question: quelle est la complexité, compte tenu d'un graphe , de décider de l'existence d'un endomorphisme non trivial de , ou de compter le nombre d'endomorphismes? Même question avec les endomorphismes sans point fixe.$G$$G$

Je pense que l'argument donné dans cette réponse s'étend aux endomorphismes et justifie que le cas des graphes bipartis dirigés, ou posets, n'est pas plus facile que le problème des graphes généraux (le problème des graphes généraux se réduit à ce cas), mais sa complexité ne fait pas semblent simples à déterminer. On sait que décider de l'existence d'un homomorphisme d'un graphique à un autre est NP-difficile (cela est clair car il généralise la coloration des graphiques), mais il semble que restreindre la recherche aux homomorphismes d'un graphique à lui - même pourrait rendre le problème plus facile, donc cela ne m'aide pas à déterminer la complexité de ces problèmes.

Le comptage des endomorphismes ou des endomorphismes sans point fixe est terminé pour : étant donné un graphe connecté , considérons le graphe qui est l'union disjointe de et d'un triangle. Alors , donc peut être calculé en utilisant deux endomorphismes compte (et par un résultat général, même un seul suffit) et un certain post-traitement poly-temps. Notez que le nombre de triangles peut être compté en temps cubique (ou même multiplication matricielle). La même équation s'applique aux endomorphismes libres à point fixe, car les 3 coloriages et les triangles sont des endomorphismes libres à point fixe de$\mathsf{FP}^{\mathsf{\# P}}$$G$$G'$$G$$|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$$\# 3COL$$G'$.

Si vous souhaitez que soit connecté, vous pouvez procéder comme suit. Notez d'abord que le comptage des endomorphismes de graphes de couleur vertex (où les sommets de couleur ne peuvent être mappés qu'à d'autres sommets de couleur ) équivaut à compter les endomorphismes de graphes, comme suit. Soit les couleurs . Pour chaque sommet de couleur , ajoutez un nouveau cycle impair disjoint de taille au moins ( ), et connectez un sommet de à . Chaque endomorphisme de correspond à$G'$$c$$c$$\{1,...,C\}$$v$$c$$C_v$$n + 2c$$n=|V(G)|$$C_v$$v$$G$$2^n$les endomorphismes du nouveau graphique (pour chaque cycle, vous avez deux choix pour le mapper). Notez qu'aucun sommet de ne peut correspondre à des sommets de n'importe quel , car les cycles sont trop grands (vous devez pouvoir adapter un cycle à l'intérieur d'un autre, ce que vous ne pouvez pas faire pour des cycles impairs).$G$$C_v$

Maintenant, pour créer une version de qui est connectée, nous commençons avec une version colorée, puis appliquons la transformation ci-dessus. Commencez comme avant, en ajoutant à un triangle disjoint . Ajoutez maintenant un seul nouveau sommet qui est connecté à chaque sommet dans . Couleur rouge et tous les autres sommets bleus.$G'$$G$$\Delta$$v_0$$G \cup \Delta$$v_0$