Being based on a standard dynamic programming scheme, correctness of ComputeOptimalSolution can be shown by structural induction on the
subtrees of \(T\)  [1]}. Moreover, by analyzing its running time, one may note that dealing with cost functions does not (asymptotically)
provide any overhead w.r.t. Yannakakis's algorithm [2]} for plain CSPs. Following [1]}, the following can be shown for the
more general case of \({\mbox{CSOP}}\)  instances having bounded generalized hypertree-width hypergraphs.In all complexity results, we assume
the weighting function \({w}\)  be explicitly listed in the input (otherwise, just add the cost of computing through \({w}\)  all cost values for the
variable assignments of the given input instance).
