Abstrakt
Pro pevný digraf G, problém splnitelnosti omezení se šablonou G, nebo krátce CSP(G), je problém rozhodnutí, zda daný vstupní digraf H má homomorfismus do G. Dichotomická hypotéza Federa a Vardiho postuluje, že CSP(G) je pro libovolný G polynomiálně řešitelné, nebo NP-úplné.
Tento článek potvrzuje hypotézu pro třídu orientovaných stromů, tzv. speciální triády. Jako pozorování dostaneme nejmenšího známý příklad orientovaného stromu (s 39 vrcholy), jehož CSP je NP-úplné.