We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.

Jonsson, P. and Krokhin, A. (2007) 'Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.', Journal of computer and system sciences., 73 (5). pp. 691-702.


In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of positive-weight constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so that the total weight of satisfied constraints is maximized. We consider this problem and its variant Max AW CSP where the weights are allowed to be both positive and negative, and study how the complexity of the problems depends on the allowed constraint types. We prove that Max AW CSP over an arbitrary finite domain exhibits a dichotomy: it is either polynomial-time solvable or NP-hard. Our proof builds on two results that may be of independent interest: one is that the problem of finding a maximum H-colourable subdigraph in a given digraph is either NP-hard or trivial depending on H, and the other a dichotomy result for Max CSP with a single allowed constraint type.

Item Type:Article
Keywords:Maximum constraint satisfaction problem, Digraph H-colouring, Complexity, Dichotomy
Full text:(VoR) Version of Record
Download PDF
Publisher Web site:
Date accepted:No date available
Date deposited:06 April 2010
Date of first online publication:August 2007
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar