Topology and adjunction in promise constraint satisfaction

DOI10.1137/20M1378223arXiv2003.11351MaRDI QIDQ6337399FDOQ6337399

Authors: Andrei Krokhin, Jakub Opršal, Marcin Wrochna, S. Zivny 

Publication date: 25 March 2020

Abstract: The approximate graph colouring problem, whose complexity is unresolved in most cases, concerns finding a $c$-colouring of a graph that is promised to be $k$-colourable, where $cgeqk$. This problem naturally generalises to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyse the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph colouring and promise graph homomorphism problems.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Topology and adjunction in promise constraint satisfaction

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