Parameterized Complexity of Small Decision Tree Learning


  • Sebastian Ordyniak University of Leeds
  • Stefan Szeider TU Wien


Computational Complexity of Reasoning


We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples. Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters.




How to Cite

Ordyniak, S., & Szeider, S. (2021). Parameterized Complexity of Small Decision Tree Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6454-6462. Retrieved from



AAAI Technical Track on Knowledge Representation and Reasoning