Vladimir Deineko ; Peter Jonsson ; Mikael Klasson ; Andrei Krokhin - Supermodularity on chains and complexity of maximum constraint satisfaction

dmtcs:3420 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3420
Supermodularity on chains and complexity of maximum constraint satisfactionArticle

Authors: Vladimir Deineko 1; Peter Jonsson 2; Mikael Klasson 2; Andrei Krokhin 3

  • 1 Warwick Business School
  • 2 Department of Computer and Information Science - Linköping University
  • 3 School of Engineering and Computing Sciences

In the maximum constraint satisfaction problem ($\mathrm{Max \; CSP}$), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximise the number (or the total weight) of satisfied constraints. This problem is $\mathrm{NP}$-hard in general so it is natural to study how restricting the allowed types of constraints affects the complexity of the problem. In this paper, we show that any $\mathrm{Max \; CSP}$ problem with a finite set of allowed constraint types, which includes all constants (i.e. constraints of the form $x=a$), is either solvable in polynomial time or is $\mathrm{NP}$-complete. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known combinatorial property of supermodularity.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: maximum constraint satisfaction,complexity,supermodularity,Monge properties,digraph $H$-colouring,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 176 times.
This article's PDF has been downloaded 184 times.