×

Complexity of correspondence \(H\)-colourings. (English) Zbl 1440.05150

Summary: Correspondence homomorphisms generalize standard homomorphisms as well as correspondence colourings (also known as DP-colourings). For a fixed target graph \(H\), we study the problem of deciding whether an input graph \(G\), with each edge labelled by a pair of permutations of \(V ( H )\), admits a homomorphism to \(H\) ‘corresponding’ to the labels. Homomorphisms to \(H\) are called \(H\)-colourings, and we employ the similar term correspondence \(H\)-colourings for correspondence homomorphisms to \(H\). We classify the complexity of this problem as a function of the fixed graph \(H\). It turns out that there is dichotomy – each of the problems is polynomial-time solvable or NP-complete. While most graphs \(H\) yield NP-complete problems, there are interesting cases of graphs \(H\) for which the problem can be solved in polynomial time by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems, and also the complexity of a bipartite version of both problems. We give detailed proofs for the case when \(H\) is reflexive, and, for the record, sketch the remaining proofs.

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C15 Coloring of graphs and hypergraphs
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bernshteyn, A.; Kostochka, A.; Zhu, X., Fractional DP-colorings of sparse graphs, J. Graph Theory, 1-19 (2019)
[2] Brewster, R. C.; Siggers, M. H., A complexity dichotomy for signed \(H\)-colouring, Discrete Math., 341, 2768-2773 (2018) · Zbl 1393.05108
[3] A.A. Bulatov, A dichotomy theorem for non-uniform CSP’s, in: 58th Annual IEEE FOCS 2017.
[4] Bulatov, A. A., Complexity of cnservative constraint satisfaction problems, ACM Trans. Comput. Log., 12, #24 (2011) · Zbl 1351.68113
[5] J.Y. Cai, X. Chen, P.Y. Lu, Graph homomorphisms with complex values: a dichotomy theorem, ICALP 2010, pp. 275-286. · Zbl 1288.05178
[6] Dvořák, Z.; Postle, L., Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8, J. Combin. Theory Ser. B, 128, 38-54 (2018) · Zbl 1379.05034
[7] Dyer, M. E.; Greenhill, C., The complexity of counting graph homomorphisms, Random Structures Algorithms, 17, 260-289 (2000) · Zbl 0965.68073
[8] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Combin. Theory B, 72, 236-250 (1998) · Zbl 0904.05078
[9] Feder, T.; Hell, P., Correspondence homomorphisms to reflexive graphs, Extended Abstract from LAGOS 2017. Extended Abstract from LAGOS 2017, Electron. Notes Discrete Math., 62, 9-14 (2017) · Zbl 1383.05212
[10] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[11] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[12] 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, 57-104 (1998) · Zbl 0914.68075
[13] Fiala, J.; Kratochvíl, J., Locally constrained graph homomorphisms – structure, complexity, and applications, Comp. Sci. Rev., 2, 97-111 (2008) · Zbl 1302.05122
[14] Foucaud, F.; Haratyunyan, A.; Hell, P.; Legay, S.; Manoussakis, Y.; Naserasr, R., The complexity of tropical graph homomorphisms, Discrete Appl. Math., 229C, 64-81 (2017) · Zbl 1367.05141
[15] Godsil, C.; Royle, G., (Algebraic Graph Theory. Algebraic Graph Theory, Springer Graduate Texts in Mathematics, vol. 207 (2001)) · Zbl 0968.05002
[16] Golovach, P. A.; Paulusma, D.; Song, J., Computing vertex-surjective homomorphisms to partially reflexive trees, Theoret. Comput. Sci., 457, 86-100 (2012) · Zbl 1251.05031
[17] Hell, P., Graph partitions with prescribed patterns, Eur. J. Comb., 35, 335-353 (2014) · Zbl 1292.05214
[18] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory Ser. 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: SODA, 2011, pp. 1703-1713. · Zbl 1376.68067
[21] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc., 43, 439-561 (2006) · Zbl 1147.68608
[22] A. Kazeminia, A.A. Bulatov, Counting homomorphisms modulo a prime number, arXiv:1905.10682 [cs.CC]. · Zbl 07561703
[23] Ladner, R. E., On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155-171 (1975) · Zbl 0322.68028
[24] Lovász, L., Large Networks and Graph Limits (2012), American Mathematical Society · Zbl 1292.05001
[25] T. Wang, Every toroidal graph without triangles adjacent to \(5\)-cycles is DP-\(4\)-colorable, arXiv:1803.01197 [math.CO].
[26] D. Zhuk, A proof of CSP Dichotomy Conjecture, in: 58th Annual IEEE FOCS 2017. · Zbl 1491.68128
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.