Extensions of the minimum cost homomorphism problem

DOI10.1007/978-3-642-14031-0_36MaRDI QIDQ3578332zbMATH OpenOpenAlexFDO

Authors Rustem Takhanov

Publication date 20 July 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Assume $D$ is a finite set and $R$ is a finite set of functions from $D$ to the natural numbers. An instance of the minimum $R$-cost homomorphism problem ($MinHo{m}_R$) is a set of variables $V$ subject to specified constraints together with a positive weight $c_{vr}$ for each combination of $vinV$ and $rinR$. The aim is to find a function $f:VightarrowD$ such that $f$ satisfies all constraints and $su{m}_{vinV}su{m}_{rinR}{c}_{vr}r(f(v))$ is minimized. This problem unifies well-known optimization problems such as the minimum cost homomorphism problem and the maximum solution problem, and this makes it a computationally interesting fragment of the valued CSP framework for optimization problems. We parameterize $MinHo{m}_{R}left(Gammaight)$ by {em constraint languages}, i.e. sets $Gamma$ of relations that are allowed in constraints. A constraint language is called {em conservative} if every unary relation is a member of it; such constraint languages play an important role in understanding the structure of constraint problems. The dichotomy conjecture for $MinHo{m}_R$ is the following statement: if $Gamma$ is a constraint language, then $MinHo{m}_{R}left(Gammaight)$ is either polynomial-time solvable or NP-complete. For $MinHom$ the dichotomy result has been recently obtained [Takhanov, STACS, 2010] and the goal of this paper is to expand this result to the case of $MinHo{m}_R$ with conservative constraint language. For arbitrary $R$ this problem is still open, but assuming certain restrictions on $R$ we prove a dichotomy. As a consequence of this result we obtain a dichotomy for the conservative maximum solution problem.

Recommendations

• A dichotomy theorem for the general minimum cost homomorphism problem
• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• The dichotomy of minimum cost homomorphism problems for digraphs
• The complexity of conservative valued CSPs
• Minimum cost homomorphisms with constrained costs

Cited in

(10)

• Computational complexity of the extended minimum cost homomorphism problem on three-element domains
• A dichotomy theorem for the general minimum cost homomorphism problem
• Necessary conditions for tractability of valued CSPs
• The Maximum Solution Problem on Graphs
• scientific article; zbMATH DE number 5531978 (Why is no real title available?)
• The complexity of valued CSPs
• The Complexity of Three-Element Min-Sol and Conservative Min-Cost-Hom
• Binarisation for valued constraint satisfaction problems
• The complexity of conservative valued CSPs
• Combining unsupervised dimension reduction with sufficient dimension reduction

This page was built for publication: Extensions of the minimum cost homomorphism problem

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