License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.651
URN: urn:nbn:de:0030-drops-44956
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4495/
Go to the corresponding LIPIcs Volume Portal

Uppman, Hannes

Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains

pdf-format:
53.pdf (0.6 MB)

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 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.

BibTeX - Entry

@InProceedings{uppman:LIPIcs:2014:4495,
  author =	{Hannes Uppman},
  title =	{{Computational Complexity of the Extended Minimum Cost Homomorphism Problem on Three-Element Domains}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{651--662},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4495},
  URN =		{urn:nbn:de:0030-drops-44956},
  doi =		{10.4230/LIPIcs.STACS.2014.651},
  annote =	{Keywords: Complexity, Optimisation, Constraint Satisfaction}
}

Keywords: Complexity, Optimisation, Constraint Satisfaction
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI