Adjoint functors and tree duality

Abstract : A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph delta H also has tree duality, and we derive a family of tree obstructions for delta H from the obstructions for H. Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (2), pp.97--109
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00988207
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 7 mai 2014 - 15:58:17
Dernière modification le : mercredi 29 novembre 2017 - 10:26:17
Document(s) archivé(s) le : jeudi 7 août 2014 - 11:36:19

Fichier

987-4374-2-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00988207, version 1

Collections

Citation

Jan Foniok, Claude Tardif. Adjoint functors and tree duality. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (2), pp.97--109. 〈hal-00988207〉

Partager

Métriques

Consultations de la notice

336

Téléchargements de fichiers

87