The homomorphism problem for regular graph patterns

Miguel Romero, Pablo Barceló, Moshe Y. Vardi

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations


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.

Original languageEnglish
Title of host publication2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509030187
StatePublished - 8 Aug 2017
Externally publishedYes
Event32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 - Reykjavik, Iceland
Duration: 20 Jun 201723 Jun 2017

Publication series

NameProceedings - Symposium on Logic in Computer Science
ISSN (Print)1043-6871


Conference32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017


Dive into the research topics of 'The homomorphism problem for regular graph patterns'. Together they form a unique fingerprint.

Cite this