The
Valued Constraint Satisfaction Problem (
VCSP{\textsc{VCSP}}) is a general framework encompassing many optimisation problems. We discuss precisely what it means for a problem to be
modelled in the
VCSP{\textsc{VCSP}} framework. Using our analysis, we show that some optimisation problems, such as (
s,
t)
-Min-Cut and
Submodular Function Minimisation, can be modelled using a restricted set of valued constraints which are tractable to solve regardless of how they are combined.
Hence, these problems can be viewed as special cases of more general problems which include all possible instances using the
same forms of valued constraint. However, other, apparently similar, problems such as
Min-Cut and
Symmetric Submodular Function Minimisation, which also have polynomial-time algorithms, can only be naturally modelled in the
VCSP{\textsc{VCSP}} framework by using valued constraints which can represent NP-complete problems. This suggests that the reason for tractability
in these problems is more subtle; it relies not only on the form of the valued constraints, but also on the precise structure
of the problem. Furthermore, our results suggest that allowing constant constraints can significantly alter the complexity
of problems in the
VCSP{\textsc{VCSP}} framework, in contrast to the
CSP{\textsc{CSP}} framework.
Stanislav Živný is supported by EPSRC grant EP/F01161X/1.