Hell, Pavol; Mishra, Aurosish \(H\)-coloring degree-bounded (acyclic) digraphs. (English) Zbl 1382.68112 Theor. Comput. Sci. 554, 40-49 (2014). Summary: An NP-complete coloring or homomorphism problem may become polynomial time solvable when restricted to graphs with degrees bounded by a small number, but remain NP-complete if the bound is higher. We investigate an analogous phenomenon for digraphs, focusing on the three smallest digraphs \(H\) with NP-complete \(H\)-colorability problems. It turns out that in all three cases the \(H\)-coloring problem is polynomial time solvable for digraphs with in-degrees at most 1, regardless of the out-degree bound (respectively with out-degrees at most 1, regardless of the in-degree bound). On the other hand, as soon as both in- and out-degrees are bounded by constants greater than or equal to 2, all three problems are again NP-complete. Interestingly, the situation changes when we further restrict the inputs to be acyclic digraphs. In two of the three cases the NP-complete problems remain NP-complete. In the third case, the \(H\)-coloring problem turns out to be polynomial time solvable for acyclic digraphs with in-degrees at most 2, regardless of the out-degree bound (respectively with out-degrees at most 2, regardless of the in-degree bound). We also show that in this case as soon as both in- and out-degrees are bounded by constants greater than or equal to 3, the \(H\)-coloring problem is once again NP-complete, even for acyclic digraphs. A conjecture proposed for graphs \(H\) by Feder, Hell and Huang states that any variant of the \(H\)-coloring problem which is NP-complete without degree constraints is also NP-complete with degree constraints, provided the degree bounds are high enough. It has been verified for \(H\)-coloring of digraphs, but the degree bounds are quite high, and are stated in terms of the sum of in- and out-degrees. Our results confirm the conjecture with the best possible bounds that are needed for NP-completeness; moreover, they underscore the fact that the bound must apply separately to both the in-degrees and the out-degrees. MSC: 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs 05C20 Directed graphs (digraphs), tournaments 05C85 Graph algorithms (graph-theoretic aspects) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) Keywords:coloring; homomorphism; acyclic digraph; degree-bounded digraph PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Mishra}, Theor. Comput. Sci. 554, 40--49 (2014; Zbl 1382.68112) Full Text: DOI References: [1] Bang-Jensen, Jørgen; Hell, Pavol; MacGillivray, Gary, The complexity of colouring by semicomplete digraphs, SIAM J. Discrete Math., 1, 3, 281-298 (August 1988) [2] Barto, Libor; Kozik, Marcin; Niven, Todd, Graphs, polymorphisms and the complexity of homomorphism problems, (Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC ’08 (2008), ACM: ACM New York, NY, USA), 789-796 · Zbl 1231.68148 [3] Brooks, R. L., On coloring the nodes of a network, Math. Proc. Cambridge Philos. Soc., 37, 194-197 (1941) · Zbl 0027.26403 [4] Emden-Weinert, Thomas; Hougardy, Stefan; Kreuter, Bernd, Uniquely colourable graphs and the hardness of colouring graphs of large girth, Combin. Probab. Comput., 7, 4, 375-386 (1998) · Zbl 0918.05051 [5] Feder, Tomás; Hell, Pavol; Huang, Jing, List homomorphisms of graphs with bounded degrees, Discrete Math., 307, 3-5, 386-392 (2007) · Zbl 1111.05035 [6] Feder, Tomás; Vardi, Moshe Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 1, 57-104 (February 1999) [7] Galluccio, A.; Hell, P.; Nešetřil, J., The complexity of h-colouring of bounded degree graphs, Discrete Math., 222, 101-109 (1998) · Zbl 0956.05036 [8] Garey, Michael R.; Johnson, David S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1990), W. H. Freeman & Co.: W. H. Freeman & Co. New York, NY, USA · Zbl 0411.68039 [9] Häggkvist, R.; Hell, P., Universality of \(a\)-mote graphs, European J. Combin., 14, 23-27 (1993) · Zbl 0799.05063 [10] Hell, P.; Nešetřil, J., Counting list homomorphisms and graphs with bounded degrees, (Graphs, Morphisms and Statistical Physics. Graphs, Morphisms and Statistical Physics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 63 (2004)), 105-112 · Zbl 1059.05049 [11] Hell, P.; Zhu, X., Duality and polynomial testing of tree homomorphisms, Trans. Amer. Math. Soc., 348, 1281-1297 (1996) · Zbl 0877.05055 [12] Hell, Pavol; Mishra, Aurosish, Small h-coloring problems for bounded degree digraphs, (Computing and Combinatorics. Computing and Combinatorics, Lecture Notes in Computer Science, vol. 7936 (2013), Springer: Springer Berlin, Heidelberg), 579-590 · Zbl 1382.68111 [13] Hell, Pavol; Nešetřil, Jaroslav, On the complexity of H-coloring, J. Combin. Theory Ser. B, 48, 1, 92-110 (February 1990) [14] Hell, Pavol; Nešetřil, Jaroslav, Graphs and Homomorphisms (2004), Oxford University Press · Zbl 1062.05139 [15] Hell, Pavol; Nešetřil, Jaroslav, Colouring, constraint satisfaction, and complexity, Comput. Sci. Rev., 2, 143-163 (2008) · Zbl 1302.68251 [16] Holyer, Ian, The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034 [17] Jeavons, Peter, On the algebraic structure of combinatorial problems, Theoret. Comput. Sci., 200, 185-204 (1998) · Zbl 0915.68074 [18] Jonsson, Peter; Krokhin, Andrei; Kuivinen, Fredrik, Hard constraint satisfaction problems have hard gaps at location 1, Theoret. Comput. Sci., 410, 38-40, 3856-3874 (2009) · Zbl 1176.90498 [19] Mackworth, Alan K., Consistency in networks of relations, Artificial Intelligence, 8, 1, 99-118 (1977) · Zbl 0341.68061 [20] Maurer, H. A.; Sudborough, J. H.; Welzl, E., On the complexity of the general coloring problem, Inf. Control, 51, 2, 128-145 (1981) · Zbl 0502.68015 [21] Molloy, Michael; Reed, Bruce, Colouring graphs when the number of colours is almost the maximum degree, (Proceedings of the 33rd ACM Symposium on Theory of Computing, vol. 462 (2001)), 470 · Zbl 1323.05052 [22] Nešetřil, Jaroslav; Siggers, Mark H.; Zádori, László, A combinatorial constraint satisfaction problem dichotomy classification conjecture, European J. Combin., 31, 1, 280-296 (January 2010) [23] Nešetřil, Jaroslav; Siggers, Mark, Combinatorial proof that subprojective constraint satisfaction problems are NP-complete, (Mathematical Foundations of Computer Science 2007. Mathematical Foundations of Computer Science 2007, Lecture Notes in Computer Science, vol. 4708 (2007), Springer: Springer Berlin, Heidelberg), 159-170 · Zbl 1147.68530 [24] Siggers, Mark H., Dichotomy for bounded degree H-coloring, Discrete Appl. Math., 157, 2, 201-210 (January 2009) 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.