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

Direct link
Extensions of the Minimum Cost Homomorphism Problem
Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory. Linköping University, The Institute of Technology. (TCSLAB)
2010 (English)In: Proceedings of the 16th Annual International Computing and Combinatorics    Conference, Berlin: Springer , 2010, 328-337 p.Conference paper (Refereed)
Abstract [en]

Assume D is a finite set and R is a finite set of functions from D to the natural numbers. An instance of the minimum R-cost homomorphism problem (MinHom R ) is a set of variables V subject to specified constraints together with a positive weight c vr for each combination of v ∈ V and r ∈ R. The aim is to find a function f:VD such that f satisfies all constraints and ∑  v ∈ V  ∑  r ∈ R c vr r(f(v)) is maximized.

This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize MinHom R by constraint languages, i.e. sets Γ of relations that are allowed in constraints. A constraint language is called conservative if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for MinHom R is the following statement: if Γ is a constraint language, then MinHom R is either polynomial-time solvable or NP-complete. For MinHom the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of MinHom R with conservative constraint language. For arbitrary R this problem is still open, but assuming certain restrictions on R we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem

Place, publisher, year, edition, pages
Berlin: Springer , 2010. 328-337 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 6196
National Category
Computer Science
URN: urn:nbn:se:liu:diva-63678DOI: 10.1007/978-3-642-14031-0_36ISBN: 978-3-642-14030-3 (print)ISBN: 978-3-642-14031-0 (online)OAI: diva2:382145
16th Annual International Computing and Combinatorics Conference, COCOON 2010; Nha Trang; Viet Nam
Available from: 2010-12-29 Created: 2010-12-29 Last updated: 2014-09-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Takhanov, Rustem
By organisation
TCSLAB - Theoretical Computer Science LaboratoryThe Institute of Technology
Computer Science

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: 15 hits
ReferencesLink to record
Permanent link

Direct link