A dichotomy theorem for the general minimum cost homomorphism problem

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

36 Citations (Scopus)

Abstract

In the constraint satisfaction problem (CSP), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (MinHom), one is additionally given weights cva for every variable v and value a, and the aim is to find an assignment f to the variables that minimizes Σv c vf(v). Let MinHom(Γ) denote the MinHom problem parameterized by the set of predicates allowed for constraints. MinHom (Γ) is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that MinHom(Γ) can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of MinHom (Γ) for all choices of Γ. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].

Original languageEnglish
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
Pages657-668
Number of pages12
Volume5
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 - Nancy, France
Duration: Mar 4 2010Mar 6 2010

Other

Other27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
CountryFrance
CityNancy
Period3/4/103/6/10

Fingerprint

Costs
Constraint satisfaction problems
Directed graphs
Combinatorial optimization
Learning systems
Logistics
Computational complexity
Concretes

Keywords

  • Constraint satisfaction problem
  • Minimum cost homomorphisms problem
  • Perfect graphs
  • Relational clones
  • Supervised learning

ASJC Scopus subject areas

  • Software

Cite this

Takhanov, R. (2010). A dichotomy theorem for the general minimum cost homomorphism problem. In Leibniz International Proceedings in Informatics, LIPIcs (Vol. 5, pp. 657-668) https://doi.org/10.4230/LIPIcs.STACS.2010.2493

A dichotomy theorem for the general minimum cost homomorphism problem. / Takhanov, Rustem.

Leibniz International Proceedings in Informatics, LIPIcs. Vol. 5 2010. p. 657-668.

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

Takhanov, R 2010, A dichotomy theorem for the general minimum cost homomorphism problem. in Leibniz International Proceedings in Informatics, LIPIcs. vol. 5, pp. 657-668, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, 3/4/10. https://doi.org/10.4230/LIPIcs.STACS.2010.2493
Takhanov R. A dichotomy theorem for the general minimum cost homomorphism problem. In Leibniz International Proceedings in Informatics, LIPIcs. Vol. 5. 2010. p. 657-668 https://doi.org/10.4230/LIPIcs.STACS.2010.2493
Takhanov, Rustem. / A dichotomy theorem for the general minimum cost homomorphism problem. Leibniz International Proceedings in Informatics, LIPIcs. Vol. 5 2010. pp. 657-668
@inproceedings{84a7e12a858c4c24b65ce21e07cd3cd7,
title = "A dichotomy theorem for the general minimum cost homomorphism problem",
abstract = "In the constraint satisfaction problem (CSP), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (MinHom), one is additionally given weights cva for every variable v and value a, and the aim is to find an assignment f to the variables that minimizes Σv c vf(v). Let MinHom(Γ) denote the MinHom problem parameterized by the set of predicates allowed for constraints. MinHom (Γ) is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that MinHom(Γ) can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of MinHom (Γ) for all choices of Γ. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].",
keywords = "Constraint satisfaction problem, Minimum cost homomorphisms problem, Perfect graphs, Relational clones, Supervised learning",
author = "Rustem Takhanov",
year = "2010",
doi = "10.4230/LIPIcs.STACS.2010.2493",
language = "English",
isbn = "9783939897163",
volume = "5",
pages = "657--668",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",

}

TY - GEN

T1 - A dichotomy theorem for the general minimum cost homomorphism problem

AU - Takhanov, Rustem

PY - 2010

Y1 - 2010

N2 - In the constraint satisfaction problem (CSP), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (MinHom), one is additionally given weights cva for every variable v and value a, and the aim is to find an assignment f to the variables that minimizes Σv c vf(v). Let MinHom(Γ) denote the MinHom problem parameterized by the set of predicates allowed for constraints. MinHom (Γ) is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that MinHom(Γ) can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of MinHom (Γ) for all choices of Γ. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].

AB - In the constraint satisfaction problem (CSP), the aim is to find an assignment of values to a set of variables subject to specified constraints. In the minimum cost homomorphism problem (MinHom), one is additionally given weights cva for every variable v and value a, and the aim is to find an assignment f to the variables that minimizes Σv c vf(v). Let MinHom(Γ) denote the MinHom problem parameterized by the set of predicates allowed for constraints. MinHom (Γ) is related to many well-studied combinatorial optimization problems, and concrete applications can be found in, for instance, defence logistics and machine learning. We show that MinHom(Γ) can be studied by using algebraic methods similar to those used for CSPs. With the aid of algebraic techniques, we classify the computational complexity of MinHom (Γ) for all choices of Γ. Our result settles a general dichotomy conjecture previously resolved only for certain classes of directed graphs, [Gutin, Hell, Rafiey, Yeo, European J. of Combinatorics, 2008].

KW - Constraint satisfaction problem

KW - Minimum cost homomorphisms problem

KW - Perfect graphs

KW - Relational clones

KW - Supervised learning

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

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

U2 - 10.4230/LIPIcs.STACS.2010.2493

DO - 10.4230/LIPIcs.STACS.2010.2493

M3 - Conference contribution

SN - 9783939897163

VL - 5

SP - 657

EP - 668

BT - Leibniz International Proceedings in Informatics, LIPIcs

ER -