×

Minimum cost homomorphisms to reflexive digraphs. (English) Zbl 1136.68462

Laber, Eduardo Sany (ed.) et al., LATIN 2008: Theoretical informatics. 8th Latin American symposium, Búzios, Brazil, April 7–11, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-78772-3/pbk). Lecture Notes in Computer Science 4957, 182-193 (2008).
Summary: For a fixed digraph \(H\), the minimum cost homomorphism problem, MinHOM\((H)\), asks whether an input digraph \(G\), with given costs \(c _{i }(u), u \in V(G), i \in V(H)\), and an integer \(k\), admits a homomorphism to \(H\) of total cost not exceeding \(k\).
Minimum cost homomorphism problems encompass many well studied optimization problems such as list homomorphism problems, retraction and precolouring extension problems, chromatic partition optimization, and applied problems in repair analysis.
For undirected graphs the complexity of the problem, as a function of the parameter \(H\), is well understood; for digraphs, the situation appears to be more complex, and only partial results are known. We focus on the minimum cost homomorphism problem for reflexive digraphs \(H\). It is known that MinHOM\((H)\) is polynomial if \(H\) has a Min-Max ordering. We prove that for any other reflexive digraph \(H\), the problem MinHOM\((H)\) is NP-complete. (This was earlier conjectured by Gutin and Kim.) Apart from undirected graphs, this is the first general class of digraphs for which such a dichotomy has been proved. Our proof involves a forbidden induced subgraph characterization of reflexive digraphs with a Min-Max ordering, and implies a polynomial test for the existence of a Min-Max ordering in a reflexive digraph \(H\).
For the entire collection see [Zbl 1133.68008].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alekseev, V. E.; Lozin, V. V., Independent sets of maximum weight in (p,q)-colorable graphs, Discrete Mathematics, 265, 351-356 (2003) · Zbl 1034.05020
[2] Bang-Jensen, J.; Gutin, G., Digraphs: Theory, Algorithms and Applications (2000), London: Springer, London
[3] Brewster, R. C.; Hell, P., Homomorphisms to powers of digraphs, Discrete Mathematics, 244, 31-41 (2002) · Zbl 0994.05071
[4] 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
[5] Feder, T., Homomorphisms to oriented cycles and k-partite satisfiability, SIAM J. Discrete Math, 14, 471-480 (2001) · Zbl 0982.05097
[6] 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
[7] Feder, T.; Hell, P.; Tucker-Nally, K., Digraph matrix partitions and trigraph homomorphisms, Discrete Applied Mathematics, 154, 2458-2469 (2006) · Zbl 1106.05060
[8] Feder, T., Hell, P., Huang, J.: List homomorphisms to reflexive digraphs (manuscript, 2005) · Zbl 1236.05092
[9] Feder, T., Classification of Homomorphisms to Oriented Cycles and k-Partite Satisfiability, SIAM Journal on Discrete Mathematics, 14, 471-480 (2001) · Zbl 0982.05097
[10] Gutin, G., Kim, E.J.: Complexity of the minimum cost homomorphism problem for semicomplete digraphs with possible loops (submitted) · Zbl 1225.05113
[11] Gutin, G., Kim, E.J.: Introduction to the minimum cost homomorphism problem for directed and undirected graphs. Lecture Notes of the Ramanujan Math. Society (to appear) · Zbl 1189.90179
[12] Gutin, G., Kim, E.J.: On the complexity of the minimum cost homomorphism problem for reflexive multipartite tournaments (submitted)
[13] Gutin, G.; Rafiey, A.; Yeo, A., Minimum Cost and List Homomorphisms to Semicomplete Digraphs, Discrete Appl. Math., 154, 890-897 (2006) · Zbl 1138.05032
[14] Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs. Discrete Applied Math. (submitted) · Zbl 1144.05034
[15] Gutin, G., Rafiey, A., Yeo, A.: Minimum Cost Homomorphisms to Semicomplete Bipartite Digraphs (submitted) · Zbl 1184.05042
[16] Gutin, G.; Rafiey, A.; Yeo, A.; Tso, M., Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Appl. Math., 154, 881-889 (2006) · Zbl 1131.90020
[17] Gutin, G., Hell, P., Rafiey, A., Yeo, A.: A dichotomy for minimum cost graph homomorphisms. European J. Combin. (to appear) · Zbl 1149.90164
[18] Halldórsson, M. M.; Kortsarz, G.; Shachnai, H.; Goemans, M. X.; Jansen, K.; Rolim, J. D.P.; Trevisan, L., Minimizing average completion of dedicated tasks and interval graphs, Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, 114-126 (2001), Heidelberg: Springer, Heidelberg · Zbl 0998.68508
[19] Hell, P., Algorithmic aspects of graph homomorphisms, Survey in Combinatorics 2003, London Math. Soc., 239-276 (2003), Cambridge: Cambridge University Press, Cambridge · 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: Oxford University Press, Oxford · Zbl 1062.05139
[22] Hell, P.; Huang, J., Interval bigraphs and circular arc graphs, J. Graph Theory, 46, 313-327 (2004) · Zbl 1046.05066
[23] Hell, P.; Nešetřil, J.; Zhu, X., Complexity of Tree Homomorphisms, Discrete Applied Mathematics, 70, 23-36 (1996) · Zbl 0868.05018
[24] Jansen, K., Approximation results for the optimum cost chromatic partition problem, J. Algorithms, 34, 54-89 (2000) · Zbl 0947.68164
[25] Jiang, T.; West, D. B., Coloring of trees with minimum sum of colors, J. Graph Theory, 32, 354-358 (1999) · Zbl 0939.05037
[26] Khanna, S.; Sudan, M.; Trevisan, L.; Williamson, D., The approximability of constraint satisfaction problems, SIAM Journal on Computing, 30, 1863-1920 (2000) · Zbl 0992.68059
[27] Kroon, L. G.; Sen, A.; Deng, H.; Roy, A.; D’Amore, F.; Marchetti-Spaccamela, A.; Franciosa, P. G., The optimal cost chromatic partition problem for trees and interval graphs, Graph-Theoretic Concepts in Computer Science, 279-292 (1997), Heidelberg: Springer, Heidelberg
[28] Lovász, L., Three short proofs in graph theory, J. Combin. Theory, Ser. B, 19, 269-271 (1975) · Zbl 0322.05142
[29] Supowit, K., Finding a maximum planar subset of a set of nets in a channel, IEEE Trans. Computer-Aided Design, 6, 93-94 (1987)
[30] Wegner, G.: Eigenschaften der nerven homologische-einfactor familien in R^n, Ph.D. Thesis, Universität Gottigen, Gottigen, Germany (1967)
[31] West, D., Introduction to Graph Theory (1996), Upper Saddle River: Prentice Hall, Upper Saddle River · Zbl 0845.05001
[32] Zhou, H., Characterization of the homomorphic preimages of certain oriented cycles, SIAM Journal on Discrete Mathematics, 6, 87-99 (1993) · Zbl 0788.05079
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.