The smallest hard trees

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

Abstract

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.

Details

Original languageEnglish
Pages (from-to)105–137
Number of pages33
JournalConstraints
Volume28
Issue number2
Publication statusPublished - Jun 2023
Peer-reviewedYes

External IDs

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

Keywords

DFG Classification of Subject Areas according to Review Boards

Subject groups, research areas, subject areas according to Destatis

Keywords

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