9
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I'm not sure of your exact formula for $|\mathrm{End}(G')|$ (I get $(|\mathrm{End}(G)| + \#3COL(G))(\#triangles + 3^3)$, and something similar for fixed-point-free) but the argument still holds. The second part of your argument shows hardness even assuming connectedness, I think it is true but I think it doesn't apply directly to fixed-point-free endomorphisms (there are fixed points in the cycle mappings), but that's not so important. I'd be more curious to know: is the decision problem NP-hard (for non-trivial, and for fixed-point-free endomorphisms)? Thanks again! $\endgroup$ – a3nm May 21 '14 at 9:45
  • $\begingroup$ You're right about the formula - I updated it. To make the second part apply to fixed-point-free, put an edge from each of two maximally distant vertices of $C_v$ to $v$. The count for fixed-point-free will be slightly different, but I think it still works. (You may also need to increase the size of the cycles...). For pairs of rigid graphs (no nontrivial endos) $G,H$, deciding existence of endos of $G \cup H$ (disjoint union) is equivalent to deciding existence of a homomorphism $G \to H$ or $H \to G$. Almost all graphs are rigid w.h.p., so it's quite possible that decision is NP-hard... $\endgroup$ – Joshua Grochow May 21 '14 at 10:02
  • $\begingroup$ OK I think I buy your argument for fixed-point-free count. For decision, in fact I now notice that "The core of a graph", Hell, p. 8-9, seems to prove that deciding the existence of a non-trivial endomorphism is NP-complete. (The question of fixed-point-free endomorphisms remains but there is little reason to believe it wouldn't be hard also.) $\endgroup$ – a3nm May 21 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.