Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth
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\subseteq 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_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ when given an instance $I$ with a tree decomposition $\mathcal{T}$ of width $\mathsf{tw}$ of the primal graph of $I$. (2) If $c_Γ\geq 2$, there is no such algorithm solving the problem in time $(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)}$ for any $\varepsilon > 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.
Authors
- Marta Piecyk (ORCID: https://orcid.org/0000-0001-9162-8300)
- Paweł Rzążewski (ORCID: https://orcid.org/0000-0001-7696-3848)
- Daniel Marx (ORCID: https://orcid.org/0000-0002-3108-9760)
- Stanislav Živný (ORCID: https://orcid.org/0000-0002-0263-159X)
- George Osipov (ORCID: https://orcid.org/0000-0002-2884-9837)
- Jakob Greilhuber (ORCID: https://orcid.org/0009-0001-8796-6400)
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-12
- DOI
- https://doi.org/10.48550/arxiv.2611.16729
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint