Abstract
An instance of the (finite)valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of values, and a sum of (rationalvalued) functions, with each function depending on a subset of the variables. The goal is to find an assignment of values to the variables that minimizes the sum. We study (assuming that PTIME ≠ NP) how the complexity of this very general problem depends on the functions allowed in the instances. The case when the variables can take only two values was classified by Cohen et al.: essentially, submodular functions give rise to the only tractable case, and any nonsubmodular function can be used to express, in a certain specific sense, the NPhard Max Cut problem. We investigate the case when the variables can take three values. We identify a new infinite family of conditions that includes bisubmodularity as a special case and which can collectively be called skew bisubmodularity. By a recent result of Thapper and Živńy, this condition implies that the corresponding VCSP can be solved by linear programming. We prove that submodularity, with respect to a total order, and skew bisubmodularity give rise to the only tractable cases, and, in all other cases, again, Max Cut can be expressed. We also show that our characterization of tractable cases is tight; that is, none of the conditions can be omitted.
Original language  English 

Pages (fromto)  10641084 
Number of pages  21 
Journal  SIAM Journal on Computing 
Volume  43 
Issue number  3 
DOIs  
Publication status  Published  8 May 2014 
Fingerprint Dive into the research topics of 'Skew bisubmodularity and valued CSPs'. Together they form a unique fingerprint.
Profiles

Anna Huber
 Centre for Sustainable Engineering
 SCEDT Engineering  Senior Lecturer in Mathematics
Person: Academic