10.4230/LIPICS.STACS.2010.2493
Takhanov, Rustem
Rustem
Takhanov
A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Minimum cost homomorphisms problem
relational clones
constraint satisfaction problem
perfect graphs
supervised learning
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
2010
2010-03-09
2010-03-09
2010-03-09
en
urn:nbn:de:0030-drops-24936
10.4230/LIPIcs.STACS.2010
978-3-939897-16-3
1868-8969
10.4230/LIPIcs.STACS.2010
LIPIcs, Volume 5, STACS 2010
27th International Symposium on Theoretical Aspects of Computer Science
2013
5
57
657
668
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Marion, Jean-Yves
Jean-Yves
Marion
Schwentick, Thomas
Thomas
Schwentick
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
5
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
319667 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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 $\sum_{v} c_{vf(v)}$. Let $MinHom\left( \Gamma \right)$ denote the $MinHom$ problem parameterized by the set of predicates allowed for constraints. $MinHom\left( \Gamma \right)$ 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\left( \Gamma \right)$ 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\left( \Gamma \right)$ for all choices of $\Gamma$. 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].
LIPIcs, Vol. 5, 27th International Symposium on Theoretical Aspects of Computer Science, pages 657-668