Duality and Polynomial Testing of Tree Homomorphisms |
| |
| Authors: | P. Hell J. Nesetril X. Zhu |
| |
| Affiliation: | School of Computing Science, Simon Fraser University, Burnaby, BC, Canada V5A 1S6 ; Department of Applied Mathematics, Charles University, Prague, The Czech Republic ; Sonderforschungsbereich 343, Universität Bielefeld, 33501 Bielefeld, Germany |
| |
| Abstract: | Let  be a fixed digraph. We consider the  -colouring problem, i.e., the problem of deciding which digraphs  admit a homomorphism to  . We are interested in a characterization in terms of the absence in  of certain tree-like obstructions. Specifically, we say that  has tree duality if, for all digraphs  ,  is not homomorphic to  if and only if there is an oriented tree which is homomorphic to  but not to  . We prove that if  has tree duality then the  -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  -property studied by Gutjahr, Welzl, and Woeginger. We then focus on the case when  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  for which the  -colouring problem is  -complete. We contrast these with several families of oriented triads  which have tree duality, or bounded treewidth duality, and hence polynomial  -colouring problems. If  , then no oriented triad  with an  -complete  -colouring problem can have bounded treewidth duality; however no proof of this is known, for any oriented triad  . We prove that none of the oriented triads  with  -complete  -colouring problems given in the companion paper has tree duality. |
| |
| Keywords: | |
|
| 点击此处可从《Transactions of the American Mathematical Society》浏览原始摘要信息 |
|
点击此处可从《Transactions of the American Mathematical Society》下载全文 |
|
