### Abstract

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 language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Pages | 328-337 |

Number of pages | 10 |

Volume | 6196 LNCS |

DOIs | |

Publication status | Published - 2010 |

Externally published | Yes |

Event | 16th Annual International Computing and Combinatorics Conference, COCOON 2010 - Nha Trang, Viet Nam Duration: Jul 19 2010 → Jul 21 2010 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6196 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 16th Annual International Computing and Combinatorics Conference, COCOON 2010 |
---|---|

Country | Viet Nam |

City | Nha Trang |

Period | 7/19/10 → 7/21/10 |

### Fingerprint

### ASJC Scopus subject areas

- Computer Science(all)
- Theoretical Computer Science

### Cite this

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 6196 LNCS, pp. 328-337). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6196 LNCS). https://doi.org/10.1007/978-3-642-14031-0_36

**Extensions of the minimum cost homomorphism problem.** / Takhanov, Rustem.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).*vol. 6196 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6196 LNCS, pp. 328-337, 16th Annual International Computing and Combinatorics Conference, COCOON 2010, Nha Trang, Viet Nam, 7/19/10. https://doi.org/10.1007/978-3-642-14031-0_36

}

TY - GEN

T1 - Extensions of the minimum cost homomorphism problem

AU - Takhanov, Rustem

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955018422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955018422&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14031-0_36

DO - 10.1007/978-3-642-14031-0_36

M3 - Conference contribution

SN - 3642140300

SN - 9783642140303

VL - 6196 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 328

EP - 337

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -