CLAP: A New Algorithm for Promise CSPs
Lorenzo Ciardo, Stanislav Živný
Abstract
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 characterization of the power of CLAP in terms of a minion homomorphism. Using this characterization, 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\n algorithm of Brakensiek et al. [SIAM J. Comput., 49 (2020), pp. 1232--1248] and not by a reduction to tractable finite-domain CSPs.
Topics & Concepts
Constraint satisfaction problemHomomorphismRelaxation (psychology)Discrete mathematicsAlgorithmMathematicsComputer scienceCombinatoricsArtificial intelligencePsychologySocial psychologyProbabilistic logicComplexity and Algorithms in GraphsAdvanced Graph Theory ResearchConstraint Satisfaction and Optimization