The complexity of Boolean surjective general-valued CSPs

Peter Fulla, Hannes Uppman, Stanislav Zivny

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $(\mathbb{Q}\cup \{\infty \})$-valued objective function given as a sum of fixed-arity funct…