Duality and Polynomial Testing of Tree Homomorphisms
HTML articles powered by AMS MathViewer
- by P. Hell, J. Nesetril and X. Zhu PDF
- Trans. Amer. Math. Soc. 348 (1996), 1281-1297 Request permission
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
- Stefan Arnborg, Jens Lagergren, and Detlef Seese, Easy problems for tree-decomposable graphs, J. Algorithms 12 (1991), no. 2, 308–340. MR 1105479, DOI 10.1016/0196-6774(91)90006-K
- R. Bačík and S. Mahajan, Semidefinite programming and its applications to $NP$ problems, manuscript, 1995.
- Jørgen Bang-Jensen and Pavol Hell, The effect of two cycles on the complexity of colourings by directed graphs, Discrete Appl. Math. 26 (1990), no. 1, 1–23. MR 1028872, DOI 10.1016/0166-218X(90)90017-7
- Jørgen Bang-Jensen, Pavol Hell, and Gary MacGillivray, The complexity of colouring by semicomplete digraphs, SIAM J. Discrete Math. 1 (1988), no. 3, 281–298. MR 955645, DOI 10.1137/0401029
- Jørgen Bang-Jensen, Pavol Hell, and Gary MacGillivray, On the complexity of colouring by superdigraphs of bipartite graphs, Discrete Math. 109 (1992), no. 1-3, 27–44. Algebraic graph theory (Leibnitz, 1989). MR 1192368, DOI 10.1016/0012-365X(92)90276-L
- J. Bang-Jensen, P. Hell and G. MacGillivray, Hereditarily hard colouring problems, Discrete Math. 138 (1995), 75–92.
- J. A. Bondy and U. S. R. Murty, Graph theory with applications, American Elsevier Publishing Co., Inc., New York, 1976. MR 0411988
- Bruno Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput. 85 (1990), no. 1, 12–75. MR 1042649, DOI 10.1016/0890-5401(90)90043-H
- Rina Dechter, From local to global consistency, Artificial Intelligence 55 (1992), no. 1, 87–107. MR 1167277, DOI 10.1016/0004-3702(92)90043-W
- T. Feder, Classification of homomorphisms to oriented cycles (draft), manuscript, 1994.
- T. Feder and M. Y. Vardi, Monotone monadic SNP and constraint satisfaction, 25th Annual ACM Syposium on Theory of Computing, 1993, 612-622.
- U. Feige and L. Lovász, Two-prover one-round proof systems: Their power and their problems, 24th Annual ACM Syposium on Theory of Computing, 1992, 733-744.
- Martin Charles Golumbic, Algorithmic graph theory and perfect graphs, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, Ont., 1980. With a foreword by Claude Berge. MR 562306
- W. Gutjahr, Graph colourings, Ph. D. Thesis, Free University Berlin, 1991.
- W. Gutjahr, E. Welzl and G. Woeginger, Polynomial graph colourings, Discrete Appl. Math. 35 (1992), 29-46.
- Roland Häggkvist and Pavol Hell, Universality of $A$-mote graphs, European J. Combin. 14 (1993), no. 1, 23–27. MR 1197472, DOI 10.1006/eujc.1993.1004
- Pavol Hell and Jaroslav Ne et il, On the complexity of $H$-coloring, J. Combin. Theory Ser. B 48 (1990), no. 1, 92–110. MR 1047555, DOI 10.1016/0095-8956(90)90132-J
- P. Hell and J. Nešetřil, Homomorphisms of graphs and of their orientations, Monatsh. Math. 85 (1978), no. 1, 39–48. MR 495696, DOI 10.1007/BF01300959
- P. Hell, J. Nešetřil and X. Zhu, Duality and polynomial testing of tree homomorphisms, Technical Report, KAM series 93-243, Department of Applied Mathematics, Charles University, Prague, 1993.
- P. Hell, J. Nešetřil and X. Zhu, Complexity of tree homomorphisms, Discrete Appl. Math., to appear.
- P. Hell, J. Nešetřil and X. Zhu, Duality of Graph Homomorphisms, Combinatorics, Paul Erdös is Eighty, Vol. 2, Bolyai Society Mathematical Studies, Budapest (Hungary), 1995.
- P. Hell and X. Zhu, The existence of homomorphisms to oriented cycles, SIAM J. on Disc. Math. 8 (1995), 208–222
- L. Kantorovitch, The method of successive approximations for functional equations, Acta Math. 71 (1939), 63–97. MR 95, DOI 10.1007/BF02547750
- Pavol Hell, Hui Shan Zhou, and Xu Ding Zhu, Homomorphisms to oriented cycles, Combinatorica 13 (1993), no. 4, 421–433. MR 1262918, DOI 10.1007/BF01303514
- Pavel Komárek, Some new good characterizations for directed graphs, Časopis Pěst. Mat. 109 (1984), no. 4, 348–354 (English, with Russian summary). MR 774277
- Richard E. Ladner, On the structure of polynomial time reducibility, J. Assoc. Comput. Mach. 22 (1975), 155–171. MR 464698, DOI 10.1145/321864.321877
- Gary MacGillivray, On the complexity of colouring by vertex-transitive and arc-transitive digraphs, SIAM J. Discrete Math. 4 (1991), no. 3, 397–408. MR 1105945, DOI 10.1137/0404035
- H. A. Maurer, J. H. Sudborough, and E. Welzl, On the complexity of the general coloring problem, Inform. and Control 51 (1981), no. 2, 128–145. MR 686834, DOI 10.1016/S0019-9958(81)90226-6
- Ugo Montanari, Networks of constraints: fundamental properties and applications to picture processing, Information Sci. 7 (1974), 95–132. MR 0413625, DOI 10.1016/0020-0255(74)90008-5
- J. Nešetřil, Theory of graphs , SNTL (Praha), 1979.
- Jaroslav Ne et il and Aleš Pultr, On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math. 22 (1978), no. 3, 287–300. MR 522724, DOI 10.1016/0012-365X(78)90062-6
- J. Nešetřil and X. Zhu, On Bounded Treewidth Duality of Graphs, manuscript, 1994.
- Neil Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms 7 (1986), no. 3, 309–322. MR 855559, DOI 10.1016/0196-6774(86)90023-4
- E. Welzl, Symmetric graphs and interpretations, J. Combin. Th. (B) 37 (1984), 235-244.
- X. Zhu, A polynomial algorithm for homomorphisms to oriented cycles, J. of Algorithms, to appear.
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
- Received by editor(s): July 20, 1993
- © Copyright 1996 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 348 (1996), 1281-1297
- MSC (1991): Primary 05C85; Secondary 68Q25
- DOI: https://doi.org/10.1090/S0002-9947-96-01537-1
- MathSciNet review: 1333391