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

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.

• If I read your current definition correctly, any graph $G$ is homomorphic to $H$. (Pick an arbitrary vertex $h \in V(H)$ and let $\varphi(v) = h$ for all $v\in V(G)$)? Oct 1, 2018 at 12:46
• If the current version still has some unwanted feature, please comment to let me know. Oct 2, 2018 at 2:14
• $H$ is fixed. $G$ is the input. So for large enough $G$, it is necessarily to have $\varphi(u)=\varphi(v)$ for some distinct $u,v\in V(G)$. And we don't want any loops in $H$. Admittedly, this is not algebraic. Oct 2, 2018 at 7:46
• That is kind of what I was afraid of. Oct 2, 2018 at 8:31
• @kne It's just "Add a loop to every vertex of $H$ -- is there a surjective homomorphism?" I don't think it has much in common with graph minors. Oct 2, 2018 at 14:13

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.

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.

• That would be a surprise if testing for being strongly homomorphic to a graph $H$ with only $3$ vertices is $NP$ complete. Note that that is testing if $G$ can be partitioned into $3$ independent sets each two of which form a biclique. Oct 2, 2018 at 2:11
• If you allow the fixed graph $H$ to have loops (which are not allowed in our problem here), then instead of $3$ independent sets, you may have something like $1$ independent set and $2$ cliques, each two of them form a biclique. Oct 2, 2018 at 2:13
• Anyway, I have to admit that breaking the algebraic nature of these kinds of problems seems to push us into an unknown universe. Oct 2, 2018 at 8:29
• Yes, my memory of the strong homomorphism case was faulty. Now corrected.
– kne
Oct 2, 2018 at 11:47