The complexity of Boolean surjective general-valued CSPs - Fulla, P; Zivny, S (Schloss Dagstuhl, 2017)
Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity. In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classification of Boolean surjective VCSPs. The newly discovered tractable case has an interesting structure related to projections of downsets and upsets. Our work generalises the dichotomy for {0,infinity}-valued constraint languages corresponding to CSPs) obtained by Creignou and Hebrard, and the dichotomy for {0,1}-valued constraint languages (corresponding to Min-CSPs) obtained by Uppman.