The evaluation of conjunctive regular path queries - which form the
navigational core of the query languages for graph databases - raises
challenges in the context of the homomorphism problem that are not fully
addressed by existing techniques. We start a systematic investigation of such
challenges using a notion of homomorphism for regular graph patterns (RGPs). We
observe that the RGP homomorphism problem cannot be reduced to known instances
of the homomorphism problem, and new techniques need to be developed for its
study. We first show that the non-uniform version of the problem is
computationally harder than for the usual homomorphism problem. By establishing
a connection between both problems, in turn, we postulate a dichotomy
conjecture, analogous to the algebraic dichotomy conjecture held in CSP. We
also look at which structural restrictions on left-hand side instances of the
RGP homomorphism problem ensure efficiency. We study restrictions based on the
notion of bounded treewidth modulo equivalence, which characterizes
tractability for the usual homomorphism notion. We propose two such notions,
based on different interpretations of RGP equivalence, and show that they both
ensure the efficiency of the RGP homomorphism problem.