Jan Foniok ; Claude Tardif - Adjoint functors and tree duality

dmtcs:458 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, Vol. 11 no. 2 - https://doi.org/10.46298/dmtcs.458
Adjoint functors and tree dualityArticle

Authors: Jan Foniok ORCID1; Claude Tardif 2

  • 1 Institute for Operations Research [Zurich]
  • 2 Royal Military College of Canada

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.


Volume: Vol. 11 no. 2
Section: Graph and Algorithms
Published on: January 1, 2009
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada

2 Documents citing this article

Consultation statistics

This page has been seen 270 times.
This article's PDF has been downloaded 241 times.