Minimum cost homomorphisms with constrained costs

DOI10.1007/978-3-319-42634-1_16MaRDI QIDQ2817862zbMATH OpenOpenAlexFDO

Authors Mayssam Mohammadi Nevisi, Pavol Hell

Publication date 2 September 2016

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

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

zbMATH Keywords

NP-completenessdichotomyhomomorphisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Minimum cost homomorphism problems can be viewed as a generalization of list homomorphism problems. They also extend two well-known graph colouring problems: the minimum colour sum problem and the optimum cost chromatic partition problem. In both of these problems, the cost function meets an additional constraint: the cost of using a specific colour is the same for every vertex of the input graph. We study minimum cost homomorphism problems with cost functions constrained to have this property. Clearly, when the standard minimum cost homomorphism problem is polynomial, then the problem with constrained costs is also polynomial. We expect that the same may hold for the cases when the standard minimum cost homomorphism problem is NP-complete. We prove that this is the case for trees $H$: we obtain a dichotomy of minimum constrained cost homomorphism problems which coincides with the dichotomy of standard minimum cost homomorphism problems. For general graphs $H$, we prove a partial dichotomy: the problem is polynomial if $H$ is a proper interval graph and NP-complete when $H$ is not chordal bipartite.

Recommendations

• A dichotomy for minimum cost graph homomorphisms
• Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs
• The dichotomy of minimum cost homomorphism problems for digraphs
• Minimum Cost Homomorphisms to Reflexive Digraphs
• Minimum cost homomorphisms to semicomplete multipartite digraphs

Cites work

• A dichotomy for minimum cost graph homomorphisms
• A dichotomy theorem for the general minimum cost homomorphism problem
• Bipartite permutation graphs
• Bi‐arc graphs and the complexity of list homomorphisms
• Classifying the Complexity of Constraints Using Finite Algebras
• Complexity of conservative constraint satisfaction problems
• Independent sets of maximum weight in (\(p,q\))-colorable graphs.
• Interval bigraphs and circular arc graphs
• Level of repair analysis and minimum cost homomorphisms of graphs
• List homomorphisms and circular arc graphs
• List homomorphisms to reflexive graphs
• Minimum Color Sum of Bipartite Graphs
• On the complexity of H-coloring
• Recognizing interval digraphs and interval bigraphs in polynomial time
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of conservative valued CSPs
• The dichotomy of list homomorphisms for digraphs
• The dichotomy of minimum cost homomorphism problems for digraphs

Cited in

(4)

• A dichotomy theorem for the general minimum cost homomorphism problem
• The Maximum Solution Problem on Graphs
• Extensions of the minimum cost homomorphism problem
• Approximation of minimum cost homomorphisms

This page was built for publication: Minimum cost homomorphisms with constrained costs

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