# Optimal Decision Tree Pruning Revisited: Algorithms and Complexity

arXiv: https://arxiv.org/abs/2503.03576 · HTML: https://mlsanity.com/paper/2503.03576/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 39 references that are in the map.
- First posted on arXiv 5 Mar 2025.

## Builds on (most cited first, 5 of 5)

- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [PMLB v1.0: An open source dataset collection for benchmarking machine learning methods](https://mlsanity.com/paper/2012.00058/) (2020)
- [Fast Sparse Decision Tree Optimization via Reference Ensembles](https://mlsanity.com/paper/2112.00798/) (2021)
- [Witty: An Efficient Solver for Computing Minimum-Size Decision Trees](https://mlsanity.com/paper/2412.11954/) (2024)
- [On Computing Optimal Tree Ensembles](https://mlsanity.com/paper/2306.04423/) (2023)

## Built on by (most cited first, 1 of 1)

- [Improving Decision Trees through the Lens of Parameterized Local Search](https://mlsanity.com/paper/2510.12726/) (2025)

## Abstract (arXiv)

We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees. Thereby, we offer new insights into the computational challenges of decision tree simplification, a crucial aspect of developing interpretable and efficient machine learning models. We focus on fundamental pruning operations of subtree replacement and raising, which are used in heuristics. Surprisingly, while optimal pruning can be performed in polynomial time for subtree replacement, the problem is NP-complete for subtree raising. Therefore, we identify parameters and combinations thereof that lead to fixed-parameter tractability or hardness, establishing a precise borderline between these complexity classes. For example, while subtree raising is hard for small domain size D or number d of features, it can be solved in D2d · |I|O(1) time, where |I| is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis.