Skip to main content

Research Repository

Advanced Search

Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights

Jonsson, P.; Krokhin, A.

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


Authors

P. Jonsson



Abstract

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.

Citation

Jonsson, P., & Krokhin, A. (2007). Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. Journal of Computer and System Sciences, 73(5), 691-702. https://doi.org/10.1016/j.jcss.2007.02.001

Journal Article Type Article
Publication Date Aug 1, 2007
Deposit Date Mar 26, 2010
Publicly Available Date Mar 28, 2024
Journal Journal of Computer and System Sciences
Print ISSN 0022-0000
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 73
Issue 5
Pages 691-702
DOI https://doi.org/10.1016/j.jcss.2007.02.001
Keywords Maximum constraint satisfaction problem, Digraph H-colouring, Complexity, Dichotomy

Files





You might also like



Downloadable Citations