Complexity of counting graph endomorphisms

Question

A homomorphism from a graph $G = (V, E)$ to a graph $G' = (V', E')$ is a mapping $f$ from $V$ to $V'$ such that if $x$ and $y$ are adjacent in $E$ then $f(x)$ and $f(y)$ are adjacent in $E'$. An endomorphism of a graph $G$ is a homomorphism from $G$ to itself; it is fixed-point-free if there is no $x$ such that $f(x) = x$ and it is non-trivial if it is not the identity.

I have recently asked a question related to poset (and graph) automorphisms, that is, bijective endomorphisms whose converse are also an endomorphism. I found related work about counting (and deciding the existence of) automorphisms, but searching I couldn't find any results related to endomorphisms.

Hence my question: What is the complexity, given a graph $G$, of deciding the existence of a non-trivial endomorphism of $G$, or of counting the number of endomorphisms? Same question with fixed-point-free endomorphisms.

I think the argument given in this answer extends to endomorphisms and justifies that the case of directed bipartite graphs, or posets, is no easier than the problem for general graphs (the problem for general graphs reduces to this case), but its complexity do not seem straightforward to determine. It is known that deciding the existence of an homomorphism from one graph to another is NP-hard (this is clear as it generalizes graph coloring), but it seems like restricting the search to homomorphisms from a graph to itself might make the problem easier, so this doesn't help me determine the complexity of these problems.

Answer 1

Counting endomorphisms or fixed-point-free endomorphisms is complete for $\mathsf{FP}^{\mathsf{\# P}}$: given a connected graph $G$, consider the graph $G'$ which is the disjoint union of $G$ and a triangle. Then $|\text{End}(G')| = (|\text{End}(G)| + \# 3COL(G))(\#\{\text{triangles in } G\} + 3^3)$, so $\# 3COL$ can be computed using two endomorphism counts (and by a general result, even just one suffices) and some poly-time post-processing. Note that the number of triangles can be counted in cubic (or even matrix multiplication) time. The same equation holds for fixed-point free endomorphisms, since the 3-colorings and triangles are fixed-point-free endomorphisms of $G'$.

If you would like $G'$ to be connected, you can do as follows. First note that counting vertex-colored graph endomorphisms (where vertices of color $c$ can only be mapped to other vertices of color $c$) is equivalent to counting graph endomorphisms, as follows. Let the colors be $\{1,...,C\}$. For each vertex $v$ of color $c$, add in a new disjoint odd cycle $C_v$ of size at least $n + 2c$ ($n=|V(G)|$), and connect one vertex of $C_v$ to $v$. Every endomorphism of $G$ corresponds to $2^n$ endomorphisms of the new graph (for each cycle, you have two choices of how to map it). Note that no vertices of $G$ can map to vertices of any $C_v$, since the cycles are too large (you'd have to be able to fit one cycle inside another, which you can't for odd cycles).

Now, to make a version of $G'$ that is connected, we start with a colored version, and then apply the above transformation. Start as before, by adding to $G$ a disjoint triangle $\Delta$. Now add a single new vertex $v_0$ that is connected to every vertex in $G \cup \Delta$. Color $v_0$ red and all other vertices blue.