Minimum cost homomorphisms with constrained costs

DOI10.1007/978-3-319-42634-1_16zbMATH Open1476.68110arXiv1602.07827OpenAlexW2963834637MaRDI QIDQ2817862FDOQ2817862

Authors: Mayssam Mohammadi Nevisi, Pavol Hell 

Publication date: 2 September 2016

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

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)