On the complexity of the approximate hypergraph homomorphism problem
share
Understanding the computational complexity of fragments of the Constraint Satisfaction Problem (CSP) has been instrumental in the formulation of Feder-Vardi's Dichotomy Conjecture and its positive resolution by Bulatov and Zhuk. An approximation version of the CSP - known as the promise CSP - has recently gained prominence as an exciting generalisation of the CSP that captures many fundamental computational problems. In this work, we establish a computational complexity dichotomy for a natural fragment of the promise CSP consisting of homomorphism problems involving a class of 3-uniform hypergraphs.
READ FULL TEXT