×

Correspondence homomorphisms to reflexive graphs. (English) Zbl 1383.05212

Bassino, Frédérique (ed.) et al., LAGOS 2017. Selected papers of the 9th Latin-American algorithms, graphs, and optimization symposium, Marseille, France, September 11–15, 2017. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 62, 9-14 (2017).
Summary: Correspondence homomorphisms are a common generalization of homomorphisms and of correspondence colourings. For a fixed reflexive target graph \(H\), the problem is to decide whether an input graph \(G\), with each edge labeled by a pair of permutations of \(V(H)\), admits a homomorphism to \(H\) ‘corresponding’ to the labels. We classify the complexity of this problem as a function of \(H\). It turns out that there is dichotomy – each of the problems is polynomial or NP-complete. While most graphs \(H\) yield NP-complete problems, there is an interesting polynomial case when the problem can be solved by Gaussian elimination. We also classify the complexity of the analogous correspondence list homomorphism problems.
For the entire collection see [Zbl 1383.05001].

MSC:

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

References:

[1] Bulatov, A. A., A dichotomy theorem for nonuniform CSPs
[2] Complexity of cnservative constraint satisfaction problems, ACM Trans. Comput. Logic, 12 (2011), #24
[3] Dvořák, Z.; Postle, L., Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8 · Zbl 1379.05034
[4] Feder, T.; Vardi, M. Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Computing, 28, 57-104 (1998) · Zbl 0914.68075
[5] Feder, T.; Hell, P., List homomorphisms to reflexive graphs, J. Comb. Theory B, 72, 236-250 (1998) · Zbl 0904.05078
[6] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[7] 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
[8] Feder, T.; Hell, P., Complexity of correspondence homomorphisms
[9] Rafiey, A.; Kinne, J.; Feder, T., Dichotomy for digraph homomorphism problems
[10] Godsil, C.; Royle, G., Algebraic Graph Theory, Springer Graduate Texts in Mathematics, vol. 207 (2001) · Zbl 0968.05002
[11] Hell, P.; Nešetřil, J., On the complexity of H-colouring, J. Comb. Theory B, 48, 92-110 (1990) · Zbl 0639.05023
[12] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139
[13] Hell, P.; Rafiey, A., The dichotomy of list homomorphisms for digraphs, SODA, 1703-1713 (2011) · Zbl 1376.68067
[14] Hoory, S.; Linial, N.; Wigderson, A., Expander graphs and their applications, Bull. Amer. Math. Soc., 43, 439-561 (2006) · Zbl 1147.68608
[15] Ladner, R. E., On the structure of polynomial time reducibility, J. Assoc. Comput. Mach., 22, 155-171 (1975) · Zbl 0322.68028
[16] Lovász, L., Large Networks and Graph Limits (2012), American Mathematical Society · Zbl 1292.05001
[17] Zhuk, D., The proof of CSP dichotomy conjecture · 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.