CSP DICHOTOMY FOR SPECIAL POLYADS

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10174135" target="_blank" >RIV/00216208:11320/13:10174135 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1142/S0218196713500215" target="_blank" >http://dx.doi.org/10.1142/S0218196713500215</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1142/S0218196713500215" target="_blank" >10.1142/S0218196713500215</a>

Result language
angličtina
Original language name
CSP DICHOTOMY FOR SPECIAL POLYADS
Original language description
For a digraph H, the Constraint Satisfaction Problem with template H, or CSP(H), is the problem of deciding whether a given input digraph G admits a homomorphism to H. The CSP dichotomy conjecture of Feder and Vardi states that for any digraph H, CSP(H)is either in P or NP-complete. Barto, Kozik, Maroti 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 oforiented 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 anynear-unanimity polymorphism.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/GP201%2F09%2FP223" target="_blank" >GP201/09/P223: Constraint satisfaction problem and universal algebra</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2013
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)