×

The complexity of tropical graph homomorphisms. (English) Zbl 1367.05141

Summary: A tropical graph \((H, c)\) consists of a graph \(H\) and a (not necessarily proper) vertex-colouring \(c\) of \(H\). Given two tropical graphs \((G, c_1)\) and \((H, c)\), a homomorphism of \((G, c_1)\) to \((H, c)\) is a standard graph homomorphism of \(G\) to \(H\) that also preserves the vertex-colours. We initiate the study of the computational complexity of tropical graph homomorphism problems. We consider two settings. First, when the tropical graph \((H, c)\) is fixed; this is a problem called \((H, c)\)-colouring. Second, when the colouring of \(H\) is part of the input; the associated decision problem is called \(H\)-tropical-colouring. Each \((H, c)\)-colouring problem is a constraint satisfaction problem (CSP), and we show that a complexity dichotomy for the class of \((H, c)\)-colouring problems holds if and only if the Feder-Vardi dichotomy conjecture for CSPs is true. This implies that \((H, c)\)-colouring problems form a rich class of decision problems. On the other hand, we were successful in classifying the complexity of at least certain classes of \(H\)-tropical-colouring problems.

MSC:

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

References:

[1] Alon, N.; Marshall, T. H., Homomorphisms of edge-colored graphs and Coxeter groups, J. Algebraic Combin., 8, 1, 5-13 (1998) · Zbl 0911.05034
[2] Bang-Jensen, J.; Hell, P., The effect of two cycles on the complexity of colorings by directed graphs, Discrete Appl. Math., 26, 1, 1-23 (1990) · Zbl 0697.05029
[3] Bang-Jensen, J.; Hell, P.; MacGillivray, G., The complexity of colouring by semicomplete digraphs, SIAM J. Discrete Math., 1, 3, 281-298 (1988) · Zbl 0678.05018
[4] Bang-Jensen, J.; Hell, P.; MacGillivray, G., Hereditarily hard \(H\)-colouring problems, Discrete Math., 138, 1-3, 75-92 (1995) · Zbl 0816.68090
[5] Barto, L.; Kozik, M.; Niven, T., The CSP dichotomy holds for digraphs with no sources and sinks (a positive answer to a conjecture of Bang-Jensen and Hell), SIAM J. Comput., 38, 5, 1782-1802 (2009) · Zbl 1191.68460
[6] Brewster, R. C., Vertex Colourings of Edge-Coloured Graphs (1993), Simon Fraser University: Simon Fraser University Canada, Ph.D. Thesis
[7] Brewster, R. C., The complexity of colouring symmetric relational systems, Discrete Appl. Math., 49, 1-3, 95-105 (1994) · Zbl 0810.05025
[8] Brewster, R. C.; Foucaud, F.; Hell, P.; Naserasr, R., The complexity of signed and edge-coloured graph homomorphisms, Discrete Math., 340, 2, 223-235 (2017), http://arxiv.org/abs/1510.05502 · Zbl 1351.05099
[9] Brewster, R. C.; Hell, P., On homomorphisms to edge-colored cycles, Electron. Notes Discrete Math., 5, 46-49 (2000) · Zbl 1412.05064
[10] Brewster, R. C.; MacGillivray, G., The homomorphism factoring problem, J. Combin. Math. Combin. Comput., 25, 33-53 (1997) · Zbl 0907.05043
[12] Bulatov, A. A., A dichotomy constraint on a three-element set, J. ACM, 53, 1, 66-120 (2006) · Zbl 1316.68057
[13] Draeger, K., Answer to the question Complexity of digraph homomorphism to an oriented cycle, Theoret. Comput. Sci. Stack Exchange (2016), http://cstheory.stackexchange.com/q/33899
[14] Feder, T., Classification of homomorphisms to oriented cycles and of \(k\)-partite satisfiability, SIAM J. Discrete Math., 14, 4, 471-480 (2001) · Zbl 0982.05097
[15] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combin. Theory Ser. B, 72, 2, 236-250 (1998) · Zbl 0904.05078
[16] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 1, 230-246 (2006) · Zbl 1111.68115
[17] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 4, 487-505 (1999) · Zbl 0985.05048
[18] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 1, 61-80 (2003) · Zbl 1057.05033
[20] Feder, T.; Vardi, M. Y., The Computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (1998) · Zbl 0914.68075
[22] Hell, P.; Nešetřil, J., On the complexity of \(H\)-coloring, J. Combin. Theory Ser. B, 48, 1, 92-110 (1990) · Zbl 0639.05023
[23] Hell, P.; Nešetřil, J., (Graphs and Homomorphisms. Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications (2004), Oxford University Press)
[24] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of tree homomorphisms, Discrete Appl. Math., 70, 1, 23-36 (1996) · Zbl 0868.05018
[25] Karp, R. M., Reducibility among combinatorial problems, (R. E., Miller; J. W., Thatcher, Complexity of Computer Computations (1972), Plenum Press), 85-103 · Zbl 1467.68065
[26] Krom, M. R., The decision problem for a class of first-order formulas in which all disjunctions are binary, Z. Math. Log. Grundl. Math., 13, 1-2, 15-20 (1967) · Zbl 0162.31601
[27] Ladner, R., On the structure of polynomial time reducibility, J. ACM, 22, 1, 155-171 (1975) · Zbl 0322.68028
[28] Moret, B. M.E., The Theory of Computation (1998), Addison Wesley, Problem 7.1, Part 2 (Chapter 7) · Zbl 0594.90036
[30] Trotter, W. T.; Moore, J. I., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math., 16, 4, 361-381 (1976) · Zbl 0356.06007
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.