Enumerating Homomorphisms

Abstract : The homomorphism problem for relational structures is an a bstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in li terature; in particular, the way the graph-theoretical structure of the variables and constrai nts influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.231-242, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359270
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 14:24:07
Dernière modification le : vendredi 8 décembre 2017 - 18:04:01
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:00:12

Fichiers

6-enumeration_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359270, version 1
  • ARXIV : 0902.1256

Collections

Citation

Andrei A. Bulatov, Victor Dalmau, Martin Grohe, Daniel Marx. Enumerating Homomorphisms. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.231-242, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359270〉

Partager

Métriques

Consultations de la notice

41

Téléchargements de fichiers

143