liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
Department of Computer Science, University of Durham, Science Laboratories, South Road, Durham, DH1 3LE, United Kingdom.
2007 (English)In: Journal of computer and system sciences (Print), ISSN 0022-0000, Vol. 73, no 5, 691-702 p.Article in journal (Refereed) Published
Abstract [en]

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. © 2007 Elsevier Inc. All rights reserved.

Place, publisher, year, edition, pages
2007. Vol. 73, no 5, 691-702 p.
Keyword [en]
Complexity, Dichotomy, Digraph H-colouring, Maximum constraint satisfaction problem
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-49055DOI: 10.1016/j.jcss.2007.02.001OAI: diva2:269951
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-01-11

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
Journal of computer and system sciences (Print)
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link