Reconfiguration beyond Hom-spaces in promise CSPs: on the complexity of approximating 1-in-3 SAT

What is the complexity of finding a k-colouring of a graph that is promised to be 3-colourable? This is a classical approximation problem, known as approximate graph colouring, and a motivating example for the promise CSP (PCSP) paradigm. In a PCSP, one is given a set of variables with overlapping constraints and it is asked whether there is an assignment so that the constraints satisfy a given set of predicates or whether they are unable to satisfy a set of weaker predicates.

Similarly to CSPs, the complexity classification of PCSPs seems to rely heavily on the analysis of polymorphisms; that is, the symmetries of the solution space of the problem at hand. Whilst for CSPs the community singled out the source of hardness early on (lack of non-trivial polymorphisms), for PCSPs we are far from pinpointing this property, and combinatorial topology is believed to be a necessary tool in many hardness proofs. In fact, many early results on approximate graph and hypergraph colouring used arguments relying on colouring obstructions or homotopy equivalence of mappings between Hom-spaces. These methods, however, tend to fail when the Hom-spaces of the predicates collapse to a discrete object.

In this talk, I will present the proof of hardness of a particular approximation of 1-in-3 SAT where a Hom-space collapses but the very same topological tools used in PCSPs so far appear in a slightly different disguise. This is joint work with Andrei Krokhin.