Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Authors: Juha Harviainen
Frank Sommer
Manuel Sorge
Stefan Szeider
Venue: ICML 2025 poster (2025)
Keywords: parameterized complexity
NP-hard problems
efficient algorithms
dynamic programming
subtree replacement
subtree raising
Primary area: theory->optimization
TL;DR: We present a comprehensive parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decision trees

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.

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Juha Harviainen Frank Sommer
Manuel Sorge" Stefan Szeider
Abstract
Holzinger al., 2020). Recent advancements in algorithms have made it feasible to compute decision trees that optimal with respect to various optimization goals (e.g., Narodytska et al., 2018; Demirovic et al., 2022: McTaavish et al., 2022). With that, the algorithmics and parameterized complexity of the underlying optimization problems were studied intensively (Staus et al., 2025; Ordyniak & Szeider, 2021; Kobourov al., 2025; Eiben et al., 2023; Komusiewiez et al., 2023a; Ordyniak et al., 2024; Gahlawat & Zehavi, 2024; Komusiewicz et al., 2025), feeding back into practical advances (Staus et al., 2025).
We present a comprehensive classical and pa- rameterized 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 computa- tional challenges of decision tree simplification, a crucial aspect of developing interpretable and effi- cient machine learning models. We focus on fun- damental pruning operations of subtree replace- ment and raising, which are used in heuristics. Surprisingly, while optimal pruning can be per- formed in polynomial time for subtree replace- ment, 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 bor- derline 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 Dad | ((1) time, where // is the input size. We complement our theoretical findings with preliminary experimental results, demonstrating the practical implications of our analysis.
Large datasets still require heuristic optimization techniques, however. Commonly used heuristics to compute decision trees for given data recursively split the input data based on certain criteria such as reduction in entropy (Quinlan, 1986; Breiman et al., 1984; Mingers, 1989). The resulting large trees often overfit, and so the heuristics then prune them, that is, they delete nodes to decrease the size while maintaining good classification performance. In other words, they heuristically solve optimization problems in which they balance some form of the two goals of maximizing the number of pruned nodes and minimizing the number of introduced errors. This motivates studying these optimization problems themselves.
While the algorithmics of computing optimal decision trees from scratch is reasonably well understood, the algorithmics of optimally pruning a given decision tree has received scant attention. Our goal is to initiate a rigorous algorithmic study of the latter, highlighting what properties make the underlying problems hard or tractable, and pointing to promising algorithmic approaches that may be developed further into practical implementations.
1. Introduction
Decision trees are fundamental data structures used to describe, classify, and generalize data (Larose, 2014; Murthy, 1998; Quinlan, 1986). They are widely used in machine learning due to their interpretability and efficiency (Breiman et al., 1984). Towards explainable AI, one prefers small decision trees over large ones as they provide more concise and understandable models (Rudin, 2019;
There are two main operations that heuristics apply, sub- tree replacement and subtree raising (see below for details), and we study optimally pruning trees under each of these. An overview of our results is follows. It was already known that optimally replacing subtrees is polynomial-time sol (Almuallim, 1996), so we study the running time in more detail and give an improved algorithm that is lin- ear instead of quadratic in the tree size if the number & of pruned nodes or number of misclassifications small. As side result, we give a quicker algorithm for classifying examples with a given tree based on heavy-light decom-
Equaal contribution 'Department of Computer Science, University of Helsinki, Helsinki, Finland "Institute of Logic and Computation, TU Wien, Austria. Correspon- dence to: Juha Harviainen nnlhahharviainenheer fi Frank Sommer < <fsommer@ aaanmerr@a.tuwien... wc..uwien.acc.t> Manuel Stefan Szeider
Sorge www.:el.....ee...uiii..... <sz@@c wtt.aaacttwic.ac.at...
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
(a)
(h)
set E[T, wo of examples classified in the subtree rooted w contains at least as many blue examples red examples, and otherwise receives color red. Replacement is basic pruning operation and used in CART (Breiman et al., 1984) and C4.5 (Quinlan, 1993), for example.
the new leaf pots the most frequent class assignicd
A subtree raising operation applied to w removes w and its entire left or right subtree from T. In other words, we choose a child of and then we remove the subtree rooted at w and replace it by the subtree rooted at Subtree raising is implemented in the well-known decision tree heuristics C4.5 (Quinlan, 1993). C5.0, and J48 (Witten et al., 2011).
Figure 1. Illustration of the two pruning operations. (a) shows the input tree T. (b) shows the result of one subtree replacement operation. (c) shows the result one subtree raising operation.
positions (Sleator& & Tarjan, 1983). In contrast, we show that optimally pruning a decision tree with subtree raising is No-comleee. In general we thus cannot expect efficient algorithms and therefore investigate which aspects of the problem make it hard or tractable. In this regard, we com- pletely classify the influence of natural single parameters, such as k t, the number d of features, the domain size D on the complexity of raising subtrees optimally. Further, we almost completely classify all pairs and triples of parame- ters. For instance, we show that we cannot expect efficient algorithms for optimally raising subtrees if D or d is small, however, there a prospect for an efficient algorithm if they are both small the same time. This latter algorithm might be relevant for practice: We provide a proof-of-concept im- plementation and use it on standard benchmark data to show that heuristics achieve an almost optimal tradeoff between the number of pruned nodes and introduced classification errors.
We now formulate the optimization problems implicitly solved by the tree-pruning heuristics as search problems: We aim to prune k inner nodes while satisfying an upper bound t on the number of resulting classification errors. 3 Algorithms solving these problems can also perform error minimization.
DECISION TREE REPLACEMENT (DTREP)
Instance: A training data set (E, A), a decision tree T for (E, A), and k, t E N.
Question: Can we perform replacement operations that prune exactly k inner nodes such that the resulting tree 7" has at most t errors?
DECISION TREE RAISING (DTRAIS_)
Instance: A training data set (E, AE, a decision tree T for (E, and k, ( E I.
Question: Can we perform raising operations that prune exactly inner nodes such that the resulting tree T' has at most errors?
Our results offer new insights into the computational chal- lenges of decision tree simplification and provide theo- retical foundation for developing more efficient pruning algorithms. Our results contribute to the growing body of work on the theoretical foundations of interpretable ML, which is crucial for developing trustworthy Al systems.
For technical reasons (see the preliminaries), replacing at least nodes has the same complexity as replacing exactly k. This is not so for raising, and thus we also study the variant DTRAIS where we perform at least raising operations.
Problem statement. We study two types of pruning oper- ations that are used by implementations in well-established mechine-learning libraries (see Figure for illustrations), focusing on decision trees that are binary trees throughout the paper. Let T be a decision tree for a set E C Rd of examples labeled via A: E + (blue, red) by two² classes blue and red and let E VTT) inner (non-leaf) node of T. Here, for a graph G, by (GG) we refer to its vertex set.
Results for replacement. It is known that DTREP can be solved in O(n + f)s) time (Almuallim, 1996), where n is the number of input examples, s the size of the in- put tree and f = 8 - A the size of the tree after pruning. This means that the running time is quadratic in the tree size. We show that one can achieve time linear in the size, that is, O(n min (2)) s) time, if k is small (Theorem 3.1). As side result, we show that classify- ing a given example can be done in time Old log" s) af- ter (ds)-time preprocessing, where d is the number of
A subtree replacement operation applied to w removes w and its entire subtree from T and replaces it by a new leaf u which has the most frequent class label of all examples in the subtree of w, that is, u receives color blue if the
'Throughout, use the following intuitive equivalence be- tween the number of operations and the number of pruned nodes: A replacement operation that removes inner nodes can be simu- lated by k replacement operations applied to inner nodes that have 2 leaves children. Similarly, a raising operation that removes k inner nodes be simulated by l raising operations applied inner nodes that have 2 children and least one them is a leaf.
A continuously updated version of our paper is available on arXiv (Harviainen et al., 2025a) and the related source code for replicating the experiments on Zenodo (Harviainen et al., 2025b). In general our algorithms can also be used in the multiclass setting; see Section 7 for short discussion.
2

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
resalt for DTRAIS_.
parameter
result for RAIS
BF
Thm. 4.2
?
Thm 4.6
FPT
BF
++
dy + D
Auss + D++1
XP and Whilhard paraNP-hard
BF
RP
Thm. S.1
Thm, 5.1
A++ d Suax + dy
i++ dass + di +
+ Sres D +
Thm.
Thm. 5.1
Thm. 5.5
Thmn. 5.6
Prop. 5.7
Thm. 5.1
P
Thm.
Tim
Thm 4.2
BF
Thm 4.5
Thm.
Thm. 5.2
Thm. 4.2
Thm. 4.2
Thm. 5.1
ders D,
b.s. dr Thm. 3.6 BF
R dreax
Thiis, 5.2 and 5.3
Thm 5.1
Thm 5.5
Figure 2. A Hasse diagram of the single parameter relations and results for DTRAIS=, D'RAISy: parameter p has an edge to lower parameter q if there a functtin f such that after straight- forward preprocessing we have q Σ f(p). The corresponding theorems and propositions are given in the boxes; for hardness the reference is in the highest box for which hardness holds, for (FPT or XP) tractability the reference is in the lowest box for which tractability holds. BF is for brute-force algorithm.
Inrgest parameter p
D + binca +
Hardness
FPT
Algorthm:
Thm. 5.1
XP and WiJn--aad
smallest parameter
paraN--hard
DTRAIS_
DTRAIS
Figure 3. Overview of our results for DTRAIS=, D For each box q is the smallest parameter required to achieve an FPT or XP algorithm, and p is the largest parameter such that W[1]- hardness or paraNP-hardness holds. Also, each parameter combi- nation which is not smaller than and not larger than leads to the same classification result. Consequently, for parameters q leading to an FPT-algorithm, all paramcters which are not smaller than g also lead to an FPT-algorithm. BF is for brute-force algorithm.
features (Lemma 3.2). This improves on the straightfor- ward ((s)-time algorithm. Given these polynomial-tine results, it is interesting to extend them to replacing subtrees in decision-tred -reee ensembles, which have received a tremen- dous amount of attention for their simplicity and improved accuracy over plain decision trees (Breiman, 2001; Rokach, 2016). However, we show that efficiently pruning ensem- bles is unlikely, since the problem is comolleee even if they contain only two trees (Theorem 3.4).
the parameter ōmax the maximum number of features in which two examples of different classes differ.* Also, we consider the largest number dr of different features that occur on a root-to-leaf path in the input tree.
Results for raising. In contrast to the tractability of DTREP, surprisingly DTRAIS= and DTRAIS> turned out to be NP-complete. Hence, we studied the parameterized complexity, determining the influence of the most natural pa- rameters on the problems' complexity (Gottlob et al., 2002; Flum & Grohe, 2006; Niedermeier, 2006; Cygan et al., 2015; Downey & Fellows, 2013). There are three main levels of influence that a parameter p can have when a problem is NP-hard: ideally (1)
Figure shows overview over the relations between all parameters together with our complexity results for D'TRII== and DTRAIS> for individual parameters; in fact, we completely classify the two problems with respect to the three levels of influence that the parameters can have. Apart from two trivial tractability results for n and 8, assuming all other individual parameters to be small still yields in- tractable problems. Notably, DTRAIS> remains NP-hard, even for pruning at least & = 0 nodes. Given such broadly negative results, we also consider combinations of two or more parameters, see Figure 3 for an overview. Indeed, we obtain an almost full classification for pairs and triples of parameters. Among several tractability results, we obtain an algorithm with D ((1)) running time.
tractability (FPT), that is, there is an algorithm with (p) - (7)0(1) running time, or (2) W[[]-hardness and XP-tractability, that is, there is an algorithm with running time f(p)- ( and it is likely not possible to remove the dependence of the exponent p, and (3) paraNP-hardnee that is, even for constant values of p the problem is NP-hard.
This latter algorithm is particularly interesting in combina- tion with measurements that show that the parameters D and dr are small in benchmark data for computing optimal imple-
Natural parameters for this analysis are the size of the initial unpruned tree T, the lower bound i: on the removed inner nodes, and the upper bound of errors of the pruned tree. A dual parameter to l is the upper bound é on the size of the tree after pruning (A: + s). Further natural parameters are priori related to the input dataset, but actu- ally we may assume that these parameters refer only to the input trees, not to the data itself, see Section 2: the number of features, the number n of examples, and the maximum domain size D, that is, the maximum number of different values that a feature can attain. Furthermore, we consider
decision trees. Thus we provide a proof-of-coneee mentation and use it to compute the complete Pareto-front of the optimal tradeoff' between the number & of pruned nodes and number t of classification errors. This allows us for the first time to measure the quality of the heuristic prun- ing techniques, showing that they achieve almost optimal
'See Ordyniak & Szeider (2021, Table 1) and Staus al. (2025, Table 3) for indication that this parameter is small in practical data.
3

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
tradeoff's in our data.
all our thresholds are integers in the reductions, so changing value x: of some feature x' with [æo] < x' [x]] will not change the leaf the example ends up at.
2. Preliminaries
Reasonable trees. We assume that the input tree T in DTREP, DTRAIS=, DTRAISS is reasonable, that is, (a) no leaf is empty and (b) every leaf has the label of a most frequent example set in this leaf. That is, the set of exam- ples at each cut should be nonempty, and the threshold there should partition that set into two nonempty sets. Note that all trees computed by standard heuristics are reasonable. We make this assumption purely for our hardness results to be more relevant to practical situations. With the replacement operation, since the input trees are reasonable, the number of errors cannot decrease as more cuts are pruned. This is not the case with raising operations (see Theorem 5.4) and thus we study both DTRAIS= and DTRAIS
For m E IN we write [m]] = (1,2...., m_} and [0, m] == [m] U (0}. For e E Rd we denote by e[i] the ith entry of e. Sometimes, we may slightly abuse the notation by indexing the entries by other objects than the integers E [d], such as the set of vertices of a graph. We can assume that there is bijection between these objects and the set [d].
Let Σ be a set of class labels; unless stated otherwise, we use Σ = fblue, red]. A decision tree in Id with set of classes Σ consists of an ordered binary tree T. that is, each inner node has a well-defined left and right child. Let feat: (T) - [d] and thr: (IT) - R be labelings of each inner node v E ((T) by a feature feat(u) E [d] and threshold thr(u) E R. Additionally, let cla: V(T)= + Σ be labeling of the leaves of T by class labels. The tu- ple (T, feat, thr, cla) is a decision tree in Ra with set of classes Σ. We often omit the labelings feat, thr, cla and just refer to the tree T. The size of I' is the number of its inner nodes, also referred to as cuts.
Relations between parameters. Note that since we are only interested in the classification properties of subtrees of the input tree T, we can omit from all examples all features that do not occur in cuts in T. Similarly, we can preprocess the domains in each feature E [d]: We may look at all the thresholds that occur in feature in some cut in T, say their number is D Then to the values in netwen such thresholds. Accounting for a minimum and maximum value, we may thus assume that the domain of i contains at most D' + 2 values. Hence, the maximum domain size D is upper bounded by 2 plus the maximum number of thresholds that occur in a feature in T,
A training data set is tpple (F,, A) of set of examples E S IRd and their class labeling A: E' + E. Given training data set, we fix for each feature a minimum-sizzi set (h)(i) of thresholds that distinguishes between all values of the examples in the ith feature. In other words, for each pair of examples e and e' with e|i] < e'li]. there is at least one value x E Thr(i) such that eli] < x e'ii]. For a fea- ture i [d] and threshold x E Thr(i),,
discretize the examples
Proofs marked with are deferred to the appendix.
use Eg [i, == {e E E' eli] I J and Es [i, x] == {e E E eli] > x} to denote the set of examples of E whose ith feature is less or equal, and strictly greater than x, respectively.
3. Results for Subtree Replacement
In this section, we present our results for the subtree replace- ment operation. The problem solvable in polynomial time with dynamic programming (DP) by a reduction to TREE KNAPSACK, and an improved version of the algorithm re- quires O(nn + f)s) time (Almuallim, 1996). However, if only a small number of cuts are pruned, then the time com- plexity is quadratic in the size. We propose novel algo- rithm whose complexity is only linear in the size if the num- ber of pruned cuts or allowed misclassifications is small: Theorem 3.1. DTREP can be solved in time O(n + min min(k?, .))).))
Now, let T be a decision tree. Each node v E V(T). including the leaves, defines a subset E/T, v] S E as follows. For the root u of T, we define ETT, v)] = E.
For each non-root node v, let w denote the parent of We then define E(T, u] == E(T, w] n Es (fea((w), thr(w] if u is the left child of w and E(T. u] = E w] n E> [feat(w), [h)( if is the right child of w. If the tree T is clear from the context, we simplify E u] to Elu]. Thus for each example e E E there is a unique leaf such that e E Elu)). We also say that is the leaf of e. Note that the sets E(p] at the leaves v of T form a partition of E. If v is the leaf of e, we say that cla(v) is the class assigned to by T. An example e E E is correctly classified by T if the class assigned to it is X(e), and otherwise it is referred to as being misclassified or an error.
Proof. First, we compute for each node v the number of misclassified examples f, in the subtree rooted at v if we were to replace the subtree by red or blue leaf, whichever minimizes the number of errors. This requires ((ns) time in the worst case and less if the tree is not deep. Similarly, we compute the size Su of the subtree rooted at each v.
Identical feature values. Note that we allow our examples to have identical values in all features, and this occurs in our reductions. However, they could also be adjusted to have two identical examples, at the cost of increasing 1) and 6maxi
We use bottom-up dynamic programming, indexing the re- currence by the current node and the number of pruned
4

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
DTRAIS> with respect É: we iterate over all (ss*) possi- nodes errors, depending on which of l and l is smaller. If l let opt(v, ke) for k' [0, k] be the smallest possi- ble number of errors in the subtree rooted at v after pruning exactly k' inner nodes from it. Further, let u and w be the children of v. Then, let (1, 8e 1) = Ly if 8o - 1 S k.
ble combinations of subtrees that are pruned away or ((s*) combinations of unpruned cuts. FPT for follows from there being at most 2" possible pruned trees. Thus, both D'RRII== and DTRA are also FPT for l + f. Similarly, since each input decision tree is reasonable, we have S n and thus both are FPT for n. We start by presenting an XP-algorithm for the number d of features that serves as a starting point for the rest of the algorithms developed in this subsection.
and, for k' < 5y 1, let
opt(v, ke k(
min k)) + opt(w, A/- k-).
If U is the root of the tree and opt(v, k) S i, then there exists a feasible pruned tree for the instance of DTREP. Otherwise, if L < k. we use similar algorithm but instead maximize the number of pruned nodes given that we get t' errors in the subtree. A solution exists if we can prune at least k cuts while having at most errors, since we can prune fewer cuts without introducing more errors. LI
Theorem 4.1. DTRAIS_ and DTRAIS can be solved in O (g) time.
The algorithm uses bottom-up dynamic programming on the input tree T. Intuitively, for each node v of T we compute the minimum number of errors achievable by raising opera- tions that prune at least (or exactly) h nodes in the subtree of T rooted at v. In order to do that, we need to be able to determine the set E' of examples that are classified in e's subtree after pruning. Set E' may be different from E[T, v] because in an optimal solution we may have to prune some nodes on the path P in T from the root to v. Think of the nodes on P as successively cutting away examples from E', that is, if a node w's successor on P is a left child, w cuts away examples on the left in its feature and if it is a right child, w cuts away examples on the right. To find E' it is thus sufficient, for each feature i, to determine the two strongest cuts that remain after raising. That is, among all cuts that cut away examples on the left the strongest cut would be the rightmost one and among all cuts that cut away examples on the right, the strongest cut would be the left- most one. Therefore we index the table, in addition to v and the remaining budget k', in each feature with the thresholds corresponding to the two strongest remaining cuts.
Currently, computing the number of misclassifications in each subtree dominates the time complexity and requires (ns) time. We next speed up the classification of examples with heavy-light decompositions (Sleator & Tarjan, 1983), thus obtaining faster algorithm for DTREP.
Lemma 3.2 (+)) After O(ds) preprocessing, we can classify any example in time Od s).
Corollary 3.3. DTREP can be solved in time O( min(k? _t) . + nd nog""s)) s).
Proof. First, classify all n examples by utilizing Lemma 3.2. Second, use the algorithm of Theorem 3.1.
D
Interestingly, pruning with subtree replacement becomes hard if we consider tree ensembles. A tree ensemble T is set of decision trees and TT classifies (F, >) if for each example E E the majority vote of the trees in T agrees with the label X(e); ties are broken consistently.
Proof of Theorem 4.1. We only show the result for DTRAIS,,, the proof for DTRAIS_ is analogous.
We show this by reducing from the NP-hard k- BIIIIIIQUE problem (Johnson, 1987). The constructed ensemble has two trees, one for each partite set. Each tree consists of long root-to-leaf path that cannot be pruned without violat- ing the error bound. To the unspecified children of this fixed path we attach a cut corresponding to a vertex selection. We then create edge examples which are correctly classified only if both cuts corresponding to the endpoints of e are preserved. Parameter É is chosen such that we can only pre- serve 2- i cuts. The desired error bound forces us to select exactly cuts per tree which correspond to r-biclique. Theorem 3.4 (+). DTREP is NP-hard even foenfor an ensemble 2 trees where both trees are reasonable and d = 3.
Definition of the DP table: For each node v E VTT) let T. be the subtree of T rooted at v. Denote by El(e,,, re)eetal the set of examples in E within the box de- fined by (Le, re)eelg with l, E Thr(i), that is,
E[((I, == n E> &] Bslirr). iE|4
We index the DP table Q by the root node v E V(T) of the subtree, remaining budget k' E [0, kj. and the thresholds (es, re)eet) with l, E Thr(i). To an entry Q2v, (e),rt) k"). we put the minimum number of mis- classifications achievable on the example set Fl((e, re))e with a tree obtained from the subtree T, by raising opera- tions that prune at least k'' inner nodes from T..
4. Algorithms for Subtree Raising
Before presenting our main algorithmic results, note that DTRAIS= trivially in XP with respect to and e, and
Location of the solution: A solution to DTRAIS can be
5

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
read off from Q by letting be the root of T, k' = k. and e = min min((T)(()) and r; max(TTr(i)) for each i.
Theorem 4.2 (+), DTRAIS_ and DTRAIS can be solved
in O(DD + 2)2dr 82) time.
Initialization of Q: The values at a leaf v are the numbers of examples in ((,,, re)g with a different label from v, since a leaf cannot be pruned without removing the parent.
So far, all of our results applied to both the at least and the exactly variant of subtree raising. However, for DTRAIS=.. we can achieve an FPT-algorithm for k d. Later, in Proposi- tion 5.7 we show that such result for DTRAIS> is unlikely to exist under standard complexity theory assumptions.
Recurrence of Q: Let u, w be the left and right child of v, respectively. and let Su, Sw be the number of inner nodes in Tu and Tw, respectively. We claim that
Theorem 4.3. DTRAIS= can be solved in ( (((++)2arrs))) .2)) time.
Q(u, (()se4)) K']
Quu, (4i, (i)sed) k' - 8w - 11, Qlu, (4,, mi)eela, K' 8n -1], minure Quu, (lu,))) ke)gg,"" Q(u, (f.". Te)se(d.. W' -k],,
Proof Sketch. We proceed analogously to Theorems 4.1 and 4.2 for filling a table Q via bottom-up dynamic programming on the input tree T. The main difference is that we restrict the possibilities for the values of the thresholds E, Ti. Intuitively, if we focus on the strongest k + 1 cuts on the left in a specific feature i, at least one them cannot be pruned. Thus, the threshold & that we index our table with has to be among these A + 1 cuts. This restricts the number of table entries to O + 1)2dr . s9).
min
(1)
where 4.' l and r Ti if i + feat(v), and otherwise rht Mleat(v)) min(freat(y), thr(t)) and f leat()) max (feaat))) thr(:)).
Correctness of the DP: To see that Equation (1) is correct, first show that the left-hand side is smaller or equal to the right-hand side. Let TV be obtained from T. by pruning at least K'' nodes by raising. There are three cases:
Definition of the DP table: Table Q is defined similarly to Theorem 4.1, but we only consider relevant (see below) threshold sequences (e,, re)eE4 for node with l,, ri E Thr(i). Intuitively, the thresholds (fi,r;) must be the thresholds of the strongest cuts in feature i that occur above u in T after removing at most k - k' cuts above v. Let P be the path in T from v to the root. For each feature E [d] let (e)), be the list of thresholds of the cuts on the left above ordered from right to left (largest to smallest). That is, to obtain (L)))E,, take the set of thresholds of cuts y on ((P) \ {v} such feat(y) i and y's predecessor on P is a right child, and then order it descendingly. Similarly, let (r:) )e.. be the list of thresholds of the cuts on the right above v ordered from left to right (smallest to largest).
First, v, the subtree Tw. and possibly some nodes in Tu are pruned to obtain TV. Note that, then, the number of errors of TV for El(e,, re]] is at least Q/u, (L,, rs)se(d) K' sw - 1]. Analogously, if u and the subtree T2 are pruned, then the number of errors of T for E((Ai, ra) is at least Quu, (4,, ri)eed) k' 8. 1].
In the third case, v is not pruned and all raising opera- tions in Tu are contained in Tu and Tw. Let Ty and Th, be the resulting trees and let K, and Kg be the number of pruned nodes in Tn and T.., respectively. Further, let tu and fur be the numbers of misclassifications in T. that occur in TV and Ty respectively. Observe that the ex- ample set classified by Ty is (((C,,))))((() where ru is defined as in the recurrence. Analogously, the example set classified by Ty, is (r:)st())) Thus, lu + to 2 Quu, (l,, r²) (eetd) K,] + Q(u: (f.". rr)se ]. Hence, the left-hand side of the recurrence equals at most the right-hand side. We defer the other direction Appendix B.I.
We now need notation to refer to the strength of a cut c, which is intuitively one plus the number of cuts that have to be pruned such that e becomes the strongest cut. For this, let id)(i) be the index of l; in (L) that is, if & = E/, then id) = j. Note that the index is well-defined. Analogously, let (i) be the index of ra in (r)) Sequence (e)) is relevant (for node v) if the remaining budget K' together with the number of cuts that need to be pruned above e such that the thresholds 4;, ri correspond to the strongest cuts do not exceed k. Formally, it must hold that k 2 k' + Eiela (id)(i) + (i) - 2). Observe that the sum indeed measures the number of nodes we have remove from P so that the strongest remaining cuts have the thresholds specified in (l,, ri)se(d)-
Running time of the DP: Observe that there are D2d table entries, and each entry can be computed in ((s) time. Proof for DTRAIS is analogous but we prune exactly k
nodes instead of at least l nodes in the definition of Q. m
By only considering thresholds that are actually used in the input tree, we can improve the running time. For this, we define the following parameter: Let Dr be the maximum number of different thresholds on cuts in feature i on path P over all features E [d] and all root-to-leaf paths P.
Recurrence and correctness of the DP: The same as in Equation (1), except that we will not prune v if it would lead to too many cuts being removed to obtain the specified thresholds. Moreover, we will not prune the
6

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
eut if k k' + Eigga (i) ((d + in this way, the sequence (Li, ra keejd is relevant for v then also in the table entries on the right-hand side is the case that the sequences of thresholds are relevant for the corresponding nodes. We omit a correctness proof of the recurrence because it is analogous to the proof of Thm. 4.1.
(i) 2). Note that,
F2 0
blue
0
blue
By S
blue
Running time: There are (k + 1)3dr s² relevant threshold sequences, and each entry is computed in (ss) time. D
blue
Fy S
red
blue
Next, we prove that DTRAIS> is in XP for l + L. We start with the special case of k- = = 0:
Figure The initial decision tree used for Theorem 5.1.
Lemma 4.4 (+) DTRAIS> can be solved in (ns) time i - - O.
construct decision tree T whose inner nodes relate the vertices of G in the sense that pruning subset of inner nodes leads to no misclassification if and only if the corre- sponding set of vertices of G is an independent set. Further, we let k = K. and / = 0 in our reduction.
Theorem 4.5 (*)). DTRAIS> is solvable in O( 0(n't1gh-1) s time.
Theorem 4.6
(+)). DTRAIS can be solved in
((65m Dé(t + 1))e .Pns) time.
We create one blue example e for each edge (v, w) of G such that e(e] = e(w] = 1 and otherwise elu] 0 for E V(G). Additionally, we create one red example with elu] = 0 for all E VG)).. The inner nodes of our initial de- cision tree T form path such that there is single cut with respect to each feature V E V()) in an arbitrary but fixed order. If efv] = 1, then the example is directed to a blue leaf, and otherwise passed forward on the path. At the end of the path, there is red leaf. This is illustrated in Figure 4.
Note that since for DTRAIS= we cannot assume that the pruned tree is minimal, cannot use the algorithm of Theorem 4.6.
5. Hardness Results for Subtree Raising
In this subsection we show by complementing hardness results that our algorithmic results from Section cannot be improved substantially without violating standard com- plexity assumptions. Specifically, Time Hypothesis (ETH), which states that states that ASAT on n-variable formulas cannot be solved in 20(n) time (Im- pagliazzo & Paturi, 2001; Impagliazzo et al., 2001). In this section, by I we denote the instance of DTRAIS_ or DTRAISZ we construct in the reductions.
Initially, all examples are classified correctly. Any subtree including the unique red leaf cannot be pruned, because then the unique red example would be misclassified. Con- sequently, each raising operation removes an inner node and the blue leaf attached to it. On the other hand, the example corresponding to an edge (v, w) gets misclassified if the cuts related vertices v and w are both pruned. Hence, the pruned features correspond an independent set in G, and, if exactly/at least i cuts can be pruned, then there exists an in- dependent set of size exactly/at least k. Since k = we ob- tain the (4))-[/1o(k time lower bound if the ETH is true. We defer adaption for reasonable trees to the Appendix.
the Exponential
First, we show that the trivial brute-force algorithm for DTRAIS= cannot be improved significantly.
Theorem 5.1. Even if 8max 2, = 2, and both DTRAIS= and DTRAIS are W[I]-hard for i and, unless the ETH is false, they cannot be solved in f time.5
O
Now, we show, by adapting the proof of Theorem 5.1, that also the simple O(s²) time brute-force algorithms for DTRAIS and DTRAIS cannot be improved significantly.
Proof. We prove the statement by reduction from the
W[I]-hard (Downey & Fellows, 1995) problem of k- INDEPENDENT SET which cannot be solved in f() n(x) time unless the ETH fails (Cygan et al., 2015). The input is graph G and an integer K, and the task is to find a set S C V(G) of size at least 6 such that no edge of G has both endpoints in S. With slight abuse of notation, we let the vertices of G be the (binary) features of the examples. We first show the statement for non-reasonable trees. We
Theorem 5.2 (*). Even if dmax 2 and D 2, both DTRAIS and DTRAIS are W[l]-hard for E and, un- less the ETH is false, they cannot be solved in ((f(e)- (T)((0) time, even if 6max = 2, and D) = 2.
Theorem 5.3 (*).. Even if t 0 and D = 2, both DTRAIS= and DTRAIS> are W[2]-hard for E and, un- less the ETH is false, they cannot be solved in (f)())- (T(()) time, even ift = and D 2.
'The Exponential Time Hypothesis (ETH) states that 3-SAT on n-variable formulas cannot be solved in 20(n) time, Im- pagliazzo& Paturi (2001); Impagliazzo et al. (2001) for details.
Next, we show that DTRAIS substantially harder than
7

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
DTRAIS= with respect k: A similar (nn time brute- force algorithm for ATRAIS implies P=NP. This result is based on the observation that the number of errors does not increase monotone if more raising operations are performed.
Table I. Datasets with improvable heuristic results: is the initial unpruned tree size, hais the number of pruned nodes by the raising heuristic, keepi the number of pruned nodes by the replacement heuristic, k" the maximum number of nodes that can be pruned by raising operations while maintaining at most bras errors. Column tris contains the number of errors obtained by the raising heuristic, frept the number of errors obtained by the replacement heuristic, and t the minimum number of errors obtainable by pruning least kais nodes with raising operations.
Theorem 5.4 (+)) For every positive integer k there is a training data set (F,,) X) and an initial decision tree T with zero errors such that only performing k raising operations leads to a tree without errors and performing j raising operation for any 1 j < k leads to at least one error.
Theorem 5.5 (*). ) DTRAIS> is NP-hard even if k O,
Datasct
Ayis
Kiepl
k-
fris
Frepi
t²
6max = 2, and D = 2.
soyhean
28
1.5
15
17
8
8
7
cleveland-nominal
46
38
38
39
23
23
22
We now show that our XP-algorithm for d (Theorem 4.1) cannot be improved to an FPT-algorithm and that the ex- ponential dependence on d cannot be reduced substantially.
haberman
92
74
71
75
39
38
38
postoperative-patien
23
3
2
3
1
1
1
heart-statlog
54
31
27
31
17
15
17
Intuitively, we create two features de and df per color class such that in the pruned tree we need to preserve exactly one cut in each feature to fulfill the desired error bound. We achieve this property by adding huge number of blue examples and red examples which can only be dis- tinguished in d². The two cuts in features di and di force us to select exactly one vertex i; of this color class. For each edge we create an edge example. If vertex U/ is selected, then all edge examples corresponding to edges having an endpoint in color class i which is not U; are then misclassi- fied. Thus, we can only correctly classify an edge example if we select both endpoints of that edge. Furthermore, we sure that only edge examples may be misclassified without violating the error bound. Hence, by setting t == m (*), we ensure that we need to select a multicolored clique.
cuts for the chosen number of errors, and near-minimum number of errors for the chosen number of pruned cuts.
We used 40 datasets from the Penn Machine Learning Benchmarks library (Romano et al., 2022), including 32 pre- viously used for minimum-size tree computation (Bessiere et al., 2009; Narodytska et al., 2018; Staus et al., 2025) and additional larger datasets. The datasets range from 72 to 5404 examples (mean 674.88, median 302). We computed unpruned and pruned trees using WEKA 3.8.5's (Frank et al., 2010) C4.5 implementation (Quinlan, 1993): The unpruned trees apply neither replacement nor raising, whereas pruned trees used only the replacement or raising heuristics; more details in the appendix (in particular, Table 2).
Theorem 5.6 (+). Even if 6max = 6, both DTRAIS and DTRAIS& are W[L]-hard for d + and, unless the ETH is false, they cannot be solved in fd + f) [7]((++0) time.
Analysis of the unpruned trees showed that several param- eters are suitably small with medians s: 26, d: 9, D: 6. We thus used Theorem 4.2; the source code and data are publicly avail- able (Harviainen et al., 2025b). The implementation is a proof of concept and has lots of room for optimizations. We computed the Pareto front that contains for each number k of pruned nodes via subtree raising, the posssibbe classification error of the resulting pruned tree. With mem- ory limit of 64GB and time limit of 24h this was achieved for 26 instances.
algorithm based on
Recall that in Theorem 4.3 we showed that DTRAIS_ is FPT with respect to k +- d. By adapting the proof of Theorem 5.6 slightly, we show that this is unlikely for DTRAIS
Proposition 5.7 ). DTRAIS& is W[L]-hard for d even if = 0 and 8max 6.
Finally, we show that the combination of d and is unlikely to yield an FPT-algorithm.
Key questions we can now answer (see also Table 1):
Theorem 5.8 (+). Even if L O and 6max = 6. both DTRAIS= and D are W[1]-hard for d and, unless the ETH is false, they cannot be solved in f(d) (I(o(d) time.
Do heuristics achieve close to minimum- -osssbble errors for their chosen number of pruned nodes? Mostly yes: In only four of the 26 solved instances, the heuristics did not achieve the minimum-possible errors.
6. Experiments
Do heuristics prune close to maximum number of nodes for their chosen number of errors? Mostly yes: In only four instances the heuristics are suboptimal.
The main goal of our small-scale empirical study was to study whether common heuristics for decision-tree tree pruning find optimal tradeoffs between the number of pruned nodes and errors on the resulting trees. In other words, we assess if the heuristies achieve near-m mar-maxxmum number of pruned
"Staus et al. (2025) used 35 data sets. We had to exclude 3 of them (auto, cloud, spect) since for these dataset the heuristics only outputted a tree with a single cut.
8

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
in Theorem 4.6 also directly apply the multiclass setting without changes. To adapt the algorithm from Theorem 4.6 additionally only need to set the leaf to the class of the dirty example, when we introduce new leaf.
0.200
Jymphegraphy
soybean
0.175
percenbae of crors
While we managed to determine the parameterized complex- ity of most parameter combinations, some combinations of at least three parameters remain open, such as whether DTRAIS= or DTRAIS> is FPT with respect to d d++ + l. Regarding optimally pruning ensembles, NP-hard already for two trees. However, the reduction does not show parameterized hardness and it would thus be inter- esting to see non-trivial for important parameters here. This could be a potentially valuable research direction, since ensembles are typically more accurate than a single decision tree of the same size.
0.125
0.100
0.075
showed it be
30
0.025
tractability results
0.000
10 15
20
25
number nodes
More generally, natural follow-up question is whether can perform other local operations on the input decision trees where we can beat heuristics more clearly. A promis- ing candidate in this direction could be an operation that can arbitrarily reconstruct parts of the decision tree (Schi- dler & Szeider, 2024), thus enabling local changes without removing entire subtrees. Another direction is to investigate related methods such local search (Carreira CCarreira-Perpinán & Tavallali, 2018; Saremi & Yaghmaee, 2018). What is the complexity of computing the associated operations opti- mally and exhaustively?
Figure 5. The trade-off between number of raising operations and classification eгror for three instances. The thin points are the optimal values computed by our algorithm and the thick circles are the values achieved by the raising hcuristic of WEKA.
For a visualization of the Pareto front for three instances, see Figure Soybean one of the few instances where the number of errors of the heuristic larger than the optimum that in
for that number of raising operations. One these instances more nodes can be pruned than the heuristics do without significantly worsening the accuracy.
Acknowledgements
The study indicates that commonly used heuristics perform well in most cases, with only few instances showing room for improvement in either error minimization node prun- ing maximization. However, inspection of the Pareto front leads us hypothesize that often more nodes can be pruned than the heuristics do without worsening the accuracy sig- nificantly.
Juha Harviainen was supported by the Research Council of Finland, Grant 351156, Frank Sommer was supported by the Alexander von Humboldt Foundation. Stefan Szeider was supported by the Austrian Science Fund (FWF) within the projects 10.55776/C0E12 and 10.55776/736420.
Impact Statement
7. Outlook
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
We provided comprehensive analysis of the parameter- ized complexity of optimal pruning with subtree replace- ment and subtree raising, presenting algorithmic results and complexity- -thooreicc lower bounds for each operation. Fur- ther, we performed a small-scale experiment, showing the surprising result that pruning heuristics are almost optimal despite the hardness of the problem, that is, almost ev- ery of our data sets no smaller classification error can be achieved by pruning the same number of nodes. Our algo- rithms were crucial for discovering this, since without them we could not compare the heuristics against the optimum.
In our paper we solely focused on the biclass setting for clarity of the theory. All our hardness results directly apply the multiclass setting. All our algorithms except the one

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
References
tional Joint Conferences on Artificial Intelligence Organi- zation, 2023. URL https::/p///ooc... /ttp://doi.../ http//ii.ogg.../2// 24963/ ijcai (essii.20233555
Almuallim, H. An efficient algorithm for optimal pruning of decision trees. Artif. Intell,, 83(2):347- 362, 1996. URL
http://dooo.ogg///// (95) 00060-7.
Flum, and Grohe, M. Parumeterized Complexity The- ory. Texts in Theoretical Computer Science, An EATCS Series. Springer, 2006. URL https: wtt///o....o..1//
Bessiere, C.. Hebrard, E., and O' O'Sullivan, B. Minimis- ing decision tree size combinatorial optimisation. In Proceedings of the 15th International Conference on Prin- ciples and Practice of Constraint Programming (CP '09), volume 5732 of Lecture Notes in Computer Science, pp. 173- 187. Springer, 2009. URL https: /twiiiiioo///oo org/ 10. 1 1007 978-11111 642 04244---44--
Frank, E., Hall, M. A., Holmes, G., Kirkby, R., and Pfahringer, B. WEKA A machine learning work- bench for data mining. In The Data Mining and Knowledge Discovery Handbook, 2nd ed, pp. 1269- 1277. Springer, 2010. URL https:/ /dtp..og/o.....///////////////// 6..
Breiman, L. Random forests. Mach. Learn., 45(1):5- 32, 2001, URL https::/ddee http://///i..oo///////// wrw/oo.g///... 1023/A:
1010933404324,
Gahlawat, H. and Zehavi, M. Learning small decision trees with few outliers: A parameterized perspective. In Pro- ceedings of the 38th AAAI Conference on Artificial In- telligence (AAAI '24), pp. 12100-12108, AAAI Press, 2024. URL https: /ttp://.oog/.../////ee/eeeee//// /aa0///aaa..... 138111.29098.
Breiman, L.,, Friedman, J. H., Olshen, R. A., and Stone, C. Classification and Regression Trees. Wadsworth, 1984.
Parreira, M. Á. and Tavallali, P. Alternating optimization of decision trees, with application to learning sparse oblique trees. In Proceedings of the Thirty-Second Annual Conference on Neural Information Processing Systems (NeurlPS 18). pp. 1219- 1229, 2018. URL https:/ httpas/////cceedings..... neurips searipps.co/paper/001///sss
Gottlob, G., Scarcello. F,, and Sideri, M. Fixed- -arammerrreeter complexity in AI and nonmonotonic reasoning. Artif. Intell., 138(1-2)555-86, 2002. URL https:/ pppp:://dii /ooi org 10 10t.:0016//0000 30000000000000200000000000000000 (02) 00182-0.
1332238c243233333377fff222222222 abbsaaaaaaaaaaaaaaaaaaaaaaaaattt html.
Guo, J., Niedermeier, R., and Wernicke, S. Parameter- ized complexity of vertex cover variants. Theory Com- put. Syst., 4003):00--500 2007. URL https: //tt:::/di.... /doi.
Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipezuk, M., Pilipczuk, M., and Saurabh, S. Parameterized Algorithmss Springer, 2015. URL https: arooi.orgg10.10000 1007/00000000 /978 3- 319--13--0 1019--2275-33
org 1007 10000000000000000000000000000000
Harviainen, J., Sommer, F., Sorge, M., and Szeider, S. Opti- mal decision tree pruning revisited: Algorithms and com- plexity. CoRR, abs/ abs/2503.03576 2025a. URL https: //dot wtw.i.orrg//00 / 48550/8555/// 205.0..3.6.0..606..6. 03576.
Demirovie, E., Lukina, A., Hebrard, E., Chan, J., Bailey, J., Leckie, C., Ramamohanarao, K., and Stuckey, P. J. MurTree: Optimal decision trees via dynamic program- ming and search. Journal of Machine Learning Research, 13:26:1-26:47 2022.
2503.
Harviainen, J., Sommer, F., Sorge, M., and Szeider, S. Op- timal decision tree pruning revisited: Algorithms and complexity (associated software), 2025b. URL https: ///ooi.or/// /2w//////oo..///dood/d/dooo
Downey, R. G. and Fellows, M. R. Fixed-parameter tractability and completeness II: on completeness for W[1]. Theor. Comput. Sci., 141(1&2)::00- 131, 1995. URL /ttp:::/oo...rr/11..000... 0304 3975 (94) 00097-3..
zenodo..oooooooo 2tw.///eeoooo..3300000.. 15534096.
Holzinger, A., Saranti, A., Molnar, C., Biecek, P., and Samek, W. Explainable Al methods A brief overview. In Proceedings of the Workshop xxAI Beyond Explainable Al Held in Conjunction with the International Confer- ence on Machine Learning (xxAI@ ICMI. 20), volume 13200 of Lecture Notes in Computer Science, pp. 13- 38. Springer, 2020. URL https: //oii /ttp::///oo.oo./.... 003-033---000----
Downey, R. G. and Fellows, M. R. Fundamentals of Parameterized Complexity. Texts in Computer Sci- ence. Springer, 2013. URL https: h http//doi.oae http://ii.ogo...o////o 0:007/97---441--555--
1007
Eiben, E., Ordyniak. S., Paesani, G., and Szeider, S. Leam- ing small decision trees with large domain. In Proceed- ings of the 32nd International Joint Conference on Arti- ficial Intelligence (IJCAI 23),, pp. 3184-3197 Interna-
Impagliazzo, R. and Paturi, R. On the complexity of k-SAT. J. Comput. Syst. Sei., 62(2):367-355 2001. URL https:
10

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Impagliazzo, R., Paturi, R., and Zane, F. Which problems have strongly exponential complexity? Comput. Syst. Sci., 6324):3 2001. URL https: /oo. 10. wtw.1000/ccss.00..2222..
Mingers, J. An empirical comparison of pruning meth- ods for decision tree induction. Mach. Learn., 4:227- 243, 1989. URL https: http::///ooooo..../oo///// /at.g///...02//.... 1022604100933
Murthy, S. K. Automatic construction of decision trees from data: A multi mulli-disciplinnry survey. Data Min. Knowl. Discov., 2(4):345-389, 1998. URL https:
Janota, M. and Morgado, A. SAT-based encodings for optimal decision trees with explicit paths. In Proceed- ings of the 23rd International Conference on Theory and Applications of Satisfiability Testing (SAT' '20), volume 12178 of Lecture Notes in Computer Science, pp. 501- 518. Springer, 2020. URL https::////. httpa:::/doio./////// 1007 0011/99783333333 00000000--------
/ //dpi.org/11 wtt.o/////....////..... 100.1122//0100994443322222
Narodytska, N., Ignatiev, A., Pereira, F., and Marques- Silva, J. Learning optimal decision trees with SAT. In Proceedings of the 27th International Joint Confer- ence on Artificial Intelligence (IJCAI '18), pp. 1362- 1368. ijcai. org. 2018. URL https::///// 24963/ i jecii 2018/189.
Johnson, S. The NP-completeness column: An ongoing guide. J. Algorithms, 8(3):438448, 1987. URL https:/ wtt.oo/.gg...........
/toppp://do.... /tt///doi... org/10.
/ttp://///..////....////0////011 6774 90021-6.
Niedermeier, R.
Invitation to Prred-Parameter Algorithms. Oxford University Press, 2006. URL https: /ttps::/ddoi.oo oto/10..rr1... 1093 : OSO 0S0/978019856607 7. 0001.
Kobourov, S. G., Löffler, M., Montecchiani, F., Pilipezuk, M.. Rutter, I., Seidel, R., Sorge, M., and Wulms, J. The influence of dimensions on the complex- ity of computing decision trees. Artif. Intell., 343: 104322, 2025. URL httpps:/ddo.oo http://ti.org/.../// 1016/ j. j.artint. 2025. 104322.
Ordyniak, S. and Szeider, S. Parameterized complexity of small decision tree learning. In Proceedings of the 35th
AAAI Conference on Artificial Intelligence (AAAI '21), pp. 6454-6462. AAAI Press, 2021. URL https: doi doi.org/10. 1699 /awaaaaia.......... v.s.i...5.......
Komusiewicz, C., Kunz, P., Sommer, F., and Sorge, M. On computing optimal tree ensembles. Proceedings of the International Conference on Ma- chine Learning (ICML. '23), volume 202 of Proceed- ings of Machine Learning Research, pp. 17364-17374. PMLR, 2023a. URL press/v202 /tt////iiiiiiie/./2/. html.
Ordyniak, S., Paesani, G., Rychlicki, M., and Szeider, S. general theoretical framework for learning small- interpretable models. In Proceedings of the 38th AAAI Conference Artificial Intelligence (AAAI '24), pp. 10662-10669 AAAI Press, 2024. URL https:
mm..
/ //doi. org/10..//. 609/aaai. wwwssi..vvi..22..
Quinlan, J. R. Induction decision trees. Machine Learn- ing, 1(1):81-106, 1986. URL aattps://doi... 10. 00023/210022432448880
Komusiewicz, C., Kunz, P., Sommer, F, and Sorge, M. On computing optimal tree ensembles. CoRR, abs/2306.04423, 2023b. URL https::///// /tt. 48550/ http://wwvv.......2.0
Quinlan,
C4.5: Programs for Machine Learning.
Morgan Kaufmann, 1993.
Komusiewicz, C., Schidler, A., Sommer, F., Sorge, M., and Staus, L. P. Learning minimum-siae BDDs: Towards efficient exact algorithms. In Proceedings of the 42th In- ternational Conference on Machine Learning (ICML '25), 2025. To appear.
Rokach, L. Decision forest: Twenty years of research. Inf. Fusion, 27:111-125, 2016. URL htt.t:tt////e / 10. 1 01 6/j.inffoon 201 005.
Romano, J. D., Le, T., Cava, W. G. L., Gregg, J. T., Goldberg, D. J., Chakraborty, P., Ray, N. L., Himmel- stein, D. S., Fu, W., and Moore, H. PMLB v1.0: an open-source dataset collection for benchmarking ma- chine learning methods. Bioinformatics, 38(3):878- 880, 2022. URL https: /woii/o..o////// wrw.//00.o......0 1093/
Larose, D. T. Discovering knowledge in data: intro- duction to data mining, volume 4. John Wiley & Sons, 2014. URL https: httpss:/coniieelirraaa wiley. /book/oo//////o//oooo / 10. cctm///bl/booll/00000/////111111
McTavish, H., Zhong, C., Achermann, R., Karimalis, I, Chen, J., Rudin, C., and Seltzer, M. I. Fast sparse decision tree optimization via reference ensembles. In Proceedings of the 36th AAA/ Conference on Artificial Intelligence (AAAI '22), pp. 0600-96113 2022. URL https: /oo. org/10. 9 aaai. 2...9.90000 21194.
Rudin, C. Stop explaining black box machine learn- ing models for high stakes decisions and use inter- pretable models instead. Nat. Mach. Intell., 1(5):206- 215, 2019. URL https:/ http://....gg/1110000000 s42256-019- 0048-x.

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Saremi, M. and Yaghmaee, F. Improving evolutionary de- cision tree induction with multi-interval discretization. Comput. Intell., 34(2):95-554, 2018. doi: 10.1111/ CO1N.
Schidler, A. and Szeider, S. SAT-based decision tree learn- ing for large data sets. J. Artif. Intell. Res., 80:875-918, 2024. URL https: www.:.o..........oo 1.15956.
Sleator, D. D. and Tarjan, R. E. A data structure for dynamic trees. J. Compul. Syst. Sci., 26(3):362- 391, 1983, URL atips://doi.. http://t.o.gg....///// 1016/ 0022-0000 (83) 90006-5.
Staus, L. Komusiewicz, C., Sommer, and Sorge, M. Witty: An efficient solver for computing minimum-size decision trees. In Proceedings of the 39th Conference on Artificial Intelligence (AAAI '25), pp. 20584-20599 AAAI Press, 2025. URL https: / /oi..ii../// org/oo..//.oooo.ooooooooo....... 1609 /
34268.
Witten, I. H., Frank, E., and Hall, M. A. Data mining: practi- cul machine learning tools and techniques. Morgan Kauf- mann, Elsevier, 3rd edition edition, 2011. URL https: // //www worl worldcat. wttp:o/oo///oo/.../23/
12

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
Appendix
endpoints of e are preserved. Parameter é is chosen such that we can only preserve 2- cuts, Furthermore, the desired error bound forces to select exactly cuts per tree which correspond to a K- k-biclique.
A. Additional Material for Section 3
A.I. Proof of Lemma 3.2
Construction:
Description of the data set: We set blue to the dominant label, that is, if some example e is classified as blue by one tree in the ensemble and as red by the other tree in the ensemble, then e is classified as blue. A visual- ization is shown in Figure 6. Let S E {P. Q} be any partite set.
Proof. We say that an edge (v. u) from e to u in a decision tree T is heavy if the number of nodes in the subtree rooted at is less than twice the number of nodes that the subtree rooted at u has. Otherwise, edge (u, u) is light. Now, any root-to-leaf path has at most O (log s) light edges, and the graph edge-induced by the heavy edges is disjoint union of paths (Sleator& & Tarjan, 1983). Constructing this heavy- light decomposition takes (s) time.
For each edge {pi, 43 E E(G) we add an edge ex- ample e(pt, 43). To all these examples we assign la- bel red.
Now, we compute for each cut and feature the tightest lower and upper bounds with respect that feature the path from the root to v. In other words, we precompute table for characterizing the interval of values on feature which an example can potentially have if it ends up at that cut. This takes ((d)) time.
For each i E [N] and each partite set 5, we add a set B's of separation examples. Each of these sets consists of M examples having the same value in each feature. To all these examples we assign label blue.
Suppose now that we want to classify example e. Since the edge-induced subgraph of the heavy edges is a disjoint union of paths, every cut belongs to unique heavy path, possibly of length O. Now, let be the root ot T and let P, be the unique heavy path containing r. Next, we compute how far e goes on the heavy path P, by binary search: e can only end up at a cut of P, if the value of each feature falls in the interval of possible values we precomputed for all cuts. Testing this for single cut takes ((d) time and the binary search thus takes Old log s) time. Then, the example goes trough a light edge to another heavy path P.s, and we continue with a binary search on that heavy path P., repeating the process until we end up at a leaf. Since T contains at most O (log s) light edges, we conclude that on every root-to-leaf- -ath of T there are at (lot s) heavy paths on any root-to-leaf path of T. Thus, this process takes Od s) time in total.
For each partite set S, we add a set Bs of blue forcing examples. Both of these sets contain exactly M ex- amples and all examples in one of these sets have the same value in each feature.
For each partite set S, we add set Rs of red enforcing examples. Both of these sets contain exactly 4 N M examples and all examples in one of these sets have the same value in each feature.
We add three features dr, do. and dg. It remains to describe the coordinates of all examples in these features.
For each edge example e = e(p;, 9)) we set eldp] = i, e[dg] - j. and e(dx] = 1.
For each separation example e E Bpp we set c|dp] = i, and e[dg] = 0 = e eldx). Similarly, for each separation example e E Bg we set eldg] = i, and eldr] = 0 eldg].
A.2. Proof of Theorem 3.4
Proof. We reduce from the NP-hard R- R-BICLIQUE prob- lem (Johnson, 1987). The input is bipartite graph G with partite sets P = {pI,.... .PP.....PP.. pN) and Q (g....., qN }. M edges, and an integer in such that G has no isolated ver- tices. The task is to decide whether G contains a complete bipartite subgraph with x vertices on each side.
For each forcing example e E Bp we set cjdr] = N + 1, e|dg] = 0, and e[d=] = 1. Similarly, for each forcing example N 1, and e e(dg] = 1.
BQ we set e[dp] = 0. eldg]
For each enforcing example e E Ry we set e(dr] = N + and e[dg] = 0 = E(dE). Similarly, for each enforcing example E RQ we set eldg] = N + and e(dr) 0 e(dx).
The idea is to create an ensemble consisting of two trees, one tree for each partite set. Each of these trees consists of long root-to-leaf path which cannot be pruned without violating the error bound, denoted as required path. To the unspecified children of the required path we attach a further cut which corresponds to a vertex selection. Furthermore, we create edge examples e which can only be correctly classified if both cuts corresponding to the
Outline:
Description of the input ensemble T: The ensemble T consists of two trees Tp and To. We only describe Tp. To obtain To, each cut in de is replaced by the identical cut in dg, that is, dr S x is replaced by dg S x.
13

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
c)
dg x
b)
a)
T P
TQ
red
dp S
red
Ag
example
dp
dq
de
P1
e(p q:)
i
j
dp S ds S 0
dg X 0
dg S
Ry
N
+
0
0
1 92
RQ
0
N
11
0
blue red
dx < D
dp S
blue red
dg S
dg $
Bp
N+1
0
1
P3
0 93
Bg
N+1
B'
i
blue
red
dg S
dg $0
blue
red
dg 0
dg
P
Q
blue
red
red
blue
blue red
red
blue
Figure A visualization of the reduction from the proof Theorem 3.4. a) shows a k- B-BLLIIQUE instance; a k-biclique is depicted brown. b) shows the corresponding classification instance. e) shows both trees Tp and To of the input ensemble T. The brown cuts correspond to cuts which are preserved the solution ensemble T'
One root-to-leaf path of Tp consists of the cuts dp x O, dp S LI....,pp I N, dg I O. We call this the re- quired path p. The left child of the last cut is red leaf and its right child is blue leaf. Furthermore, the left child of the first cut is red leaf. The left child of each remaining cut dp S i for each i E [N] is the cut dE < 0 and its left child is a blue leaf and its right child is a red leaf. This cut is referred to as the Pi-cut. In To these cuts are denoted as the qi-cuts. Since blue is the dominant label, in T each example correctly classified. Finally, we set 2- (N + +2)++ + and M x
Furthermore, each separation example E Bj. is classified as blue in Tp: either its classification path is not changed or the last cut dæ < 0 which is a p:-cut for some ps & P pruned and is replaced by a blue leaf. Since blue the dominant label, e is correctly classified by T An analog argument applies for each separation example E B/-
To verify the desired error bound it remains to show that at least ne² edge examples are correctly classified by T'. More precisely, we show that each edge example corresponding to an edge (pi, 45) in the x-biclique is correctly classified by T'. Observe that for each pt E /r the classification path of all edge examples e(p,, 9=). where q: is neighbor of az, in T' is identical to the one in T. Thus, e(pi, 4z) is classified as red in Tp. An analog argument applies for q: E Q'. Thus, each edge example corresponding to an edge of the K- biclique is correctly classified by T'. Since any x- x-biclique contains exactly n² edges the statement follows.
Clearly, this corresponding instance of DTREP can be con- structed in polynomial time. Furthermore, observe that both trees Tp and To of the ensemble are reasonable since G contains no isolated vertices.
We show that G has a k- k-biclique if and only if T can be pruned by replacement operations such that the resulting ensemble T' has exactly inner nodes and makes at most errors.
Correctness:
(+) Let T' with trees Tpp and T7 be solution for the raising problem, that is, T has ==21 =2 (N + 2) + K inner nodes and makes at most M = x² errors.
(+) Let P' C P and Q' S Q be a k-biclique (for example see part a) of Figure 6). To obtain T', we preserve the required paths of Tp and To. Furthermore, for each p; E p' we also preserve the p--cut, that is, the cut dg S which is the left child of the cut dp S i. Analogously, for each q: E Q' we also preserve the qu-cu. In other words, prune exactly N- K many P--cuts (where Pt & P') and exactly N k many 4j cuts (where 9; & Q') For an example, see part e) of Figure 6. Furthermore, observe that in both the most-frequent tree replacement and the most- frequent ensemble replacement, the label of each new leaf blue. By T and T% we denote the pruned trees.
First, we show that in both trees the required paths need to be preserved to fulfill the error bound. Second, we show that any edge example can only be correctly classified by T' if its classification path in Tj and Ty is identical to the one in Tp and Tq. respectively. Finally, we verify that all correctly classified edge examples correspond to k- biclique..
Outline:
Step 1: If the last cut dg < 0 of the required path of Tp is pruned, then the classification paths all forcing examples in Bp and all enforcing examples in Rp (independent of all other pruning operations) is identical in T'. Since both sets have size at least M, T'' would have least M errors, contradiction. Since pruning any ancestor of this cut implies also pruning this cut, the entire required path of Tp is not pruned in Ty, Analogously, we can show that the required path of To cannot be pruned.
Observe that T' contains exactly 2- 2N++2)+2++ l cuts. It remains verify that T' makes at most i = M- x² errors.
Since the classification path of each forcing and enforcing example in TVp and Ty stays the same as in Tp and Tq. respectively, all these examples are still correctly classified.
14

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
Step 2: Step implies that only Pr-cuts of Tp and qutcuts of To can be pruned. Furthermore, observe that independent of whether the most-frequent tree replacement or the most- frequent ensemble replacement is used, each new leaf which replaces one of these cuts has label blue. Thus, any edge example e = e(p;, qj) where P; & Pt ends up in a blue leaf in Tpp Since blue is the dominant label, e is misclassified as blue by T', independent of the classification result of in To- An analogous argument holds for dj & Q' and Th- Thus, e - e(pi, q2) is correctly classified if and only if pa E P' and 45 E Q'
the table Q(v, (6s, re)setd) k"] for all sequences (4,, ra re)s of thresholds with & r. Thr(i), instead we restrict these sequences follows: First, we vary only the thresholds for the features that occur on the path P from the root to u and for all remaining features i we set the thresholds to the fixed maximum and minimum value, respectively. Second, in each feature E [d] in which we vary thresholds, we consider not all threshold values Ty E Thr(i), but only those at most Dy values that occur on cuts in feature i on P and the minimum and maximum value in feature i. To see that the recurrence works in the same way, note that, if the left-hand side is so restricted, then all table entries that we refer to on the right-hand side are also restricted in this way for their corresponding tree nodes. Thus we refer only to table entries that have previously been computed.
Step 3: By the definition of t, T' has to classify at least Re edge examples correctly. Assume that x many putcuts of Tp are not pruned and that z many qi cuts of To are not pruned. By P" and Q' we denote the vertices of P and Q which correspond to the not pruned p:-cuts and q--cut, respectively. Note that + = 2 K. Since there is at most one edge example for each pair of vertices from P and Q, T' can classify at most x z edge examples correctly. Hence, we obtain that x = Æ = 2. Furthermore, for each p. E P' and each qj E Q' graph G' has to contain the edge (pt.gg) to fulfill the error bound t. Thus, (P", Q') is a k-biclique in G.
B.3. Proof of Lemma 4.4
Proof. Observe that if an example is misclassified, it will remain misclassified unless the leaf to which it ends up gets pruned away. Consequently, to achieve zero errors, we have to repeatedly prune any leaf containing misclassified example while such leaves remain. If the whole tree gets pruned, there is thus no solution. During the execution of the algorithm, each example can pass each edge of the decision tree twice, resulting in (ns) total work.
B. Additional Material for Section 4
B.I. Missing material from Theorem 4.1
B.4. Proof of Theorem 4.5
Now we show that the right-hand side is smaller than or equal to the left-hand side. Consider a tree TV obtained from Tn corresponding to Q(u, (c,, red), K' 8w - 1]. Note that pruning v and the subtree Tu. from T., and then performing the raising operations in TV yields a tree TV that misclassifies exactly Quu, (4, ri) K' Sw 1] exam- ples of (r)eeg)) Furthermore, at least K' nodes have been pruned from To to obtain T. Hence the right-hand side is smaller or equal to Q(u, (c,, rx)seja K' - Sw 1]. By an analogous argument for Tū the right-hand side is also smaller or equal to Q/w, (Ls, re)eed)
Proof. Assume a solution exists. If we prune i cuts from the set of pruned cuts and remove the misclassified exam- ples of the solution, then the algorithm from Lemma 4.4 finds a solution this reduced instance with k = & = 0. Conversely, if no solution exists, then no reduced instance does has solution either. Iterating over all subsets of cuts of size k and subsets of examples of size t results in the desired time complexity.
B.5. Proof of Theorem 4.6
Sa - 11. Let t" = Qiu,, (fi, rr"' )e[(d] k"] Q/1i, (4L, (i)ierr) K k"] wherein k" minimizes the sum. Consider the trees TV and Ty, corresponding to t", obtained by raising operations from Tu and Tw. Perform the same operations as in TV, and TV in To to obtain TV. Note that v is not pruned. Therefore, the ex- amples of E[(E,, rt)se(a) classified in the -ubttree of T are exactly E[(e,, r [4]]]] and analogously for TV Thus, the number of misclassifications in TV on (()eea)) is exactly t". Hence, the right-hand side of the recurrence is smaller or equal to the hent-hand side.
Proof. We prove the theorem by exploiting the witness tree algorithm of Komusiewicz et al. (2023b, Section 6.3). They present a method for enumerating decision trees with at most cuts with at most / errors in ((65max Dé(L + 1))²- (n) time. Roughly speaking, they utilize the concept of witness tree where decision tree is associated with function that associates one example ending up at each leaf as the witness of that leaf. The algorithm starts with a decision tree with only single leaf node. If there are more than t misclassifications, they arbitrarily pick a subset of + 1 errors. Since at least one of them has to be correctly classified, with branching, they obtain an element e which needs be correctly classified. Let be the current leaf of e. Now, a new cut is added to the tree that separates from the witness of v. By exploiting the fact that and the
B.2. Proof of Theorem 4.2
Proof Sketch. We use the almost the same definition of the table Q as in the proof of Theorem 4.1: Instead of defining
15

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
witness of u differ in most mas features and each feature has at most D thresholds, there are only 8 D possibilities for the cut. This process is then repeated at most l times. For more details, we refer the reader to the original work (Komusiewicz et al., 2023b).
by
1/ 0
blue
12 0
blue
blue
blue
1y S
blue
14 S 0
blue
For each tree enumerated by the algorithm, we need to test whether P can be obtained from the input decision tree T by pruning operations. If the roots of T' and /' are identical, then we keep the root of T and recursively continue to find Piett, the left subtree of P in Ten. the left subtree of T. and perform this analogously with the right subtree. If the roots are not identical, then we return the logical OR of finding P in the left subtree or the right subtree of T. This adds an additional factor of (Es) to the running time, making it ((66max + 1))² es) in total.
blue
blue
Fy S
Pn S
red
blue
de* S 0
blue
red
blue
Figure 7. Left: The initial decision tree used for Theorems 5.1 to 5.3 and 5.5. Right: The initial reasonable tree used for Theo- rems 5.1 to 5.3 and 5.5.
Correctness: If solution exists, then there is decision tree P with (at most) l cuts that makes at most errors. One of the decision trees enumerated by the witness tree algorithm of Komusiewicz et al. (2023b) is thus P. If no solution exists, the enumeration algorithm may still list some decision trees on (at most) l cuts that make at most I errors, but none of them can be obtained from the input decision tree T by pruning operations.
feature d' and we add one new blue example e, per vertex Example e, has value I in the feature corresponding to vertex v and in the new feature d'; in all other features (corresponding to any other vertex) e, has value 0. Also, we add a new blue example e for which ["[u] = 0 for v E V(G) and e*(d"] = 1 Furthermore, all existing examples have value 0 in d'.
Therefore, we need to show that our algorithm for testing whether P can be obtained from T works correctly. We prove this by induction. The base case of s = 1 is trivial. Suppose now the correctness for all s < 8'; we next show the correctness for s s'.
Second, extend the tree T, that is, we add new cut d' s 0 on the edge leading to the unique red leaf. More precisely, the left child of this node is the unique red leaf and the right child is a blue leaf, see Figure 7. Note that we still have xmax = 2, D 2, and 1 O.
If P can be obtained from T by pruning operations, then T has cut that is equal to the root of P. If does not have cut equal to the root of P. then the algorithm correctly outputs that P cannot be obtained from T. Assume now that T has such a cut. If is the root of T, then no other cut of T can equal the root of P because of reasonability. Therefore, we cannot prune the root, and the problem reduces to testing whether left (right) subtree of P can be obtained from the left (right) subtree of T by pruning operations. By the induction assumption, the algorithm performs this correctly.
For the correctness, observe that the new cut d' S can- not be pruned because of the new blue example e*. The remaining correctness proof is completely analog.
C.2. Proof of Theorem 5.2
Proof. We use the same initial reasonable decision tree as in Theorem 5.1, but instead reduce from k-PARTIAL VERTEX COVER (Guo et al., 2007), where we look for a subset of K vertices that covers at least e' edges of G. Unless the ETH fails, K-PARTIAL VERTEX COVER cannot be solved in [xx) o(x) time (Cygan et al., 2015). We let k, [(G) -t' and create the examples for edges as before. However, we copy the red example + 1 times to prevent pruming the red leaf. Now, if the remaining cuts after prun- ing correctly classify at least t' blue examples, then at most blue examples are misclassified. Additionally, we copy the example e also 1+ times, to avoid pruning the newly introduced cut d' < 0 to make the tree reasonable. Now, the ETH bound follows since f K.
Now assume instead that T has such a cut but it is not the root of T. Then, we need to prune the root of T and consequently also one of its subtrees. If P can be obtained from the left subtree, we can prune the right subtree, and vice versa. For both subtrees, the algorithm works correctly by the induction assumption, and thus the logical OR also outputs the correct answer.
C. Additional Material for Section 5
C.1. Adaption to Reasonable Trees for Theorem 5.1
C.3. Proof of Theorem 5.3
remains to show the statement for reasonable trees: First, we extend the classification instance. We add new binary
Proof. We use the same initial reasonable decision tree as in Theorem 1, but instead reduce from the W[2]-hard prob-
16

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
lem s-HITTING SET (Cygan al., 2015), where we look for subset of elements from the universe  that intersects with all subsets given in the input. Unless the ETH fails, K- HITTING SET cannot be solved in f fxs) n n=(()) time (Cygan et al., 2015). We let f = R and = 0. For the examples, we create one blue example e for each subset _ U in the input such that efu] = if u E and otherwise e[u] = for all E U. Additionally, we create one red example with elu] 0 for all U. Now, the ETH bound follows since e K.
subset of inner nodes has be an independent set. Addi- tionally, we copy the example e* also t + 1 times, avoid pruning the newly introduced cut d' S 0 to make the tree reasonable.
C.6. Proof of Theorem 5.6
We only show he statement for DTRAIS=. The statement for DTRAIS then follows by setting the lower bound l of the number of pruned inner nodes to the number of inner nodes of the input tree minus l (these values are specified later).
Proof.
C.4. Proof of Theorem 5.4
We reduce from MULTICOL.OED CLIQUE where each color class has the same number p of vertices. Formally, the input is graph G. and E IN, where the vertex set VGG) of N vertices is partitioned into Vi..... Vx and [V] = p for each E [x:]. More precisely, V == (u. ..?.....?]) " ".)-Th The question is whether G has contains a clique consisting of exactly one vertex per class V.. MULTICOLORED CLIQUE is W[l]-hard parameterized by K and cannot be solved in f(k) ox)) time unless the ETH fails (Cygan et al., 2015).
Proof. The training data set (F,, X) is shown in part a) of Figure& 8. More precisely, (E, consists of exactly k fea- tures and has exactly two red examples and 2 (k- 1) blue examples. The first red example has value 0 is each feature and the second red example has value 0 in each fea- tures, except feature di where it has value 1. Furthermore, for each; E [2, k|] we have a blue example with value 0 in each feature except feature d where the example has value and another blue example with value 0 in each feature cept features d and d where the example has value 1. The initial decision tree is shown in part 6) of Figure 8. Note that this tree is reasonable.
The property that all color classes have the same number of vertices is only used to simplify the proof.
The idea is to create two features di and d? per color class i such that in the pruned tree we need to preserve exactly one cut in each feature to fulfill the desired error bound. We achieve the property of exactly one cut per feature d' by adding huge number of blue forcing examples and red enforcing examples which can only be distinguished in d'. The two cuts in features df and d? force us to select exactly one vertex uiat of this color class. For each edge we create an edge example. If vertex eft is selected, then all edge examples corresponding to edges having an endpoint in color class i which is not v; will then be misclassified. Thus, we can only correctly classify an edge example if we select both endpoints of that edge. Furthermore, we ensure that only edge examples may be misclassified without violating the error bound. Hence, by setting t == m - (2). we ensure that we need to select a multicolored clique.
Outline:
On the one hand, if we perform exactly raising operations, we can prune the root of I' and wither its entire left or right subtree. The resulting decision tree has no errors. On the other hand, if we perform j raising operations for some 1 < j < k then we cannot prune the root of T. Without loss of generality, we assume that at least one raising operation is done in the left subtree of the root of T. Observe that the last cut dy S 0 cannot be pruned since then a red example ends up in a blue leaf. Similarly, no cut d; S for some 2 < i < k 1 cannot be pruned since then a blue example ends up in the red leaf. Consequently, exactly l raising operations are required.
[]]
C.5. Proof of Theorem 5.5
Proof. We use the same initial reasonable decision tree in Theorem 5.1 and reduce from K-NNDEEENDENT SET with an instance graph G. The blue examples for the edges are constructed similarly to the previous proofs but are dupli- cated [V) times. We create [?)) copies of the red example, and finally, construct one red example e for each feature u such that e(v) is 1 and other entries are zeros. By the construction, the initial decision tree has [V] mis- classifications.
Construction: We first show the statement for non- reasonable decision trees and afterwards we argue how the construction has to be adapted such that the input decision tree is reasonable.
Description of the data set: A visualization is shown in part b) of Figure 9.
For the instance of DTRAISZ, set L = IV(G)| - k. As a consequence, we have to prune at least & cuts to decrease the number of errors to On the other hand, if cuts cor- responding to both endpoints of an edge are pruned, we would create [VG)) new misclassifications, so the pruned
For each edge (of, of} E E(G) we add an edge ex- ample e(uf, vt).. To all these examples we assign la- bel red.
For each i E [x] and each a E [p - 1] we add a
17

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
a)
label
d
d2
dg
dg
di 2
blue
0
0
blue
0
da
blue
0
0
blue
dg 2
blue
ds
1|
red
0
0
blue
d:
blue
de 2
blue
!
0
blue
1
blue
blue
de }
dx >
blue
1
0
red
1
0
0
blue
red
blue
Figure 8. An instance for which pruning fewer than & cuts leads to misclassiffcations, with examples described by a) and the initial decision tree by b).
d)
45
d7
6)
blue
d5
<
blue
d5
1.5
3
1/2
B
B(e))
B(1,1) 1)
(
R Rest
blue
di
blue
d5 <
df Rest
R
F(e)))
B)1,))
F((
Bf
12
d5:
B2
E(e))
[(2, 1)
E((()
Rest
blue
d
blue
d3
d3: Rest?
R
E(+b)
B(2, 1)
E(v3)
B
V/1
1/2
B5 E((h))
B(3 1)
E(va)
R Restá
blue
blue
di
1/3
85
V/3
d Restý
R E2e5))
(33
E(v
B
4F
blue
d5
blue
red
blue
red
Figure 9. A visualization of the reduction from the proof of Theorem 5.6. a) shows a MULTICOL.ORED CLIQUE instance. A multicolored clique is depicted in brown. b) shows corresponding classification instance. Here, E(u?) the set edges incident vertex ef Hest, and Rest," refers all other examples not shown in that feature (the precise set differs in each feature and is always subset of all examples having default threshold that feature). Cuts the input tree are shown by "I" and cuts remain the optimal raised tree T" are depicted in brown. c) shows parts of the input tree T. d) shows the optimal raised tree T'.
set B(i, a) of separation examples. Each of these sets consists of m examples having the same value in each feature. To all these examples we assign label blue.
have 2 K. features.
It remains describe the coordinates of the examples in the features. Initially, we declare a default threshold default(d") for each feature d'. Then, each example has the default threshold each feature, unless we assign e a different threshold in that feature.
For each [k] we create sets B,, Bi of blue forcing examples. Each of these sets consists of examples and all examples in one of these sets have the same value in each feature.
For each feature df we default(d,)) = p. and for each feature dz default(d ( 0.
We create a set R of red enforcing examples. This set consists of examples and all examples in this set have the same value in each feature.
For each edge example = e(uf uf) we set eld;| eld;" a, and eld5] = el e(d} = b, e(d;] + 1. In each other features e is set to the default threshold.
Note that we add M |B()) edge examples, (p- 1). M < N.M separation examples, 2-x-M M < M forcing examples, and M enforcing examples. Thus, the number of examples polynomial in the input size.
For each separation example e E B(i, a) we set e[d;5] = c(d?) = a 1/2. In each other features e is set to the default threshold.
For each E [x), we add two features ds and d? and thus
For each forcing example e E B₁ we set eld;)
18

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
In each other features is set the default threshold.
sider euts of T in features where has different threshold than the default threshold.
For each forcing example e E B we set e[d]]] = p+11 In each other features e is set to the default threshold.
Step 2:
We distinguish the different example types.
For each enforcing example R we use the default threshold in each feature.
Step 1: Recall that each enforcing example e E R always has the default threshold. By Step I, each forcing example ends up in the unique red leaf and is thus correctly classified in T'.
Description of the inpul tree T: Intuitively, the input tree T is a path, where all leafs are blue except one leaf and we first have some cuts in df in ascending order, then some cuts in de in descending order, some cuts in d5 in ascending order, and so on. A visualization of T is shown in part c) of Figure 9. Since T' is path it is sufficient to present the order of the cuts from the root to the unique red leaf: (df < 1,..., di >> dx > 1). The left child of each cut is always a blue leaf and the unique red leaf is the right child of the last cut dæ > 1. Observe that T consists of p K N inner nodes.
Now, consider blue forcing example B,S.
Similar to the enforcing examples, we have E Eid5 < oz). By construction, e uses the default thresholds in each feature other than d, and in feature de, we have cld,] = 0. By Step and since a; > 0, e ends up in the left child of the cut d, a, which is a blue Icaf and thus e is correctly clas- sified in T". Analogously, we can show that all blue forcing examples in B, are correctly classified by T'.
1, df < 2, .......ff di < p, of > p, of >
1, dž
Thus, all enforcing and all forcing examples are correctly classified in T".
Error bound and f: Finally, we set / := M- (2) and 8 == 2 K. This completes our construction.
Step 2.2: Let e E B(i, b) be a blue separation example. By construction, e uses the default thresholds in all features except di and di Next, we distinguish the values of a; and b. Recall that 6 9+1/2 where q E IN and that ag E [p]. Thus, either b < a, or b > 0g.
Calculation of 6max. Observe that each enforcing example always has the default threshold, that each forcing exam- ple differs in exactly one features from the default thresh- olds, that each separation example differs exactly twice from the default thresholds, and that each edge example differs exactly four times from the default thresholds. Thus, 6max= = 6.
First, consider the case b < az. Then, e ends up in the left child of the cut dē < a, which is a blue leaf and thus e is correctly classified.
Second, consider the case b a, Then, e ends up in the right child of the cut di < a, which is the cut de > ag Now, e ends up in the left child of the cut df > a, which is blue leaf and thus e is correctly classified.
Correctness: We show that G has a multicolored clique if and only if T' can be raised to a tree T" having exactly l inner nodes making at most t = M - (?) errors.
(+) Let S = {of* : i E [x). ag [r]} be multicolored clique in G' (for example: see part a) of Figure 9). To obtain tree T' we preserve the cuts {d, < a, : E [m]) and {dp² > a; i E [x]]] A visualization of T is shown in part d) of Figure 9. In other words, T is doing the cuts (df < aj, df > a1, ds < K0z..... d² > a.). Clearly, T" consists of E 2 k inner nodes. Thus, it remains to verify that T' makes at most errors.
Hence, in T all separation examples are correctly classified.
Step 2.3: Let e = =(uft, ) be the edge example corre- sponding to an edge where both endpoints are contained in the multicolored clique S. Without loss of generality, we assume <.. Recall that uses the default thresholds in all features except di dd,, dd. and dj. Analogously, to all other example sets, Since e[d;5] 0g. ends up in the right child of this node which is the cut di >> a, Again, since e[d?] = a, e ends up in the right child of this node. Analogously, we can argue that e always end up in the right child of any cut in T" and thus e ends up in the unique red leaf.
obtain that E Eld5 < a.).
First, we make observation for examples using the default threshold in a feature and second we use this observation to show that 7' has at most t misclassifications.
Ouiline:
Step 1: Observe that if any example e lands at some in- ner node of T corresponding to cut in feature d' and has the default threshold in that feature d', that is, e[d") = default(d'), then will always go to the right subtree of that node. Since the pruned tree 7' is a path, an example e which has the default threshold in each feature will be contained in the unique red leaf of T which is the right leaf of the cut de > ag- Also, in order for an example e to land in a different leaf (which has label blue), we only need to con-
Hence, all edge examples corresponding to edges having both endpoint in the multicolored clique S are correctly clas- sified. Consequently, T" makes at most 1 = M - (*) errors.
(<= Let T" be a solution for the raising problem. that is T has l = 2 k inner nodes and makes at most t = - errors.
19

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
Oulline: First, we show that we need preserve exactly one cut per feature. Second, we show that the two cuts in the two features de and di need to have the form d, < a, and df > 0g for some a; E [p]. This value a; then corresponds to vertex uf of color class i. The union of these vertices is S. Finally, we verify that S has to be a multicolored clique.
form d, < az and d > a, for some as E [p].
By of we denote the vertex which is selected in color class i and by S we denote the set of these vertices.
Step 3: We now show that each red edge example corre- sponding to an edge where at least one vertex is not con- tained in S ends up in a blue leaf and is thus misclassified. As a consequence, S has be a multicolored clique fulfill the error bound of M (
Step 1: Assume towards a contradiction that T' does not preserve cut in each feature, and without loss of generality, assume that no cut in feature di is preserved in TV. Con- sider the red enforcing examples in R and the blue forcing examples in B, The examples in R always use the default thresholds and the examples in B use the default thresh- olds in all features except d5. Thus, examples in R and examples in _ can only be distinguished in feature d,S. Since T' does not preserve cut in feature d, all examples in RU S end up in the same leaf. Since R| = M = [85), we conclude that T has at least M > M - -2) = t er- rors, a contradiction. Thus, T' preserves at least one cut per feature.
Let = = vgg)) , be an edge example and assume without loss of generality that u,* & S. Recall that uses the default thresholds in all features except d,5, df .d5. and de. Let v be the vertex chosen in color class and assume without loss of generality that a; < b,. Now, consider the cut in feature di < by: since a; < b;. example e ends up in the left child of the cut d, < b, which a blue leaf and is thus misclassified.
Lower bound: Recall that d = 2 = l and 6max = 6. Since MULTICOL.OREI CLIQUE is W[1]-hard with respect to K (Cygan et al., 2015), we obtain that DTRAIS= is W[1]- hard with respect to d + E even if 6max 6. Further- more, since MULTICOLORED CLIQUE cannot be solved in f(x) (x(()) time unless the ETH fails (Cygan et al., 2015), we observe that DTRAIS= cannot be solved in [(d + f)- |/]o(d+z) time if the ETH is true, where |7] is the overall instance size, even if dmax = 6.
Since d = 2 ===6, E, we obtain that T' preserves exactly one cut per feature.
Step 2:
Assume towards a contradiction that the two cuts in features d5 and di do not have the form df < and di > a, for some ag E [p], that is, we assume the cuts have the form de < a; and di > b, with ag b, E [p] where either b, > 0; or b; < ag.
We do an analog adap- tion as in Theorem 5.1: First, we extend the classification instance. Basically, we add one example for each leaf in T which ends up in that specific leaf. For cut de < a; we add
Adaptation for reasonable trees:
First, we consider the case b, > ag. We show that all M many blue separation examples in B(i, a;) end up in the unique red leaf, implying that the number of errors in T" is at least M- > M- (2) = t, contradiction. Recall that each example e E B(i,as) uses the default thresholds in all features except di and d?. Thus, in each cut in a feature dš or d7 where j i i, e goes always to the right subtree of that cut. Hence, remains to consider the cuts in features di and di- By definition, e[dş] = a; + 1/2 e(d]"]. Since a; < a; + 1/2 < a, + < b,, we conclude that ends up in the right child of both cuts di < a; and di > bg. Consequently, ends up in the right leaf of the last cut in T' which is red, a contradiction.
an example such that e|d,5 = a, - 1, eld;] = p + 1 for each E [x] (i), and elds] 0 for each E [x]] For cut di > a, we add an example such that e|d.] p + 1 for each x E [K]], e[d?] = a, + 1, and eld?1 = 0 for each z E [M]] \ {e). Note that all enforcing examples end up in the unique red leaf.
Next, we add a new binary feature d' and we add (++1) new blue examples e* which have the same thresholds in all features. More precisely, e" has threshold in d and uses the default threshold in each remaining feature. All other existing examples have threshold O in the new feature d'. Example e, has value in the feature corresponding to vertex v and in the new feature d'; in all other features (corresponding to any other vertex) e, has value 0. Also, we add new blue example e* for which e" ["]] 0 for all u V(G) and e e*[d"] = 1 Furthermore, all existing examples have value 0 in d'
Second, we consider the case by < a,, Observe that for all examples e E Eid? b.] we have e(d?] 2 a, More precisely, only for the red edge examples having one end- point in ofth we have e e|d?' = a, and for all other exam- ples e' E Eld? > b,] we have e((d?] > a, Since the left child of the cut di > be is a blue leaf, we can replace threshold b, by threshold a; without increasing the num- ber of errors. Note that d? > a; is cut in the input tree between all cuts in feature de and df
Now, observe that the newly added cut d' < 0 cannot be pruned since otherwise the (1 + 1) newly added examples would be misclassified. Afterwards, the correctness can be shown analogously. Note that this adaption increased d
Hence, in the following can safely assume that for each E [x], the cuts in features de and d? have the
20

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
and e by one and does not change maxx
features and which have labels blue (separating examples) and red (choice examples) alternatingly. Hence, for each possible threshold z in features d, and di we either need to preserve cut (d5, ,x) or cut (d/, .x). Furthermore, for each edge create red edge example. If vertex uf V; is selected, then all edge examples corresponding to edges having an endpoint in color class i which is not v, will then be correctly classified by the pruned tree T". Thus, we can only correctly classify an edge example if we do not select at least one endpoint of the corresponding edge. Finally, we have another feature d' with only thresholds to ensure that all red choice examples corresponding to selected vertices are correctly classified by the pruned tree T" and that an edge example gets misclassified as blue if we select both endpoints of the corresponding edge.
C.7. Proof of Proposition 5.7
Proof. The proof is almost identical to the proof of Theo- rem 5.6 for both non-reasonable and reasonable trees. More precisely, we the same construction. Moreover, the (+) direction of the correctness works analogously. The (+) direction of the correctness is shown with the same three steps. Now, however, Step 1, that is, exactly one cut per feature is preserved, is more involved since we cannot exploit anymore that exactly 2 x cuts are preserved. After we have verified Step 1, the remaining proof works analo- gously. Thus, it remains to show that exactly one cut per feature is preserved.
Assume that in the resulting tree T at least two cuts in one feature are preserved. Without loss of generality assume that this is the case in feature d,s, that is, T" contains two cuts de < a and de < b for some a < Furthermore, assume without loss of generality that no other cut in di between a and b is preserved. Observe that all examples with e|d,5 < end up in a blue leaf and also all examples e!
Construction: We first show the statement for non- reasonable decision trees and afterwards we argue how the construction has to be adapted such that the input decision tree is reasonable.
Description of the data set: A visualization is shown in part b) of Figure 10.
with a S [e'] < b end up in a blue leaf. Since di < a is the parent of de < b in 7", raising di < leads to a smaller tree T" which misclassifies the exact same set of examples. By applying this argument iteratively, we obtain tree 7 with exactly one cut in each feature and thus Step is verified.
For each edge (17, vj) E E(G) we add an edge ex- ample e(u,", uf)). To all these examples we assign la- bel red.
For each i E [x] and each x E [p - 1] we add a blue separating example bli, x).
C.8. Proof of Theorem 5.8
For vertex of V; we create a red choice example ox.
Proof. We only show the statement for DTRAIS=. The statement for DTRAIS then follows since no more than & inner nodes can be pruned without having at least 1 error.
we create a blue forcing example b² and a red enfore- ing example r*.
We reduce from MULTICOLORED INDEPENDENT SET where each color class has the same number p of ver- tices. Formally, the input is a graph G. and K E N, where the vertex set V(G) of N vertices partitioned into Vi,..., VN and VV]l = p for each i E [x]. More pre- cisely, V;= = {u/ uf .......,.? e and p K N. The ques- tion is whether G contains of exactly one vertex per class V, MULTICOLORED INDE- PENDENT SET is W[1]-hard parameterized by x and cannot be solved in f(c) ((s)) time unless the ETH fails (Cygan et al., 2015).
Note that we add M == |E(G) edge examples, N choice examples, NN - K = (p 1) separating examples, and 2 further examples. Thus, the number of examples is poly- nomial in the input size.
For each E [K], we add two features dē and d? We also add another feature d'. Thus, we have 2 K + features.
independent set consisting
It remains to describe the coordinates of the examples in the features. Initially, we declare a default threshold default(d") for each feature d'. Then, each example has the default threshold in each feature, unless we assign e a different threshold in that feature.
As in the proof of Theorem 5.6, the property that all color classes have the same number of vertices is only used to simplify the proof.
For each feature d,s, we set default(d = p, for each feature d?, we set default(d?)) = 1, and for feature d', we set default(d") 2.
Outline: The idea is to create two features de and d:- per color class i such that the preserved cuts in the pruned tree T" correspond to a vertex selection in V,. We achieve this as follows: For each pair di and d? of features we create examples which can only be separated in these two
For each edge example e = e(v,", of) we set e(d; = e eld;- = I, cld5] = e[d}] = 2, and e(d'] = 1. In each other features e is set to the default threshold.
21

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
d)
1 1.5
a)
c)
47
1.5
45
1/
red
blue
42 1 2.5
blue
14 <
1/1
V/2
red
1/3
1/3
41 x
blue
45
blue
2.5
6)
1,5
2.5
red
Ar
2
red
62
45
E(v!)
K0,1)
B((
< b(1,2) B(v))) of Reatf
1.5
d7: Rest?
E(vt)]
60,1)
B((f)
6(1,2) E(vi) d
d5:
E(vg))
(221) (((5) <
Resty
4g >
red
d5: Reatz 64 E((2)) b22 B((5)
63
d5:
64 E(v)) | ((311) E(())
63
Reats
blue
blue
dg: Restz E(vg) 6(3, B(())
d": b" edge examples]
Rest"
blue
red
blue
red
Figure 10. A visualization of the reduction from the proof of Theorem 5.8. a) shows MULTICOL.ORED INDEPENDENT SET instance. the sake the illustration, the property that partite sets have same size is dropped. multicolored independent set is depicted orange. b) shows the corresponding classification instance. Here, ((u') is the set of all edges incident with vertex e/. Rest, Rest," and Rest" refers to all other examples not shown in that feature (the precise set differs each feature and is always subset all examples having the default threshold of that feature). Cuts of the input tree T' are shown by "I" and cuts that remain in the optimal raised tree '' are depicted in brown. c) shows parts of the input tree T. d) shows the optimal raised tree T".
For the separating example b(i, x)) we set e[dF]= =
1) 2x 1 Thus, h: (p (p-1) 2k. This completes our construction.
eld?"] = x + 1/2. In each other features e is set to the default threshold.
Calculation of 6max: Note that each edge example differs at most 4 times from the default thresholds, that each sep- arating and each choice example differs exactly times from the default thresholds, that 6* differs exactly one from the default thresholds, and that r* always has the default thresholds. Thus, 8max 6.
For the choice example = of we set e(df]] eld?] = In each other features e is set to the default threshold.
The red enforcing example r" has the default threshold in every feature. For the blue forcing example b*, we set b" [d*] = 1, and in each other feature we use the default threshold.
Correctness: We show that G has a multicolored indepen- dent set if and only T can be raised to a tree T" having exactly inner nodes making at most / errors.
(+) Let S {ot : [x], E [p} be a multicolored independent set in G' (for example: part a) of Figure 10). In the pruned tree 1", for each feature df preserve all cuts at thresholds x E {1.5, 2, 2.5, .p. for which x S 0;. Similarly, for each feature di we preserve all cuts at thresholds z E {1, 1.5, 2, 2.5, ....p 1/2) for which a; S æ. Further, we preserve the unique cut in feature d", In other words, in T" the cuts {df 1.5, di < 2,.... ........ df a1, di p - 1/2,..., di 01,---, d² ax d' 1} are preserved in that specific order. A visualization of T" is shown in part d) of Figure 10. Clearly, T" consists of f == (p 1) 2k + inner nodes. Thus, it remains to verify that T" makes no errors.
Note that each feature has at most 2p-1 different thresholds.
Description of the input tree T: Intuitively, the input tree T path and we first have the cuts in df in ascending order, then the cuts in di in descending order, the euts in d5 in ascending order, and so on, until the cut d' > 1. A visualization of T is shown in part e) of Figure 10. Since T' is path it is sufficient to present the order of
the cuts starting at the root: (df < 1.5, < 2, di < 2.5, ..5.....d5 df < p. > p- p- 1/2, di > p 1,....dy di > 1. 1.5.....dd di 1, 1). Let 11.1. For each E [x], the left child of the cut de xx+1/2 and the 1/2 is red leaf. Also, the right child of the cut d' > is red leaf. All remaining leaves are blue.
left child of the cut d?
Outline: First, we make an observation for examples using the default threshold in feature and second we use this observation show that all examples correctly classified by the pruned tree T"
Observe that T consists of (p- - 1) 4k + inner nodes.
Error bound and E: Finally, we set = 0, and & == (p-
22

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
Step 1: Observe that if any example lands some in- ner node of T corresponding has the default threshold in that feature d', that is, e[d"] = default(d""), ), then will always go to the right subtree of that node. Since the pruned tree 7 is a path, an example e which has the default threshold in each feature will be contained in the red leaf of the cut d= > 1, Also, in order for an ex- ample e land in a different leaf, we only need to consider cuts of T in features where has different threshold than the default threshold.
1.5 of T'. Also, recall that the next cuts in T" are d,
cut in feature d' and
2, 2,...: .. < a; in that specific order. Consequently, e goes to the left subtree of the cut di < + 1/2, which by construction is a red leaf. Thus, is correctly classified as red by T"
Consequently, the raised tree T' has no classification errors.
(+) Let T" be a solution for the raising problem, that is, T" has (p 1--1)))22 + inner nodes and has no classification errors.
Step 2:
We distinguish the different example types.
Outline: We first show that the unique cut in feature d' has to be preserved. Second, we show that at least on of the two cuts de < x and d? > x - 1 for each and each æ has to be preserved T'. Third, because of our choice of we then conclude that for each and each x exactly one of the cuts d5 < and di > x 1/2 has to be preserved. Fourth, we show that cuts preserved in a feature dī (or di²) ) do not have gaps, that is, if æ is the largest (smallest) threshold, such that the cut di < x (d² > x) is preserved in T', then also all cuts d, < 2 for each 2 < I (d? > 2 for each x < 2) have to be preserved in TV. Fifth, we use this solution structure to identify a selected vertex of each color class. Let S be the corresponding vertex set. Finally, we show that S has to be a multicolored independent set.
By construction, the red enforcing example r" always has the default threshold. Thus r" ends up in the right child of the last cut of T" which is a red leaf. Furthermore, the unique feature in which the blue forcing example b" does not have the default threshold is d'. Thus, 6* ends up in the left child of the last cut of T which is a blue leaf.
Step 2.1:
Thus, examples r* and b' are correctly classified by T".
Step 2.2: Consider a blue separating example e = b(i, 2). Recall that x + 1/2 and x E ip- 1] and recall that a; E N is the index of the selected vertex of color class i. Without loss of generality, assume that < a,, By Step 1, e will end up in the cut d5 < 1.5 of T'. Also, recall that the next cuts in T' are di < 2.....,d. de < 0; in that specific order. Consequently, e goes to the left subtree of the cut de < 2 + 1/2, which by construction is a blue leaf. Thus, e is correctly classified as blue by T'.
Step 1: Note that the blue forcing example b* and that the red enforcing example r* only differ in feature d², Since T has only one cut in feature d', in the solution T" the cut d' > has to be preserved.
Step 2.3: Consider red choice example e = of where & E [p].
Step 2: Our aim is to show that at least one of the cuts de < and di > - 1/2 for any i E [M] and ø E 11,,,,,25, .p.... has to be preserved in T', With- out loss of generality assume that æ is an integer. Note that x 2 2. By construction, for the blue separating exam- ple e = b(i, 1) we e = eld?] = x x-1/2 and for the red choice example e = of we have e(d,] = =[d?"] = z. Furthermore, note that b(i, 1) and cz have the default threshold in each other feature. Consequently, only the cuts d, < and di > and ci. Since T" has no classification errors, we thus con- clude that at least one of the cuts df < x and de > x - 1/2 has to be preserved in T".
First, consider the case that x * ag Then the argumentation is almost identical to the blue separating examples: Without loss of generality, assume that æ < az By Step 1, e will end up in the cut di < 1.5 of T". Also, recall that the next cuts in T are de 2........ de < a in that specific order. Consequently, e goes to the left subtree of the cut ds < 1/2, which by construction is red leaf.
1/2 of T can separate b(i, x (x--]] 1)
Second, consider the case that x = ag. Observe that in all cuts of T in features de and d?, example e will always go to the right subtree. Since e has the default threshold in each features different from d and di example e ends up in the right leaf of the last cut d'
Step 3: Recall that f = (p 1) 2x + 1. By Step 1, in T" the cut d' > has to be preserved. By Step at least one of the cuts de < Z and di > x - 1/2 for any e .P) has to be preserved in T". Note that these are exactly (p- - 1) 2x pairs of distinct cuts. Consequently, in T' exactly one of the cuts df < x and di > x - 1/2 has to be preserved.
T" which is a red leaf.
Thus, in both cases is correctly classified red by T'.
[<]] and æ E
Step 2.4: Consider a red edge example e = (uf,,)). By assumption, S is a multicolored independent set. Hence, at least one of the two endpoints of' and v5 is not contained in S. Without loss of generality, assume that of & S and that i < j. The argumentation is analog to the red choice examples of where * aş: Without loss of generality, assume that < a, By Step 1, e will end up in the cut di
Step 4: Consider all preserved cuts in feature ds Let de xr be the rightmost preserved cut in feature dj that is, for each > 2. the cut dī < is pruned. We claim that in T"
23

