Abstract: 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 $D^{2d} \cdot |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.

Lay Summary:

Decision trees classify objects by asking a series of simple questions. The sequence of questions is determined by the answers to previous questions, creating a model with a hierarchical structure that is used to represent and organize data in the form of parent–child relationship. Traditional methods for building decision trees can result in an overly complicated structure, necessitating simplification by not asking some of the less relevant questions.However, identifying which questions to omit without compromising performance is challenging. Therefore, one typically performs educated guesses about which of them could be left out, lacking guarantees on whether the excluded questions were the best ones possible. We study which properties of decision trees can be exploited to achieve such guarantees. That is, we develop algorithms that determine the least relevant questions and are efficient if the initial tree has certain properties, or show that no efficient algorithms exist.Based on our discoveries, we create a proof-of-concept implementation that helps us to assess how well traditional methods perform on this problem when excluding a fixed number of questions. Surprisingly, we discover that they are nearly optimal despite the inherent hardness of the problem, providing new insight on the robustness of conventional methods.