Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

Duality and Polynomial Testing of
Tree Homomorphisms


Authors: P. Hell, J. Nesetril and X. Zhu
Journal: Trans. Amer. Math. Soc. 348 (1996), 1281-1297
MSC (1991): Primary 05C85; Secondary 68Q25
MathSciNet review: 1333391
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $H$ be a fixed digraph. We consider the $H$-colouring problem, i.e., the problem of deciding which digraphs $G$ admit a homomorphism to $H$. We are interested in a characterization in terms of the absence in $G$ of certain tree-like obstructions. Specifically, we say that $H$ has tree duality if, for all digraphs $G$, $G$ is not homomorphic to $H$ if and only if there is an oriented tree which is homomorphic to $G$ but not to $H$. We prove that if $H$ has tree duality then the $H$-colouring problem is polynomial. We also generalize tree duality to bounded treewidth duality and prove a similar result. We relate these duality concepts to the notion of the $\underline X$-property studied by Gutjahr, Welzl, and Woeginger.

We then focus on the case when $H$ itself is an oriented tree. In fact, we are particularly interested in those trees that have exactly one vertex of degree three and all other vertices of degree one or two. Such trees are called triads. We have shown in a companion paper that there exist oriented triads $H$ for which the $H$-colouring problem is $NP$-complete. We contrast these with several families of oriented triads $H$ which have tree duality, or bounded treewidth duality, and hence polynomial $H$-colouring problems. If $P \neq NP$, then no oriented triad $H$ with an $NP$-complete $H$-colouring problem can have bounded treewidth duality; however no proof of this is known, for any oriented triad $H$. We prove that none of the oriented triads $H$ with $NP$-complete $H$-colouring problems given in the companion paper has tree duality.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 05C85, 68Q25

Retrieve articles in all journals with MSC (1991): 05C85, 68Q25


Additional Information

P. Hell
Affiliation: School of Computing Science, Simon Fraser University, Burnaby, BC, Canada V5A 1S6
Email: pavol@cs.sfu.ca

J. Nesetril
Affiliation: Department of Applied Mathematics, Charles University, Prague, The Czech Republic
Email: nesetril@kam.ms.mff.cuni.cz

X. Zhu
Affiliation: Sonderforschungsbereich 343, Universität Bielefeld, 33501 Bielefeld, Germany
Email: xu@mathematik.uni-bielefeld.de

DOI: http://dx.doi.org/10.1090/S0002-9947-96-01537-1
PII: S 0002-9947(96)01537-1
Received by editor(s): July 20, 1993
Article copyright: © Copyright 1996 American Mathematical Society