CSP DICHOTOMY FOR SPECIAL POLYADS
Libor Barto, Jakub BulΓn Β· International Journal of Algebra and Computation Β· 2013
For a digraph β, the Constraint Satisfaction Problem with template β, or CSP(β), is the problem of deciding whether a given input digraph πΎ admits a homomorphism to β. The CSP dichotomy conjecture of Feder and Vardi states that for any digraph β, CSP(β) is either in P or NP-complete. Barto, Kozik, MarΓ³ti and Niven (Proc. Amer. Math. Soc.137 (2009) 2921β2934) confirmed the conjecture for a class of oriented trees called special triads. We generalize this result, establishing the dichotomy for a class of oriented trees which we call special polyads. We prove that every tractable special polyad has bounded width and provide the description of special polyads of width 1. We also construct a tractable special polyad which neither has width 1 nor admits any near-unanimity polymorphism.