The Smallest Hard Trees

Manuel Bodirsky, Jakub Bulín, Florian Starke +1

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 orientat…