0
$\begingroup$

The "graph homomorphism problem" can be stated as: given two graphs $G$ and $H$, determine if there exists a homomorphism $f$ such that $f: G \rightarrow H$. This is a famous problem that is well-known to be NP-complete.

Now I'm thinking about a related problem: given two homomorphic graphs $G$ and $H$, find $f: G \rightarrow H$. Does this problem have a name? Is its complexity class known?

$\endgroup$
2
  • $\begingroup$ Your problem is not a decision problem. In particular, it cannot be NP-complete or NP-hard. $\endgroup$ Oct 22 '21 at 5:55
  • $\begingroup$ Good point. Fixed my question $\endgroup$
    – lennox
    Oct 22 '21 at 5:58
1
$\begingroup$

There are a couple of cases that we can dispose of straight away.

A self-edge on some vertex $v$ is an edge $v \rightarrow v$. If $H$ has even one vertex with a self-edge, then it's trivial to construct a homomorphism which maps all vertices to that vertex and all edges to that edge.

Similarly, if $H$ doesn't have a single vertex with a self-edge but $G$ has, no homomorphism exists.

Finally, we can deal with the case where $G$ has no self-edges. Then $G$ must be a chromatic graph: for some $k$, the vertices of $G$ can be assigned $k$ colours such that the start and end of each edge do not share the same colour.

Denote the complete graph with $k$ vertices by $K_k$.

Exercise: Show that a homomorphism $f : G \rightarrow K_k$ describes a $k$-colouring of $G$. Conversely, show that every $k$-colouring of $G$ can be represented as a homomorphism $f : G \rightarrow K_k$.

So any solution to your problem is also a solution to the $k$-colouring problem.

The decision problem of testing a mapping to see if it is a graph homomorphism is trivially in P. It follows that your problem is FNP-complete.

$\endgroup$

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.