. . "The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)" . "21"^^ . . . "000264353000006" . "Barto, Libor" . "Bang-Jensen and Hell conjectured in 1990 (using the language of graph homomorphisms) a constraint satisfaction problem (CSP) dichotomy for digraphs with no sources or sinks. The conjecture states that the CSP for such a digraph is tractable if each component of its core is a cycle and is NP-complete otherwise. In this paper we prove this conjecture and, as a consequence, a conjecture of Bang-Jensen, Hell, and MacGillivray from 1995 classifying hereditarily hard digraphs. Further, we show that the CSP dichotomy for digraphs with no sources or sinks agrees with the algebraic characterization conjectured by Bulatov, Jeavons, and Krokhin in 2005." . . "P(GA201/06/0664), P(LC505), Z(MSM0021620839)" . . . . "5" . "Niven, Todd" . . . "3"^^ . "Bang-Jensen and Hell conjectured in 1990 (using the language of graph homomorphisms) a constraint satisfaction problem (CSP) dichotomy for digraphs with no sources or sinks. The conjecture states that the CSP for such a digraph is tractable if each component of its core is a cycle and is NP-complete otherwise. In this paper we prove this conjecture and, as a consequence, a conjecture of Bang-Jensen, Hell, and MacGillivray from 1995 classifying hereditarily hard digraphs. Further, we show that the CSP dichotomy for digraphs with no sources or sinks agrees with the algebraic characterization conjectured by Bulatov, Jeavons, and Krokhin in 2005."@en . . "Kozik, Marcin" . "The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)"@en . "2"^^ . . . "dichotomy; holds; digraphs; sources; sinks; positive; answer; conjecture; Bang-Jensen"@en . . . . . "SIAM Journal on Computing" . . "308646" . . . . "The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)"@en . "RIV/00216208:11320/09:00207006" . . "RIV/00216208:11320/09:00207006!RIV10-GA0-11320___" . "The CSP dichotomy holds for digraphs with no sources and no sinks ( A positive answer to a conjecture of Bang-Jensen and Hell)" . "0097-5397" . "38" . . "Kozik, Marcin" . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "11320" . "[271C8EF76B54]" . .