Carbonnel, C., Romero, M., & Zivny, S. (2022). The Complexity of GeneralValued Constraint Satisfaction Problems Seen from the Other Side. SIAM J. Comput., 51(1), 19–69.
Abstract: The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted lefthandside structures, the results of Dalmau, Languages and Programming, Springer, New York, 2007, pp. 279290] establish the precise borderline of polynomialtime solvability (subject to complexitytheoretic assumptions) and of solvability by boundedconsistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The generalvalued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted lefthandside valued structures, we establish the precise borderline of polynomialtime solvability (subject to complexitytheoretic assumptions) and of solvability by the kth level of the SheraliAdams LP hierarchy (unconditionally). We also obtain results on related problems concerned with finding a solution and recognizing the tractable cases; the latter has an application in database theory.
