We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
CSP DICHOTOMY FOR SPECIAL POLYADS.
- Authors
BARTO, LIBOR; BULÍN, JAKUB
- Abstract
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.
- Subjects
POLYADIC algebras; CONSTRAINT satisfaction; PROBLEM solving; GRAPH coloring; HOMOMORPHISMS; DIRECTED graphs
- Publication
International Journal of Algebra & Computation, 2013, Vol 23, Issue 5, p1151
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196713500215