Karp hardness of testing for homomorphisms to a fixed non-bipartite graph

Question

Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$ such that:

For every $u,v\in V(G)$, $(\varphi(u)=\varphi(v))\lor(uv\in E(G)\implies\varphi(u)\varphi(v)\in E(H))$.

Note that we do not allow loops and multiple edges. This is just because $H$ is a fixed simple undirected graph. So, mapping to the same vertices is good but remember to map to every vertex of $H$. This also does not put constraint on those vertices mapped to the same $H$-vertex. By standard definition, without a loop at that $H$-vertex, the set of $G$-vertices mapped to it needs to be an independent set.

We want to decide whether a given graph $G$ is loopless surjectively homomorphic to $H$. Note that for each fixed non-bipartite $H$, we have a decision problem, denoted by $\mathrm{HOMOMORPHIC}_H$.

Formally, for every fixed (i.e. not part of the input) non-bipartite graph $H$, $\mathrm{HOMOMORPHIC_H}$ is defined as below:

Input: An undirected graph $G$

Output: YES if $G$ is loopless surjectively homomorphic to $H$, otherwise NO

We want to know the computational complexity of this problem.

Answer 1

Your question is more easily phrased as follows. You have a fixed non-bipartite, reflexive graph $H$ (reflexive = a loop on every vertex) and you want to know the complexity of deciding whether there is a surjective homomorphism (in the usual sense) from an input graph $G$ to $H$.

As far as I can see, this question is open.

• The problem is trivially in P when $H$ is a clique, since every $G$ with $|V(G)|\geq|V(H)|$ has a surjective homomorphism.
• Golovach et al. [1] have shown, for each four-vertex $H$, that the problem is either in P or is NP-complete (including bipartite cases, and allowing loops on any strict subset of the vertices).

I don't know of anything else with loops on all vertices.

---

[1] P. A. Golovach, M. Johnson, B. Martin, D. Paulusma, A. Stewart, Surjective $H$-colouring: new hardness results. ArXiv, 2017.

Answer 2

As others have pointed out in the comments, your definition of homomorphism is highly unusual. In particular, any function whose image is a single vertex is a homomorphism by your definition, thus trivializing the decision problem. The usual definition is as follows:

A homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $uv\in E(G)$ we have $\varphi(u)\varphi(v)\in E(H)$.

For the usual definition, the problem is known to be NP-complete for every non-bipartite $H$. The reference (according to Wikipedia) is Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110. (For bipartite $H$, on the other hand, there is a homomorphism if and only if $G$ is bipartite. Thus the decision problem is just bipartiteness of $G$, which is in PTIME.)

A few other notion are somewhat halfway between your definition and the usual one:

• A strong homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $u,v\in V(G)$ we have $uv\in E(G)$ if and only if $\varphi(u)\varphi(v)\in E(H)$.
• An embedding from $G$ in $H$ is an injective homomorphism, that is a homomorphism $\varphi$ such that for all $u,v\in V(G)$ with $u\not=v$ we have $\varphi(u)\not=\varphi(v)$.
• An induced subgraph mapping is an injective strong homomorphism.

[EDIT]

For each of these variants, the problem is in PTIME for fixed $H$. When injectivity is required, one can reject an instance if $|V(G)|>|V(H)|$, so only a finite set of graphs remains. For strong homomorphisms, we can have $\varphi(v)=\varphi(w)$ only if $v$ and $w$ have the same neighbours. Hence after some polynomial time preprocessing, we can again assume injectivity.