Is there a name for a graph homomorphism that is almost subgraph isomorphic but allows multiple nodes to map to the same node?

200 Views Asked by At

I'm looking for a kind of graph homomorphism $f : G = (V_G, E_G) \rightarrow H = (V_H, E_H)$ that is almost the same as subgraph isomorphism, but not quite. I require $f$ to map every node in $V_G$ to some node in $V_H$ such that if $(u, v) \in E_G$ then $(f(u), f(v)) \in E_H$. However, unlike subgraph isomorphism, it is allowed that multiple nodes in $V_G$ map to the same node in $V_H$.

I will also show by an example. Say we have the following graphs:

         a     b          1     2
          \   /            \   /
           \ /              \ /
            c                3
            |                |\
            d                4 5

            G                H

In this case there exist an $f$ because $G$ is subgraph isomorphic to $H$. But say that we now merge the $1$ and $2$ nodes in $H$ to a single node $12$:

         a     b             12
          \   /             / \
           \ /              \ /
            c                3
            |                |\
            d                4 5

            G                H'

Now, even though $G$ is no longer subgraph isomorphic to $H'$, there exists still an $f$ because I allow both the $a$ and $b$ nodes to map to the $12$ node.

$f$ is clearly not a bijective homomorphism because not every node in $H$ needs to be mapped, and it is also not an injective homomorphism because more than one node in $G$ can be mapped to the same node in $H$. But it is also not a surjective homomorphism because I don't want to enforce the constraint that there exists at least one mapping for every node in $H$.

So my question is: is there a name for my graph homomorphism, or some way of describing it using common terminology? And does there exist an algorithm for finding such mappings? $^*$

$^*$ I'm not expecting a polynomial-time algorithm to exist since this is most likely a NP-complete problem, but I'm wondering whether there's some existing algorithm that I can easily implement (like VF2 for finding subgraph isomorphic mappings).