Dichotomy theorem for general Minimum Cost Homomorphisms Problem

Abstract : In the classical Constraint Satisfaction Problem(CSP) two finite models are given and we are asked to find their homomorphism. In the MinHom problem, besides the models, a set of weighted pairs of elements of this two models is given and the task is to find a homomorphism that maximizes the weight of pairs consistent with the homomorphism, i.e. pairs for which homomorphism maps the first element of the pair to the second element. MinHom can be considered as a generic model for a class of combinatorial optimization problems, one of which is a maximal independent set. It appears naturally in defence logistic and supervised learning. This problem shares a lot of common with the classical CSP. We show that it allows similar algebraic approach to the classification of tractable cases of this problem that connects it with relational and functional clones of multi-valued logic. Using this approach we obtain complete classification of polynomially tractable subcases of MinHom. As a result of this classification we confirm general dichotomy conjecture that was given for various special cases of MinHom in terms of digraph theory[12,11].
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.657-668, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00455989
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 15:00:30
Dernière modification le : jeudi 11 février 2010 - 21:54:42
Document(s) archivé(s) le : vendredi 18 juin 2010 - 18:25:03

Fichier

takhanov.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455989, version 1

Collections

Citation

Rustem Takhanov. Dichotomy theorem for general Minimum Cost Homomorphisms Problem. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.657-668, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455989〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

64