The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
Carbonnel
C
author
Romero
M
author
Zivny
S
author
2022
The constraint satisfaction problem (CSP) is concerned with homomorphisms between two structures. For CSPs with restricted left-hand-side structures, the results of Dalmau, Languages and Programming, Springer, New York, 2007, pp. 279--290] establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by bounded-consistency algorithms (unconditionally) as bounded treewidth modulo homomorphic equivalence. The general-valued constraint satisfaction problem (VCSP) is a generalization of the CSP concerned with homomorphisms between two valued structures. For VCSPs with restricted left-hand-side valued structures, we establish the precise borderline of polynomial-time solvability (subject to complexity-theoretic assumptions) and of solvability by the kth level of the Sherali--Adams 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.
valued constraint satisfaction
homomorphism problems
fractional homomorphism
treewidth
Sherali--Adams LP
WOS:000760359900002
exported from refbase (show.php?record=1736), last updated on Thu, 23 Mar 2023 11:01:36 -0300
text
10.1137/19M1250121
Carbonnel_etal2022
SIAM Journal on Computing
SIAM J. Comput.
2022
continuing
periodical
academic journal
51
1
19
69
0097-5397