Skew bisubmodularity and valued CSPs

Anna Huber, Andrei Krokhin, Robert Powell

Research output: Contribution to journalArticleResearchpeer-review

19 Citations (Scopus)

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 (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 ≠ 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 Ž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 languageEnglish
Pages (from-to)1064-1084
Number of pages21
JournalSIAM Journal on Computing
Volume43
Issue number3
DOIs
Publication statusPublished - 8 May 2014

Fingerprint

Skew
Constraint satisfaction problems
Constraint Satisfaction Problem
Submodularity
Max-cut
Max-cut Problem
Submodular Function
NP-hard Problems
Set theory
Linear programming
Finite Set
Assignment
Express
Minimise
Imply
Subset

Cite this

Huber, Anna ; Krokhin, Andrei ; Powell, Robert. / Skew bisubmodularity and valued CSPs. In: SIAM Journal on Computing. 2014 ; Vol. 43, No. 3. pp. 1064-1084.
@article{ca9307be150642e4b00462450c80566d,
title = "Skew bisubmodularity and valued CSPs",
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 (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 ≠ 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 Ž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.",
author = "Anna Huber and Andrei Krokhin and Robert Powell",
year = "2014",
month = "5",
day = "8",
doi = "10.1137/120893549",
language = "English",
volume = "43",
pages = "1064--1084",
journal = "SIAM Journal on Computing",
issn = "1095-7111",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Huber, A, Krokhin, A & Powell, R 2014, 'Skew bisubmodularity and valued CSPs', SIAM Journal on Computing, vol. 43, no. 3, pp. 1064-1084. https://doi.org/10.1137/120893549

Skew bisubmodularity and valued CSPs. / Huber, Anna; Krokhin, Andrei; Powell, Robert.

In: SIAM Journal on Computing, Vol. 43, No. 3, 08.05.2014, p. 1064-1084.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Skew bisubmodularity and valued CSPs

AU - Huber, Anna

AU - Krokhin, Andrei

AU - Powell, Robert

PY - 2014/5/8

Y1 - 2014/5/8

N2 - 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 ≠ 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 Ž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.

AB - 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 ≠ 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 Ž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.

UR - http://www.scopus.com/inward/record.url?scp=84904798513&partnerID=8YFLogxK

U2 - 10.1137/120893549

DO - 10.1137/120893549

M3 - Article

VL - 43

SP - 1064

EP - 1084

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 1095-7111

IS - 3

ER -