×

Dichotomy for tree-structured trigraph list homomorphism problems. (English) Zbl 1223.05095

Summary: Trigraph list homomorphism problems, also known as list matrix partition problems, generalize graph list colouring and digraph list homomorphism problems. While digraph list homomorphism problems enjoy a dichotomy (each problem is \(NP\)-complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems, and in the few cases where dichotomy has been proved, for small trigraphs, the progress has been slow.
In this paper, we prove dichotomy for trigraph list homomorphism problems where the underlying graph of the trigraph is a tree. In fact, we show that for these trigraphs the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. The result can be extended to a larger class of trigraphs, and we illustrate the extension on trigraph cycles.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A.A. Bulatov, Complexity of conservative constraint satisfaction problems, ACM Transactions on Computational Logic (2011) (in press).; A.A. Bulatov, Complexity of conservative constraint satisfaction problems, ACM Transactions on Computational Logic (2011) (in press). · Zbl 1351.68113
[2] Cameron, K.; Eschen, E. M.; Hoàng, C. T.; Sritharan, R., The complexity of the list partition problem for graphs, SIAM Journal on Discrete Mathematics, 21, 900-929 (2007) · Zbl 1151.05045
[3] M. Cygan, M. Pilipczuk, M. Pilipczuk, J.O. Wojtaszczyk, The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem), in: Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2011, pp. 1666-1674.; M. Cygan, M. Pilipczuk, M. Pilipczuk, J.O. Wojtaszczyk, The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem), in: Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2011, pp. 1666-1674. · Zbl 1376.68063
[4] de Figueiredo, C. M.H.; Klein, S., Finding skew partitions efficiently, Journal of Algorithms, 37, 505-521 (2000) · Zbl 0964.68107
[5] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM Journal on Computing, 36, 230-246 (2006) · Zbl 1111.68115
[6] Feder, T.; Hell, P., Matrix partitions of perfect graphs, Discrete Mathematics, 306, 2450-2460 (2006) · Zbl 1143.05035
[7] Feder, T.; Hell, P.; Hochstättler, W., Generalized colourings of cographs, (Graph Theory in Paris (2006), Birkhauser Verlag), 149-167, invited chapter · Zbl 1114.05060
[8] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, Journal of Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[9] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM Journal on Discrete Mathematics, 16, 449-478 (2003) · Zbl 1029.05143
[10] Feder, T.; Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., List matrix partitions of chordal graphs, Theoretical Computer Science, 349, 52-66 (2005) · Zbl 1084.05026
[11] T. Feder, P. Hell, D. Král’, J. Sgall, Two algorithms for general list matrix partitions, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, pp. 870-876.; T. Feder, P. Hell, D. Král’, J. Sgall, Two algorithms for general list matrix partitions, in: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2005, pp. 870-876. · Zbl 1297.68091
[12] T. Feder, P. Hell, D.G. Schell, J. Stacho, Dichotomy for tree-structured trigraph list homomorphism problems, Preprint. http://arxiv.org/abs/1009.0358; T. Feder, P. Hell, D.G. Schell, J. Stacho, Dichotomy for tree-structured trigraph list homomorphism problems, Preprint. http://arxiv.org/abs/1009.0358 · Zbl 1223.05095
[13] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Applied Mathematics, 154, 2458-2469 (2006) · Zbl 1106.05060
[14] Feder, T.; Hell, P.; Xie, W., Matrix partitions with finitely many obstructions, Electronic Journal of Combinatorics, 14, R58 (2007) · Zbl 1158.05326
[15] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM Journal on Computing, 28, 57-104 (1999) · Zbl 0914.68075
[16] Hammer, P. L.; Simeone, B., The splittance of a graph, Combinatorica, 1, 275-284 (1981) · Zbl 0492.05043
[17] Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Applied Mathematics, 141, 185-194 (2004) · Zbl 1043.05097
[18] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, Journal of Combinatorial Theory. Series B, 48, 92-110 (1990) · Zbl 0639.05023
[19] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[20] P. Hell, A. Rafiey, The dichotomy of list homomorphisms for digraphs, in: Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2011, pp. 1703-1713.; P. Hell, A. Rafiey, The dichotomy of list homomorphisms for digraphs, in: Proceedings of the Twenty Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2011, pp. 1703-1713. · Zbl 1376.68067
[21] Lekkerkerker, C. G.; Boland, J. C., Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, 51, 45-64 (1962) · Zbl 0105.17501
[22] D.G. Schell, Matrix partitions of digraphs, Master’s Thesis, Simon Fraser University, 2008.; D.G. Schell, Matrix partitions of digraphs, Master’s Thesis, Simon Fraser University, 2008.
[23] Tarjan, R. E., Decomposition by clique separators, Discrete Mathematics, 55, 221-232 (1985) · Zbl 0572.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.