Complexity of correspondence H-colourings

DOI10.1016/J.DAM.2019.11.005MaRDI QIDQ2184689zbMATH OpenOpenAlexFDO

Authors Tomás Feder, Pavol Hell

Publication date 29 May 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.05881

zbMATH Keywords

\(H\)-colouringscorrespondence colouringsdichotomyDP-colouringsgraph homomorphismsNP-completenesspolynomial algorithms

Mathematics Subject Classification ID

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

Abstract: Correspondence homomorphisms are both a generalization of standard homomorphisms and a generalization of correspondence colourings. For a fixed 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, in a sense explained below. 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 is solved by Gaussian elimination. We also classify the complexity of the analogous correspondence {em list homomorphism} problems, and also the complexity of a {em bipartite version} of both problems. We emphasize the proofs for the case when $H$ is reflexive, but, for the record, we include a rough sketch of the remaining proofs in an Appendix.

Recommendations

• Correspondence homomorphisms to reflexive graphs
• On the complexity of H-coloring
• The complexity of the list homomorphism problem for graphs
• The complexity of the list homomorphism problem for graphs
• On homomorphisms to edge-coloured cycles

Cites work

• A complexity dichotomy for signed \(\mathbf{H}\)-colouring
• A proof of the CSP dichotomy conjecture
• Bi‐arc graphs and the complexity of list homomorphisms
• Complexity of conservative constraint satisfaction problems
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• Correspondence homomorphisms to reflexive graphs
• Counting homomorphisms modulo a prime number
• Expander graphs and their applications
• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• Graph partitions with prescribed patterns
• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Large networks and graph limits
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• On the complexity of H-coloring
• On the Structure of Polynomial Time Reducibility
• The complexity of tropical graph homomorphisms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The dichotomy of list homomorphisms for digraphs

Cited in

(8)

• The complexity of colouring symmetric relational systems
• The complexity of infinite \(H\)-colouring
• Correspondence homomorphisms to reflexive graphs
• On the complexity of coloring areflexive \(h\)-ary relations with given permutation group
• Structure Learning of H-colorings
• scientific article; zbMATH DE number 2151253 (Why is no real title available?)
• The complexity of the list homomorphism problem for graphs
• List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs

This page was built for publication: Complexity of correspondence \(H\)-colourings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2184689)