Local consistency as a reduction between constraint satisfaction problems

Abstract

We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions in a similar way as the algebraic approach classifies gadget reductions between CSPs. This research is motivated by the requirement of more expressive reductions in the scope of promise CSPs. While gadget reductions are enough to provide all necessary hardness in the scope of (finite domain) non-promise CSP, in promise CSPs a wider class of reductions needs to be used. We provide a general framework of reductions, which we call consistency reductions, that covers most (if not all) reductions recently used for proving NP-hardness of promise CSPs. We prove some basic properties of these reductions, and provide the first steps towards understanding the power of consistency reductions by characterizing a fragment associated to arc-consistency in terms of polymorphisms of the template. In addition to showing hardness, consistency reductions can also be used to provide feasible algorithms by reducing to a fixed tractable (promise) CSP, for example, to solving systems of affine equations. In this direction, among other results, we describe the well-known Sherali-Adams hierarchy for CSP in terms of a consistency reduction to linear programming.

References in corpus (9)

• Algebraic approach to promise constraint satisfaction
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• The power of Sherali-Adams relaxations for general-valued CSPs
• The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
• The complexity of promise SAT on non-Boolean domains
• Improved hardness for H-colourings of G-colourable graphs
• The complexity of 3-colouring $H$-colourable graphs
• An invitation to the promise constraint satisfaction problem
• A note on hardness of promise hypergraph colouring

Cited by in corpus (5)

• Injective hardness condition for PCSPs
• Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Symmetric Linear Arc Monadic Datalog and Gadget Reductions
• Solving promise equations over monoids and groups
• Hierarchies of Minion Tests for PCSPs through Tensors