# Has this form of "kind-of-dual" homomorphisms been studied?

Let $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ be graphs and let $h:V_2\to V_1$ be a map such that, for every edge $(u_1,v_1)\in E_1$, there is an edge $(u_2,v_2)\in E_2$ such that $h(u_2)=u_1$ and $h(v_2)=v_1$.

This kind of maps has occurred in our recent research in Database Theory. We think that it looks like a natural "dual" to graph homomorphisms, where $h$ would be $V_1\to V_2$ and map each edge of $G_1$ to an edge of $G_2$. However, we could not find it in the literature, but, since we do not have a name for it, maybe we searched in the wrong places.

Some background: in Database Theory, homomorphisms play an important role in the context of the containment problem for conjunctive queries. The "kind-of-dual" form occurs in the context of parallel query evaluation.

In this slightly extended context, testing for existence of such a mapping is NP-complete, and I expect that also for graphs. However, I am not asking for complexity results, but I would be be grateful for pointers to the literature (or even a name, for that matter).

• This is usually expressed by saying that the map reflects the existence of edges (or other relations) rather than preserving them as a homomorphism would. In this case, you could also say that for every non-edge $(u_2,v_2)$, $(h(u_2),h(v_2))$ is also a non-edge, i.e. $h$ is a homomorphism of the complements. Dec 14, 2015 at 13:44
• Thank you. Oh yeah! Now I ask myself why I haven't seen the complement characterization. ;-) The downside is that for the complexity the detour through the complement will not help a lot, since this is usually of exponential size. In any case, this helped. Dec 14, 2015 at 19:18
• @KlausDraeger, I don't follow. $P_3$ maps to $P_2+v$ via a non-bijective map $h$ of the kind in the question, but $h$ is not a homomorphism from the complement $P_2+v$ to the complement $P_3$. Are you considering graphs with self-loops? Dec 15, 2015 at 10:37
• @AndrásSalamon good point, for the "homomorphism of complements" description you need to allow self-loops (or restrict yourself to injections). Dec 15, 2015 at 12:10

In the case of undirected graphs, there is literature about such morphisms called graph emulators. They are a refinement of the notion of covering graph. A covering graph maps the neighbourhood of a vertex $u$ bijectively to the neighbourhood of $h(u)$, while an emulator is only required to do it surjectively, which seems equivalent to your question.