CSP DICHOTOMY FOR SPECIAL POLYADS
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
CSP DICHOTOMY FOR SPECIAL POLYADS
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
CSP DICHOTOMY FOR SPECIAL POLYADS
Popis výsledku anglicky
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.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GP201%2F09%2FP223" target="_blank" >GP201/09/P223: Splnitelnost omezujících podmínek a univerzální algebra</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2013
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
International Journal of Algebra and Computation
ISSN
0218-1967
e-ISSN
—
Svazek periodika
23
Číslo periodika v rámci svazku
5
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
24
Strana od-do
1151-1174
Kód UT WoS článku
000323514700007
EID výsledku v databázi Scopus
—