### 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 c_{va} 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 language | English |
---|---|

Title of host publication | STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science |

Pages | 657-668 |

Number of pages | 12 |

DOIs | |

Publication status | Published - Dec 1 2010 |

Event | 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 - Nancy, France Duration: Mar 4 2010 → Mar 6 2010 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 5 |

ISSN (Print) | 1868-8969 |

### Other

Other | 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 |
---|---|

Country | France |

City | Nancy |

Period | 3/4/10 → 3/6/10 |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Software

### Cite this

*STACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science*(pp. 657-668). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 5). https://doi.org/10.4230/LIPIcs.STACS.2010.2493