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.

  • 1
    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)$)? – user53923 Oct 1 at 12:46
  • 5
    If the current version still has some unwanted feature, please comment to let me know. – Thinh D. Nguyen Oct 2 at 2:14
  • 5
    $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. – Thinh D. Nguyen Oct 2 at 7:46
  • 5
    That is kind of what I was afraid of. – Thinh D. Nguyen Oct 2 at 8:31
  • 1
    @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. – David Richerby Oct 2 at 14:13
up vote 2 down vote accepted

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.

  • 5
    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. – Thinh D. Nguyen Oct 2 at 2:11
  • 5
    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. – Thinh D. Nguyen Oct 2 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. – Thinh D. Nguyen Oct 2 at 8:29
  • Yes, my memory of the strong homomorphism case was faulty. Now corrected. – kne Oct 2 at 11:47

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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