Skip to main content

Research Repository

Advanced Search

Skew Bisubmodularity and Valued CSPs

Huber, A.; Krokhin, A.; Powell, R.

Skew Bisubmodularity and Valued CSPs Thumbnail


A. Huber

R. Powell


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 (rational-valued) 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}\neq{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 non--submodular function can be used to express, in a certain specific sense, the NP-hard 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 Živný, 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.


Huber, A., Krokhin, A., & Powell, R. (2014). Skew Bisubmodularity and Valued CSPs. SIAM Journal on Computing, 43(3), 1064-1084.

Journal Article Type Article
Acceptance Date Jan 21, 2014
Online Publication Date May 8, 2014
Publication Date May 8, 2014
Deposit Date May 29, 2014
Publicly Available Date May 30, 2014
Journal SIAM Journal on Computing
Print ISSN 0097-5397
Electronic ISSN 1095-7111
Publisher Society for Industrial and Applied Mathematics
Peer Reviewed Peer Reviewed
Volume 43
Issue 3
Pages 1064-1084


Published Journal Article (344 Kb)

Copyright Statement
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

You might also like

Downloadable Citations