CLAP: Breaking the symmetry of Promise Constraint Satisfaction

We propose a new algorithm for Promise Constraint Satisfaction Problems (PCSPs). It is a combination of the Constraint Basic LP relaxation and the Affine IP relaxation (CLAP). We give a characterisation of the power of CLAP in terms of a minion homomorphism. Using this characterisation, we identify a certain weak notion of symmetry which, if satisfied by infinitely many polymorphisms of PCSPs, guarantees tractability.We demonstrate that there are PCSPs solved by CLAP that are not solved by any of the existing algorithms for PCSPs; in particular, not by the BLP+AIP algorithm of Brakensiek and Guruswami [SODA'20] and not by a reduction to tractable finite-domain CSPs.

 

Based on a paper that appeared in SODA'22.

 

This is joint work with Standa Živný.