×

A dichotomy for minimum cost graph homomorphisms. (English) Zbl 1149.90164

Let \(G\) and \(H\) be two finite graphs with vertex sets \(V(G)\) and \(V(H)\), respectively. The authors consider graph homomorphisms \(f: G \to H\). Mapping a vertex \(u \in V(G)\) to a vertex \(i \in V(H)\) incurs a cost \(c_i(u)\). The minimum cost homomorphism problem consists in finding a homomorphism such that the sum of incurred costs is minimum. A graph where every vertex has a loop is called reflexive, a graph without loops is called irreflexive. The authors show that the minimum cost homomorphism problem is polynomial time solvable if each connected component of \(H\) is either a reflexive or an irreflexive proper interval graph. In all other cases the problem in NP-hard. This solves an open question raised in [G. Gutin, A. Rafiey, A. Yeo and M. Tso, Discrete Appl. Maths. 154, 890–897 (2006; Zbl 1138.05032)].

MSC:

90C35 Programming involving graphs or networks

Citations:

Zbl 1138.05032
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] G. Aggarwal, T. Feder, R. Motwani, A. Zhu, Channel assignment in wireless networks, and classification of minimum graph homomorphisms, 2005. Manuscript; G. Aggarwal, T. Feder, R. Motwani, A. Zhu, Channel assignment in wireless networks, and classification of minimum graph homomorphisms, 2005. Manuscript
[2] Alon, N.; Fernandez de la Vega, W.; Kannan, R.; Karpinski, M., Random sampling and approximation of MAX-CSP problems, J. Comput. Syst. Sci., 67, 212-243 (2003) · Zbl 1160.68537
[3] Alekseev, V. E.; Lozin, V. V., Independent sets of maximum weight in \((p, q)\)-colorable graphs, Discrete Math., 265, 351-356 (2003) · Zbl 1034.05020
[4] A.A. Bulatov, Tractable conservative constraint satisfaction problems, ACM Trans. Comput. Logic (in press); A.A. Bulatov, Tractable conservative constraint satisfaction problems, ACM Trans. Comput. Logic (in press) · Zbl 1351.68113
[5] Cohen, D.; Cooper, M.; Jeavons, P.; Krokhin, A., A maximal tractable class of soft constraints, J. Artif. Intell. Res., 22, 1-22 (2004) · Zbl 1080.68658
[6] Deng, X.; Hell, P.; Huang, J., Linear-time representation algorithms for proper circular arc graphs and proper interval graphs, SIAM J. Comput., 25, 390-403 (1996) · Zbl 0858.05094
[7] Feder, T.; Hell, P.; Huang, J., List homomorphisms and circular arc graphs, Combinatorica, 19, 487-505 (1999) · Zbl 0985.05048
[8] Feder, T.; Hell, P.; Huang, J., Bi-arc graphs and the complexity of list homomorphisms, J. Graph Theory, 42, 61-80 (2003) · Zbl 1057.05033
[9] Fujishige, S., Submodular Functions and Optimization (1991), North-Holland: North-Holland Amsterdam · Zbl 0728.90056
[10] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (2004), Elsevier: Elsevier Amsterdam · Zbl 1050.05002
[11] Gutin, G.; Rafiey, A.; Yeo, A., Minimum cost and list homomorphisms to semicomplete digraphs, Discrete Appl. Math., 154, 881-889 (2006) · Zbl 1131.90020
[12] G. Gutin, A. Rafiey, A. Yeo, Minimum cost homomorphisms to semicomplete multipartite digraphs, Discrete Appl. Math. (in press); G. Gutin, A. Rafiey, A. Yeo, Minimum cost homomorphisms to semicomplete multipartite digraphs, Discrete Appl. Math. (in press) · Zbl 1144.05034
[13] Gutin, G.; Rafiey, A.; Yeo, A.; Tso, M., Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., 154, 890-897 (2006) · Zbl 1138.05032
[14] G. Gutin, A. Rafiey, A. Yeo, Minimum cost homomorphisms to semicomplete bipartite digraphs (submitted for publication); G. Gutin, A. Rafiey, A. Yeo, Minimum cost homomorphisms to semicomplete bipartite digraphs (submitted for publication) · Zbl 1184.05042
[15] Gutjahr, W.; Welzl, E.; Woeginger, G., Polynomial graph-colorings, Discrete Appl. Math., 35, 29-45 (1992) · Zbl 0761.05040
[16] Halldorsson, M. M.; Kortsarz, G.; Shachnai, H., Minimizing average completion of dedicated tasks and interval graphs, (Approximation, Randomization, and Combinatorial Optimization (Berkeley, Calif, 2001). Approximation, Randomization, and Combinatorial Optimization (Berkeley, Calif, 2001), Lecture Notes in Computer Science, vol. 2129 (2001), Springer: Springer Berlin), 114-126 · Zbl 0998.68508
[17] Hell, P.; Huang, J., Certifying LexBFS recognition algorithms for proper inteval graphs and proper interval bigraphs, SIAM J. Discrete Math., 18, 554-570 (2005) · Zbl 1069.05056
[18] Hell, P.; Huang, J., Interval bigraphs and circular arc graphs, J. Graph Theory, 46, 313-327 (2004) · Zbl 1046.05066
[19] Hell, P., Algorithmic aspects of graph homomorphisms, (Survey in Combinatorics 2003. Survey in Combinatorics 2003, London Math. Soc. Lecture Note Series, vol. 307 (2003), Cambridge University Press), 239-276 · Zbl 1035.05089
[20] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory B, 48, 92-110 (1990) · Zbl 0639.05023
[21] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139
[22] Jansen, K., Approximation results for the optimum cost chromatic partition problem, J. Algorithms, 34, 54-89 (2000) · Zbl 0947.68164
[23] Jiang, T.; West, D. B., Coloring of trees with minimum sum of colors, J. Graph Theory, 32, 354-358 (1999) · Zbl 0939.05037
[24] Khanna, S.; Sudan, M.; Trevisan, L.; Williamson, D., The approximability of constraint satisfaction problems, SIAM J. Comput., 30, 1863-1920 (2000) · Zbl 0992.68059
[25] Kroon, L. G.; Sen, A.; Deng, H.; Roy, A., The optimal cost chromatic partition problem for trees and interval graphs, (Graph-Theoretic Concepts in Computer Science (Cadenabbia, 1996). Graph-Theoretic Concepts in Computer Science (Cadenabbia, 1996), Lecture Notes in Computer Science, vol. 1197 (1997), Springer: Springer Berlin), 279-292
[26] Lovasz, L., Three short proofs in graph theory, J. Combin. Theory Ser. B, 19, 269-271 (1975) · Zbl 0322.05142
[27] Schrijver, A., Combinatorial Optimization (2003), Springer · Zbl 0542.90067
[28] Spinrad, J. P.; Brandstaedt, A.; Stewart, L., Bipartite permutation graphs, Discrete Appl. Math., 18, 279-292 (1987) · Zbl 0628.05055
[29] Spinrad, J., Efficient Graph Representations (2003), AMS · Zbl 1033.05001
[30] Supowit, K., Finding a maximum planar subset of a set of nets in a channel, IEEE Trans. Computer-Aided Design, 6, 93-94 (1987)
[31] G. Wegner, Eigenschaften der nerven homologische-einfactor familien in \(R^n\); G. Wegner, Eigenschaften der nerven homologische-einfactor familien in \(R^n\)
[32] West, D., Introduction to Graph Theory (1996), Prentice Hall: Prentice Hall Upper Saddle River · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.