Remarkably, all algorithms hitherto proposed in the literature on (variants of) CSPs can be broadly classified as instances of one of the two aforementioned techniques, or a combination of both.
A primary example of the first type is the bounded width algorithm, which outputs \(\textsc {Yes}\)  if a consistent collection of partial homomorphisms exists [1]}.
More powerful versions of the local consistency technique require that the partial homomorphisms be sampled according to a probability distribution (which results in the Sherali-Adams LP hierarchy [2]}), and that the probabilities be treated as vectors satisfying certain orthogonality requirements (which gives the sum-of-squares or Lasserre SDP hierarchy [3]}, [4]}, [5]}).
As for the second type, the linear-system formulation of a CSP can be efficiently solved in \(\mathbb {Z}\)  by computing the Hermite or the Smith canonical forms of the corresponding coefficient matrix [6]}; this results in the affine integer programming (\(\operatorname{AIP}\) ) relaxation, studied in the context of PCSPs in [7]}, [8]}, [9]}, [10]}.
A hierarchy of linear Diophantine equations was also studied by Berkholz and Grohe [11]} in the context of the graph isomorphism problem.
