Extensions of the minimum cost homomorphism problem

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

9 Citations (Scopus)

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 languageEnglish
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages328-337
Number of pages10
Volume6196 LNCS
DOIs
Publication statusPublished - 2010
Externally publishedYes
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)03029743
ISSN (Electronic)16113349

Other

Other16th Annual International Computing and Combinatorics Conference, COCOON 2010
CountryViet Nam
CityNha Trang
Period7/19/107/21/10

Fingerprint

Homomorphism
Costs
Dichotomy
Polynomials
Finite Set
Optimization Problem
Parameterise
Unary
Natural number
Expand
Polynomial time
Fragment
NP-complete problem
Language
Restriction
Arbitrary

ASJC Scopus subject areas

  • Computer Science(all)
  • Theoretical Computer Science

Cite this

Takhanov, R. (2010). Extensions of the minimum cost homomorphism problem. In 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.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6196 LNCS 2010. p. 328-337 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6196 LNCS).

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

Takhanov, R 2010, Extensions of the minimum cost homomorphism problem. in 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
Takhanov R. Extensions of the minimum cost homomorphism problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6196 LNCS. 2010. p. 328-337. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-14031-0_36
Takhanov, Rustem. / Extensions of the minimum cost homomorphism problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6196 LNCS 2010. pp. 328-337 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1a6c4cd84a114795ae89e1842c187dc3,
title = "Extensions of the minimum cost homomorphism problem",
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.",
author = "Rustem Takhanov",
year = "2010",
doi = "10.1007/978-3-642-14031-0_36",
language = "English",
isbn = "3642140300",
volume = "6196 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "328--337",
booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

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 -