2026-07-25T18:31:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4495 2024-03-06T10:35:08Z ddc:004 open_access

Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains Uppman, Hannes Complexity Optimisation Constraint Satisfaction In this paper we study the computational complexity of the extended minimum cost homomorphism problem (Min-Cost-Hom) as a function of a constraint language, i.e. a set of constraint relations and cost functions that are allowed to appear in instances. A wide range of natural combinatorial optimisation problems can be expressed as extended Min-Cost-Homs and a classification of their complexity would be highly desirable, both from a direct, applied point of view as well as from a theoretical perspective. The extended Min-Cost-Hom can be understood either as a flexible optimisation version of the constraint satisfaction problem (CSP) or a restriction of the (general-valued) valued constraint satisfaction problem (VCSP). Other optimisation versions of CSPs such as the minimum solution problem (Min-Sol) and the minimum ones problem (Min-Ones) are special cases of the extended Min-Cost-Hom. The study of VCSPs has recently seen remarkable progress. A complete classification for the complexity of finite-valued languages on arbitrary finite domains has been obtained in [Thapper and Zivny, STOC'13]. However, understanding the complexity of languages that are not finite-valued appears to be more difficult. The extended Min-Cost-Hom allows us to study problematic languages of this type without having to deal with with the full generality of the VCSP. A recent classification for the complexity of three-element by Min-Sol [Uppman, ICALP'13], takes a step in this direction. In this paper we generalise this result considerably by determining the complexity of three-element extended Min-Cost-Hom. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hannes Uppman 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.651 urn:nbn:de:0030-drops-44956 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.651 eng https://creativecommons.org/licenses/by/3.0/legalcode