Complexity of tree homomorphisms
Let \(T\) be an oriented tree and consider the complexity of deciding whether or not a given digraph is homomorphic to \(T\). A class of simple trees with NP-complete homomorphism problems is identified, the smallest tree having 45 vertices. A list of all subtrees that are necessary in order to get NP-complete homomorphism problems for a tree is presented.
scientific article; zbMATH DE number 933107