  We find an orientation of a tree with 20 vertices such that the corresponding
fixed-template constraint satisfaction problem (CSP) is NP-complete, and prove
that for every orientation of a tree with fewer vertices the corresponding CSP
can be solved in polynomial time. We also compute the smallest tree that is
NL-hard (assuming L is not NL), the smallest tree that cannot be solved by arc
consistency, and the smallest tree that cannot be solved by Datalog. Our
experimental results also support a conjecture of Bulin concerning a question
of Hell, Nesetril and Zhu, namely that "easy trees lack the ability to count".
Most proofs are computer-based and make use of the most recent
universal-algebraic theory about the complexity of finite-domain CSPs. However,
further ideas are required because of the huge number of orientations of trees.
In particular, we use the well-known fact that it suffices to study
orientations of trees that are cores and show how to efficiently decide whether
a given orientation of a tree is a core using the arc-consistency procedure.
Moreover, we present a method to generate orientations of trees that are cores
that works well in practice. In this way we found interesting examples for the
open research problem to classify finite-domain CSPs in NL.