---

Optimal Decision Tree Pruning Revisited; Algorithms and Complexity
all cuts d,5 < z for any = S x have be preserved. Without loss of generality, we assume that is an integer. Since all blue separating examples and red choice examples with threshold w S in feature di have the default feature in all features except d and d and since all cuts in feature d, appear before the cuts in feature de in I and thus also in T", we conclude that all these examples end up in a left leaf of one of the cuts di 2 for some 2 S z. Now, observe that in feature d. the examples ct, b(i, ..,,....."..... b(i, x 1) have strictly monotone increasing thresholds and have alternating labels red and blue. Consequently, all cuts of the form de <> z for each z S x need to be preserved in T".
and [ 0. Furthermore, since MULTICOLORED INDEPEN- DENT SET cannot be solved in f(s) no(x) time unless the ETH fails (Cygan et al., 2015), we observe that DTRAIS=
cannot be solved in f(d) : |2j((() time if the ETH is true,
where [1] is the overall instance size, even if 6max = 6 and f = 0.
Adaption for reasonable trees. Note that some leafs cor- responding to cuts in feature di- are not reached by any example. To make the tree T reasonable we do similar adaption as in Theorem 5.1: For each leaf L of a cut in feature di (or d,²) we add a new example which e which uses the default threshold in all features except (a) in di (or de ) and (b) in d', where e[d*] = 0, if leaf L is blue and otherwise if T. red, then e(d') = 1. Observe that the correctness can be shown analogously to the non-reasonable case.
By the above argumentation and Step 3, we conclude that in feature d? all euts of the from d? > z for each = > x are preserved in T".
Step 5: Consider one fixed i E [x]] Let æ; be the largest threshold such that the cut d5 < I; is preserved in T'. Re- call that according to Step 4 all cuts di < z for any 2 S x; are preserved in T". Assume towards a contradiction that æ is no integer, that is, I, = + 1/2 for some in- teger q E [p- - -]] Now, observe that the blue separating example b(i, q) is put in the right subtree of each cut d, z for each 2 S r; and for each cut d? > for each 22 S Also, since b(i, g) has the default threshold in each other feature, we conclude that in T' this example b(i, q) ends up in the right leaf of the last cut d= > 1 of T' which is a red leaf. Thus, b(i, q) is misclassified, a contradiction. Hence, 2, is an integer.
D. A Additional Material for Section 6
Our empirical study aimed to assess whether common decision-tree tree pruning heuristics achieve optimal tradeoffs between pruned nodes and classification errors. This is made feasible using the algorithmic and complexity analysis in the preceding sections. To this end, we selected benchmark instances used for computing minimum-sie trees, as they would likely be suitable for exact algorithms for pruning trees as well. We computed unpruned and pruned trees us- ing the WEKA library. We then took the unpruned trees and computed the whole Pareto front that contains for each num- ber k of pruned nodes, the minimum-possible classification error of the resulting pruned tree. Then we compared the Pareto front to the trade-offs chosen by the heuristics.
We let ofth be the selected vertex of color class i. Further- more, let S = (uffh i [x]]]
Step 6: It remains to verify that S is multicolored inde- pendent set. By definition, S contains exactly one vertex of each color class. Hence, it remains to show that S is an independent set.
We used 40 datasets from the Penn Machine Learning Benchmarks library (Romano et al., 2022). 35 of the datasets were used before for computing minimum-size trees (Bessiere et al.. 2009; Narodytska et al., 2018) and since the number of examples was usually small we added further larger datasets. Overall, the datasets range from 72 to 5404 examples (mean 674.88, median 302); for the full details, see Table 2. To meet the requirements of DTRAIS_ inputs, we transformed the data sets as follows (similarly to Janota & Morgado (2020)): First, we replaced each cat- egorical feature by a set of new binary features indicating whether an example is in the category. Second, we con- verted each instance into a binary classification problem by making two classes, one of which contains all examples of the largest original class and one which contains all remain- ing examples. Finally, if two examples of different classes had the same value in all features, we removed one of them arbitrarily.
Observe that since T" has no classification errors, it is suffi- cient to show that an edge example e (vff of) gets mis- classified by T' if both endpoints of and vž are contained in S.
c= =(ef, uff) be an edge example where uJ E S.
Note that analog to Step 5, the red edge example e ends up in the right subtree of each preserved cut in features df., df.
df. and dz. The same is true for each feature dī and di for each g E [x] \ {i since in these features e has the default threshold. But in feature d' example e has not the default threshold, and thus e ends up in the left leaf of the cut d' < which is a blue leaf, a contradiction.
Lower bound: Recall that d 2- x + 1, Smax = 6, and f O. Since MULTICOLORED INDEPENDENT SET is W[I]- hard with respect to k (Cygan al., 2015), obtain that DTRAIS= is W[l]- with respect to d even if 8max 6
We computed unpruned and pruned trees using the C4.5 heuristic for decision -ttee computation (Quinlan, 1993)
24

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
implemented WEKA 3.8.5 (Frank al., 2010). The pruned trees obtained by running WEKA's J48 clas- sifier with the flags -nocv -B -M 0 -J -U. We ob- tained two types of pruned trees: Those obtained by the replacement heuristic implemented in J48 when run with the flags no-cv -B -M -J -S and those obtained by the raising heuristic, corresponding to the flags -no-ov 0 -J. Overall, the size ranges from 607 (mean 60.57, median 26); the number of features d ranges from 2 to 88 (mean 12.00, median 9); the domain size D ranges from 1 to 321 (mean 15.55, median 6); the maximum number of features dæ on a root-to-lcaf path ranges from 2 to 34 (mean 7.88, median 8); the number of classifica- tion errors ranges from 0 to 302 (mean 25.17, median 4). These ranges show that, indeed, parameters d, D, dr are suitable for designing fixed-parameter algorithms. For the full details, see Table 3.
We implemented a dynamic-programming algorithm for solving DTRAIS= based on Theorem 4.2 in Python, tested with versions 3.6.9 and 3. 1... We ran the implementation under Ubuntu Linux 18.04 on compute cluster with Intel Xeon E5-2640 processors, setting a maximum RAM limit of 64GB. We ran the algorithm for each dataset together with its unpruned tree to obtain, for each number A of pruned nodes, the least number of classification errors. After at most 24h of running time, 26 of the 40 datasets (65 %) could be solved.
25

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Table 2. Dataset statistics.
Dataset
Examples
# Features
Class
Class
Class Ratio
appendicitis
106
7
85
21
0.25
australian
690
18
383
307
0.8
backache
180
155
25
0.16
banana
5300
2
2924
2376
0.81
biomed
209
14
75
134
1.79
breast-cancer
266
31
188
78
0.41
bupa
341
5
168
173
1.03
cars
392
12
147
245
1.67
cleve
302
164
138
0.84
cleveland
303
139
164
1.18
dlevland-nooine
130
69
1.13
colic
357
75
134
223
1.66
contraceptive
1358
21
764
594
0.78
dermatology
366
129
254
112
0.44
diabetes
768
8
268
500
1.87
ecoli
327
7
184
143
0.78
flare
1066
10
884
182
0.21
glass
204
128
76
0.59
glass2
162
86
76
0.88
haberman
283
3
73
210
2.88
hayes-roth
84
15
59
25
0,42
heart-c
302
27
138
164
1.19
heart-h
293
29
106
187
1.76
heart-statlog
270
150
120
0.8
hepatitis
155
123
32
0.26
WillVaalllyw
1212
100
600
612
1.02
hungarian
293
29
187
106
0.57
ionosphere
351
34
126
225
1.79
lupus
86
3
52
34
0.65
lymphography
148
50
67
81
1.21
molecular www.ooyyppromoteee.. prromoters
106
228
53
53
1.0
new-thyroid
215
150
2.31
phoneme
5404
3818
1586
0.42
pima
768
500
268
0.54
72
22
50
22
0.44
schizo
340
14
140
200
1,43
soybean
622
133
545
77
0.14
tae
106
5
71
35
0.49
titanic
2099
1418
681
0.48
tokyol
959
346
613
1.77
26

---

Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Dataset
Size
Dimensions
Dim. da on Path
Domain D
Errors
Error Ratio (%)
appendicitis
15/ 10/ 10
6/ 6/
5/ 5/
5
5
31
3
0/
2
0.00/
1.89
1.89
australian
90 46/
44
13 11/11
10/ 10/
9
29
11
11
0/
22
23
0.00/
3.19/
3.33
backache
26 13 13
131
9/
91 6/ 6
7
2/
2
0/
7
0.00/
3.89
3.89
banana
607 186
188
2/ 21
321
107
108
1/249
246
0.02/
4.70/
4.64
biomed
21
13
6/ 3/
3/
6/
0f
15
0.00/
7.18/
1.44
breast-cancer
95 31/ 24
25/21/17
14/10/ 9
81
6/
5
2/
31
33
0.75 / 11.65
12.41
hupa
111 727 65
51 51
51 5/ 5
21
18/
14
0F
25
28
0.00 7.33/
8.21
cars
22.1 15 15
71 71
51 5/
7/
5/
5
0/
31
0.00/ 0.77
0.77
cleve
29.1
13/13/13
12/
OF
15
15
0.00/ 4.97
cleveland
5 31/
16/13/15
8/ 8/ 8
10/
6/
6
OF
131
13
0.00/ 4.291
4.29
cleveland-no...
46/ 8 8
15/ 8/
10/ 5/ 5
1/
1/
6/
23
23
4.62 /9.617.69// 17.69
colic
51 28/ 28
27 27/18/18
9/ 8/ 8
6/
4/
4
0F
15
15
0.00/ 4.20/ 4.20
contraceptive
486 /20/ 106
21/21/21
13/11/11
33/
21
10/
0.74 15.98 16.49
dermatology
5/
41 3/ 3
1/
OF
0.00 0.55/ 0.55
diabetes
137 967 87
81 8/ 8
81 8/ 8
24
16/
14
0/
24
30
0.00 3.12/ 3.91
ecoli
25 5/ 5
51 3/
41 37
3
11/
2/
2
0F
10/
10
0.00 / 3.06 3.06
flare
93 15 12
81 71
81 71 6
5/
4/
125
159
160
11.73 14.92 15.01
glass
28 26/
71 71
0/
1/
0.00/ 0.49
glass2
22 16/
14
61 5/
5
51 41
6/
5/
OF
4/
0.00/ 2.47 3.09
haherman
92 21 18
3/ 3/
31 31 3
30/
9/
8
2/
38/
39
0.71 13.43 13.78
hayes-roth
14/ 12/
12
11 /
10
10/10/10
1/
1/
OF
1/
0.00/ 1.19/ 1.19
heart-c
57 29/
13 13
9/ 8/
12/
5/
0/
15
15
0.00/ 4.97
4.97
heart-h
32/
20/ 18/18/11
13/11/10
13
OF
14
14
0.00/ 4.78/
heart-statlog
54 27 23
17/13/15
10/10/ 9
13/
7/
6
0/
15
17
0.00/ 5.56/
6.30
hepatitis
187 12/ 11
10/ 9/ 8
71 6
3/
2/
2
OF
31
0.00/ 1.94
2.58
Hill_ Valley...
2 224
88 85 84
34/34/33
63
47/
47
0F
11 13
0.00/ 0.91
1.07
hungarian
57 32/
19 /9/18
13/11/10
13/
0/
14/
14
0.00/ 4.78/ 4.78
ionosphere
21 197 19
12/11/11
91 9/
4/
4/
0F
1/
0.00/ 0.28
0.28
lupus
25 41
21 21
21 21 2
20
2/
2
0/
13/
13
0.00 / 15.12/ 15.12
lymphography
23 14/ 14
18 11
10/ 6/ 6
1/
1/
OF
51
0.00 / 3.38/ 3.38
molecular b...
12 10/ 10
11/ 9/
6/ 5/
1/
0/
1/
0.00/ / 0.94/ 0.94
new-thyroid
5/ 5/
0F
21
0.00/ 0.93/
phoneme
/04/341
343
51 51
51 51 5
159
99
100
0/
981
95
0.00/ 1,81/
1.76
pima
137 96. 87
8/ 8/
8/ 81 8
24
16/
14
0/
241
30
0.00/ / 3.12/
3.91
postoperativ...
23 21/ 20
13 13/13/11
10/
1/
1/
1
0/
1/
0.00/ 1.39
1.39
schizo
83/ 69 66
12
10/10/ 10
15/
10/
0/
8/
0.00/ 2.35
2.65
soybcan
137
13
22 12/12/12
10/
1/
1
0F
8/
0.00/ 1.29
1.29
tae
41
21
21
5/ 51
51 5/ 5
13
71
7
0/
11
11
0.00 / 10,38
10,38
titanic
336
61
63
8/
87
8
81 71
7
61
/
20
19
157 /
302
296
7.48 14.39
14.10
tokyol
46
34/
33
24
24/22/11
22/11
16/16/11
10
5
5
0/
6/
0.00 0.63 0.73
Table 3. Decision trees used in our experiments: The first entry is for the unpruned tree, the second for the tree computed by the replacement heuristic and the third for raising heuristic.
27


Reviews:
[{"review_id": "gDl40t0SVt", "reviewer": "Reviewer_iXCd", "summary": "The submission at hand aims at understanding the parameterized complexity of problems relating to editing decision trees to conform to a data set up to a bounded number of errors. The considered operations are either of raising and replacing and the considered parameters are numbers given on input, relate to the size of the input or relate to the number of features with certain properties. Apart from few specific combination the obtained parameterized complexity theoretic classification is exhaustive with respect to the combination of all considered parameters and utilizes a number of maybe not particularly groundbreaking but diverse and well applied algorithmic techniques and hardness reductions.\nThe theoretical results are complemented by a small empirical section on the quality of common heuristics for minimizing a number of edits given a certain error budget. These experiments might weakly indicate some weaknesses of the considered heuristics that deserve further investigation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review and the helpful feedback! \n\nWe now make clear in the introduction that we focus on binary trees and incorporated the comment about line 417.\n\n\n\n> Which of these results can be adapted when allowing both replacing and raising?\n\n\nThat’s an insightful question. While the details depend slightly on how the problems are formulated (e.g., do we have a budget for each operation on how many cuts should be pruned or do we only care about the total number), our algorithmic and hardness results for the raising operation are generally adaptable to support also the replacement operation. \nAs to hardness, observe that in our reduction for showing the hardness of the raising problem (Theorem 5.1), each subtree rooted at an inner node has both a blue and a red leaf. Thus, a replacement operation on an inner node that replaces it by a red (correspondingly, blue) leaf can be simulated by a sequence of raising operations that raises a red (blue) leaf of the subtree in the place of the inner node. Consequently, allowing also replacement operations does not make the problem any easier or harder. \nFor our algorithms, we would need to adapt the dynamic programming recurrences to take into account the possibility of replacing the whole subtree, but other than that the details are similar. More precisely, recurrence (1) of the proof of Theorem 1 now has a fourth case to consider a tree replacement operation.\nIn summary, allowing both replacement and raising would yield hardness and tractability results similarly to when allowing only raising operations.", "claims_and_evidence": "No concerns.", "methods_and_evaluation_criteria": "Appropriate.", "theoretical_claims": "I had at least a superficial look at all proofs and am convinced by their correctness up to minor details.", "experimental_designs_or_analyses": "I only read what is not in the appendix.", "relation_to_broader_scientific_literature": "This submission studies the complexity theoretic behavior of a problem relevant to ML. There have not been extremely many papers like this on this specific kind of problem but there is much precedent of similar analyses for a range of problems.", "essential_references_not_discussed": "None that I am aware of.", "other_strengths_and_weaknesses": "Overall, this submission is topically relevant and solid in terms of its contributions and presentation. I recommend acceptance.", "other_comments_or_suggestions": "- Maybe specify that you assume decision trees to be binary\n- Line 417(right): replace both operations by each operation", "questions_for_authors": "Which of these results can be adapted when allowing both replacing and raising?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SuCWWWAjAU", "reviewer": "Reviewer_mGs2", "summary": "This manuscript analyzes the complexity gap between two tree pruning strategies: subtree replacement and subtree raising. The former is polynomially solvable, whereas the latter is NP-complete. This paper identifies the key parameters that can bridge the gap between these strategies and analyze their impact, providing precise boundaries between tractable and intractable cases. At last, some numerical experiments are utilized to validate the theorems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback! Allow us to respond to all your concerns:\n\n\nPresentation:\n\n- Theorems in Section 4 and 5: Note that all of these theorems correspond either to different combinations of parameters or different subsets of parameters that are fixed to at most some constant value. We have invested quite a lot of time into how to present them in an accessible way; Figures 2 and 3 are highly condensed versions of the statements that still convey most of the information. We feel that merging the statements into one would indeed decrease the readability since it would be more difficult to match the proofs to the corresponding statements.\n\n- The $V$ in $w \\in V(T)$ is a common notation for the vertex set of the tree $T$; we have clarified this.\n\n- The domain size $D$ is the maximum number of different values that a feature can attain, we have also clarified this.\nWe have already incorporated your specific feedback into our local version of the submission and will ensure that the presentation of the final version is as accessible as possible.\n\n\nPareto-front: \n\n- We indeed correctly compute the Pareto front or, more precisely, for each $k$ the point $(t, k)$ such that it is possible to prune exactly $k$ nodes to achieve exactly t errors and every solution with at most $k$ pruned nodes has at least $t$ errors: Any algorithm solving the search problems DTRAIS=> and DTRAIS= can also be applied to finding the optimum values for the corresponding optimization problems (see also the introduction). That is, with such an algorithm we can minimize the number of errors for fixed number $k$ of pruning operations simply by incrementing the error parameter $t$, starting with 0, until the algorithm returns a solution. Solving these optimization problems for all $k$ will yield the Pareto front. Since our algorithms provably solve the search problems correctly, we are certain to find the optimum values. We will emphasize this more clearly in the final version.\n\n\nDatasets:\n\n- Indeed, it would be desirable to extend the experiments; however, this is out of scope for the current paper where we mainly want to develop the fundamental theory. Thus we leave this for future work.\n\n- We agree, it would be good to add more info from the appendix to the overview of the datasets given in Section 6. If the paper were to be accepted, we would be happy to utilize the extra page for this purpose; in any case, we will make a full version available on arxiv or another public repository.\n\n\nBiclass vs. multiclass:\n\n- The focus on the biclass setting is for clarity of the theory. All our hardness results directly apply to the multiclass setting. All our dynamic-programming algorithms and the algorithms for Lemma 4.4 and Theorem 4.5 also directly apply to the multiclass setting without changes. The algorithm for Theorem 4.6. can easily be adapted to the multiclass setting without changing the running time: In the tree-enumeration algorithm, when introducing a new leaf, we set the leaf to the class of the dirty example. The remaining algorithm remains the same. The algorithm in Theorem 3.1 can straightforwardly be adapted to the multiclass setting: In the first step we instead compute, for each node in the tree and each class $c$, the number of misclassified examples in this node, if the node were to be replaced by a leaf with class $c$. The rest of the algorithm remains the same.", "claims_and_evidence": "Most of the claims are relatively well-supported but not very clearly presented. Some of the theorems discuss the same concept under different conditions, particularly in Section 5. The authors could consider combining them into a single, more comprehensive theorem to cover all these cases for greater clarity.\n\nAdditionally, there is one claim about the Pareto front is not well analyzed. The authors do not specify the multi-objective optimization method used to obtain the Pareto front. Since the pruning problem is an integer programming problem and non-convex, how do the authors ensure that the solutions are (even approximately) Pareto optimal and that the Pareto front is complete? Without a proper analysis, the Pareto front may be inaccurate, leading to potentially incorrect conclusions.", "methods_and_evaluation_criteria": "Yes, the pruning strategy is an effective way to improve the performance of decision tree models. The relationship between complexity and accuracy has always been a key concern for researchers. This paper analyzes two pruning strategies and provides valuable insights into reducing complexity.", "theoretical_claims": "The authors provide extensive analysis to illustrate and prove the theorems. However, some theorems and lemmas could be combined—for instance, Lemma 4.4, Theorem 4.5, and Theorem 4.6, as they all discuss the time complexity of $DTR_{AIS_{\\geq}}$under different conditions. It is recommended to consolidate them into a single theorem for clarity and conciseness. A similar issue exists in Section 5, which analyzes whether $DTR_{AIS_=}$ and $DTR_{AIS_{\\geq}}$ are solvable (time complexity) under different critical parameter conditions and the ETH assumption.", "experimental_designs_or_analyses": "The experimental analysis in this paper is not very strong. If the contribution of this work is to demonstrate that a better solution exists for both error minimization and complexity compared to current methods, the authors should focus more on multi-objective optimization, as this issue stems from non-Pareto optimality.", "relation_to_broader_scientific_literature": "This paper contributes to the complexity analysis of pruning strategies, specifically, subtree replacement and subtree raising. These strategies enhance the performance of decision tree models and can be applied to various heuristic approaches such as CART and C4.5.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strengths:\n1. This paper provides interesting insights into the complexity of two pruning strategies, which are useful for improving the performance of decision tree models.\n2. Figures 1, 2, and 3 are well-designed and effectively facilitate the understanding of the results.\n3. The supplementary materials include historical results.\n\nWeakness:\n1. Throughout the paper, the mathematical expressions are not well expressed. This may stem from the problem statement being somewhat difficult to understand and some notations being unclear. Certain notations remain abstract and require further clarification—for example, the domain size $D$.  Additionally, in the first paragraph, the expression $w\\in V(T)$ appears. What does $V$ represent? Please ensure that every symbol is clearly defined and well explained.\n2. The appendix contains some typos, such as the first line of C.6, \"We only show the statement for...”. Please check the appendix.", "other_comments_or_suggestions": "1. In Table 1, information about the datasets should be provided (rather than in the appendix), including the number of samples, features, and classes. Although misclassification is used as the objective, it is recommended to report its percentage to give a clearer sense of the error magnitude.\n2. The relationship between complexity and accuracy (misclassification errors) can be represented by the Pareto front, which may reveal certain patterns, as demonstrated with the Soybean dataset in Figure 10. However, only a few datasets are analyzed. There may be underlying rules that can be extracted from the Pareto fronts.", "questions_for_authors": "Why do you focus on bi-class problems? What will the results change in multi-class problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MODNw1glM1", "reviewer": "Reviewer_x5E5", "summary": "Decision trees are widely used for tabular datasets. The authors conduct a comprehensive analysis of decision tree pruning operations, including subtree replacement and subtree raising. The paper provides a theoretical analysis of the complexity of each pruning operation, showing that optimal subtree replacement can be achieved in polynomial time and runs linearly in tree size. In contrast, optimal subtree raising is proven to be an NP-complete problem, making it significantly more computationally expensive. The study includes detailed theorems and proofs to support these findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and the insightful questions!\n\n1) About the concern about the practical value of using the optimal strategy:\nPrior to our work there was no evidence how good these heuristics work in practice, that is, whether they are close to the optimum, or whether they can be outperformed substantially in quality.\nOur efficient exact algorithms made such an evaluation feasible. Moreover, only with the help of our algorithms such a conclusion that the heuristics are almost always optimal was possible.\nAs shown by our hardness results, this is quite surprising and in the future one should investigate this phenomenon further, that is, find explanations as to why these heuristics are so good on these data.\n \n2) Almost linear tradeoff between the number of pruned nodes and the misclassification error:\nWe feel that the intuition of a linear tradeoff might be misleading. Consider Figure 10 in the appendix, where an alternative interpretation is that the relation is rather exponential: Intuitively, pruning one node has a smaller impact in a decision tree of size s than in a tree of size 1. Thus, initially, there is an almost linear dependence on number of raised nodes and classification error, but after a certain barrier the number of errors increases exponentially (as the soybean dataset highlights). This is due the fact that the initial tree is likely overfitting and thus raising a few nodes only leads to few errors but after a certain barrier not enough nodes are left and thus the data cannot be explained anymore, leading to many errors.\nConsequently, we don’t think there is an inherent limitation of these operations. Essentially, one should use them only to eliminate overfitting.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "- Both Table 1 and Figure 10 illustrate the tradeoff between the number of pruned nodes and misclassification error. The results suggest that the heuristic method often appears on the Pareto front constructed by the proposed dynamic programming method, and the conclusion acknowledges that the heuristic is usually sufficient. If the heuristic method already achieves competitive performance with significantly lower computational cost, what is the practical value of using the optimal strategy? The optimal pruning strategy does not seem to provide meaningful performance gains while being more computationally expensive.\n- In the optimal tree literature, simple and accurate trees are typically found through search-based methods, and there is not necessarily a tradeoff between simplicity and accuracy. However, in this study, even optimal subtree raising seems to have an almost linear tradeoff between the number of pruned nodes and the misclassification error. Does this suggest an inherent limitation of the subtree raising operation itself? Or does this indicate that the tree induction method is not a good option in the first place?", "theoretical_claims": "The authors provide precise complexity classifications for pruning operations. The claims are supported by detailed proofs.", "experimental_designs_or_analyses": "Please see above.", "relation_to_broader_scientific_literature": "Pruning strategies date back to the origins of tree induction methods (Breiman 1984, Quinlan 1986), where they were introduced to simplify trees and prevent overfitting. This paper presents a comprehensive theoretical analysis of the complexity of different pruning strategies and compares heuristic pruning methods with optimal ones. The paper also relates to the literature on sparse decision trees, which aims to achieve both accuracy and simplicity simultaneously.", "essential_references_not_discussed": "The paper appropriately discusses the related works.", "other_strengths_and_weaknesses": "Please see above.", "other_comments_or_suggestions": "NA", "questions_for_authors": "Please see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KqSyoRCQen", "reviewer": "Reviewer_dtvc", "summary": "The authors investigate the computational complexity of pruning a decision tree. \nMore specifically the focus is on the algorithmic optimization of two pruning techniques: replacement (removing a subtree and assigning to the root the majority class in the leaves) and raising (removing the subtree rooted at an internal node and substituting it with the subtree rooted at one of its children). The study is on whether there are efficient algorithm that given a maximum number of internal nodes to remove can obtain a pruned tree with at most a given number of misclassification. Parameterized complexity is investigated with respect to single parameters and their combinations.\n\n## Update after rebuttal\nI kept my already positive score since there was no additional information from the authors that justified in my opinion an increase.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\nIndeed, we agree that $n^{2d}$ running time would not scale to practical data and this is in particular why we need more precise complexity and running time analyses such as those we provide here. To add to these considerations, note that the implemented algorithm instead of $n^{2d}$ has an exponential running-time part limited by $D_T^{2 d_T} \\le D^{2 d_T}$, where $D_T$ and $d_t$ are smaller than $n$ and $d$, respectively, see below:\n\nThe maximal number $D$ of thresholds per feature is often much smaller than the number of examples $n$; see Table 3 of Staus et al. (2024, https://arxiv.org/abs/2412.11954) for concrete values. Moreover, often the features are only binary implying that $D=2$. On average, $D$ is smaller than $n/2$.\n\n$D_T$ is the maximal number of different thresholds on cuts in feature $i$ on path $P$ over all features $i \\in [d]$ and all root-to-leaf paths $P$. This parameter $D_T$ is much smaller than $n$: In our Table 3 in the appendix we measured $D_T$ for both the unpruned and the pruned trees (there is a typo; the column says $D$ but it should be $D_T$). Together with the values for $n$ from Table 2 we can see that $D_T$ is usually much smaller than $n/10$, in fact in more than half of the instances $D_T< 15$.\n\nAdditionally, the exponent in the running time only depends on $d_T$, the maximal number of different features per root-leaf path, which is usually much smaller than $d$; again, see our Tables 2 and 3.\n\nWe will emphasize this more in the next version of the paper.", "claims_and_evidence": "The mathematical claims are soundly supported by the analyses presented.", "methods_and_evaluation_criteria": "The paper presents a theoretical investigation.\nThe experimental analysis is meant to investigate practically used heuristics with respect to the possible optimization of number of pruning operations and resulting misclassifications allowed. These evaluations is meaningful", "theoretical_claims": "I checked the proofs in section 4. Both the DP arguments appear correct.", "experimental_designs_or_analyses": "The esperiments are meant to provide evidence that the commonly used heuristics are not far from the optimal results given by the DP algorithms. As claimed by the authors it is a small scale study but, nonetheless provide interesting information.", "relation_to_broader_scientific_literature": "The paper appears to take into consideration the relevant papers. In fact, the perspective proposed is, to the best of my knowledge, novel.", "essential_references_not_discussed": "I have no comments on this", "other_strengths_and_weaknesses": "The paper present a novel perspective on decision tree optimization, from the point of view of pruning.\nThe hardness results are in my opinion not so surprising.\nThe DP algorithms are interesting with respect to the idea that in practical cases the number of different thresholds used per feature is small. I think some more should be---maybe experimentally---argued about this point. \nHowever, the complexity attained is significant only with respect to such assumption, since, in practice, could become proportional to nˆ2d.", "other_comments_or_suggestions": "--", "questions_for_authors": "Can you elaborate a bit more on the fact that the parameter D does not explode in practical cases?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers suggested acceptance so I will concur with them. That said, I think the results are technically interesting but of narrow impact. The fundamental reason for a-posteriori pruning a CART-style decision tree is that CART doesn't optimize a loss function over the tree, and one gets better trees (with lower generalization error) by growing them very deep (so they overfit) and then pruning them. If pruning is defined as subtree replacement, the traditional and widely used algorithm (CART cost-complexity pruning) solves this exactly and efficiently. I think it is unlikely that other forms of pruning (with more difficult pruning operations, such as subtree raising) will improve much the performance in practice, and the small experiments in the paper don't clarify this. It would be useful to readers if the authors comment on the practical impact of their results in their "Outlook" section.

A recent line of work not discussed in the paper is based on Tree Alternating Optimization (TAO). This makes it possible to optimize a loss function plus sparsity regularization (converging to a local optimum) and it scales to large sample sizes and feature dimensionality and large trees (unlike dynamic programming or MIO approaches). Pruning happens during training automatically as a result of the sparsity regularization.
Decision: Accept (poster)