Computational complexity of the extended minimum cost homomorphism problem on three-element domains

DOI10.4230/LIPICS.STACS.2014.651zbMATH Open1359.68145arXiv1308.1394OpenAlexW2963464830MaRDI QIDQ2965524FDOQ2965524

Authors: Hannes Uppman 

Publication date: 3 March 2017

Abstract: 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 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. 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 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 Thapper and Zivny [STOC'13]. However, understanding the complexity of languages that are not finite-valued appears to be more difficult. 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 Min-Sol, Uppman [ICALP'13], takes a step in this direction. In this paper we extend this result considerably by determining the complexity of three-element Min-Cost-Hom.

Full work available at URL: https://arxiv.org/abs/1308.1394

Recommendations

• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• Extensions of the minimum cost homomorphism problem
• A dichotomy theorem for the general minimum cost homomorphism problem
• The complexity of conservative valued CSPs
• The dichotomy of minimum cost homomorphism problems for digraphs

zbMATH Keywords

optimisationcomplexityconstraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Cited In (7)

• Title not available (Why is that?)
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• Binarisation for valued constraint satisfaction problems
• The complexity of general-valued CSPs
• Necessary conditions for tractability of valued CSPs
• The complexity of valued CSPs
• Extensions of the minimum cost homomorphism problem

This page was built for publication: Computational complexity of the extended minimum cost homomorphism problem on three-element domains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965524)