article published yes Vladimir Kolmogorov author 3D50B0BA-F248-11E8-B48F-1D18A9856A87 Johan Thapper author Stanislav Živný author VlKo department A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs). Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2. Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees. SIAM2015 eng 1311.4219 00035396710000110.1137/130945648 4411 - 36 https://research-explorer.ista.ac.at/record/2518 Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36. V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36. Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href="https://doi.org/10.1137/130945648">10.1137/130945648</a> Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:<a href="https://doi.org/10.1137/130945648">10.1137/130945648</a>. V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” <i>SIAM Journal on Computing</i>, vol. 44, no. 1. SIAM, pp. 1–36, 2015. Kolmogorov, V., Thapper, J., &#38; Živný, S. (2015). The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/130945648">https://doi.org/10.1137/130945648</a> Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>. SIAM, 2015. <a href="https://doi.org/10.1137/130945648">https://doi.org/10.1137/130945648</a>. 22712018-12-11T11:56:41Z2025-09-23T14:14:57Z