The homomorphism problem for regular graph patterns

Miguel Romero, Pablo Barceló, Moshe Y. Vardi

Producción científica: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

7 Citas (Scopus)


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.

Idioma originalInglés
Título de la publicación alojada2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017
EditorialInstitute of Electrical and Electronics Engineers Inc.
ISBN (versión digital)9781509030187
EstadoPublicada - 8 ago. 2017
Publicado de forma externa
Evento32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017 - Reykjavik, Islandia
Duración: 20 jun. 201723 jun. 2017

Serie de la publicación

NombreProceedings - Symposium on Logic in Computer Science
ISSN (versión impresa)1043-6871


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


Profundice en los temas de investigación de 'The homomorphism problem for regular graph patterns'. En conjunto forman una huella única.

Citar esto