"11320" . . "0002-9939" . . . . . "Proceedings of the American Mathematical Society" . "RIV/00216208:11320/09:00207021" . . "9" . . . . "CSP dichotomy for special triads"@en . "[A59A17479177]" . . "For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of G, is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 39 vertices) defining an NP-complete CSP(G)."@en . "dichotomy; special; triads"@en . . "Mar\u00F3ti, Miklos" . "Niven, Todd" . "Kozik, Marcin" . "000269307400014" . "Barto, Libor" . . "For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of G, is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 39 vertices) defining an NP-complete CSP(G)." . . "Kozik, Marcin" . "137" . "14"^^ . "308645" . "CSP dichotomy for special triads" . . "P(GA201/06/0664), P(GP201/09/P223), P(LC505), Z(MSM0021620839)" . "CSP dichotomy for special triads" . "RIV/00216208:11320/09:00207021!RIV10-GA0-11320___" . . "2"^^ . . "CSP dichotomy for special triads"@en . . "4"^^ . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . . .