Answers are grounded in this paper and cite their sources.
We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain D and a fixed finite constraint language $Γ$, in the setting where $Γ$ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let c_Γ be the size of the largest set S⊆ D such that $Γ$ can express (using the usual VCSP closure operations) a binary disequality function on elements of S. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value c_Γ. (1) The problem can be solved in time (c_Γ)ᵗʷ · (|I| + |T|)O(1) when given an instance I with a tree decomposition T of width tw of the primal graph of I. (2) If c_Γ≥ 2, there is no such algorithm solving the problem in time (c_Γ- ε)ᵗʷ · (|I| + |T|)O(1) for any ε > 0, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.
No takes yet. Share an insight, caveat, or question.
Greilhuber et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: