Extensions of the minimum cost homomorphism problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)


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:V →D 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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 16th Annual International Conference, COCOON 2010, Proceedings
Number of pages10
Publication statusPublished - 2010
Event16th Annual International Computing and Combinatorics Conference, COCOON 2010 - Nha Trang, Viet Nam
Duration: Jul 19 2010Jul 21 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6196 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other16th Annual International Computing and Combinatorics Conference, COCOON 2010
CountryViet Nam
CityNha Trang

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Extensions of the minimum cost homomorphism problem'. Together they form a unique fingerprint.

Cite this