The smallest hard trees

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung



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≠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 Bulín concerning a question of Hell, Nešetřil 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.


Seiten (von - bis)105–137
PublikationsstatusVeröffentlicht - Juni 2023

Externe IDs

Scopus 85150735824
dblp journals/constraints/BodirskyBSW23
WOS 000952043700001
Mendeley d7ffc746-7bb8-36a5-9cf7-e61cfc8c0eb5


DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis


  • Arc consistency, Bounded pathwidth duality, Computational complexity, Constraint satisfaction problem, Datalog, Graph homomorphism, Linear datalog, Polymorphism, Symmetric linear datalog, Tree