Improving Decision Trees through the Lens of Parameterized Local Search
Authors: Juha Harviainen
Frank Sommer
Manuel Sorge
Venue: NeurIPS 2025 poster ()
Keywords: efficient algorithms
running time lower bounds
dynamic programming
threshold adjustment
cut exchange
node disturbance
Primary area: theory

Abstract: Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing a fixed number of a single type of these operations. Although we discover that the corresponding problems are NP-complete in general, we provide a comprehensive parameterized-complexity analysis with the aim of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for a small number $d$ of features or small domain size $D$ but the combination of both yields fixed-parameter tractability. That is, the problems are solvable in $(D + 1)^{2d} \cdot |\mathcal{I}|^{O(1)}$ time, where $|\mathcal{I}|$ is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.

Improving Decision Trees through the Lens of Parameterized Local Search
Juha Harviainen"
Frank Sommer'
Department of Computer Science
Institute of Computer Science
University of Helsinki Helsinki, Finland
Friedrich-Schiller Universität Jena
Jena, Germany
j juha. hww.rhaiiinennhelsss.....
frank. rrame.sommeruui -eaeeerr@@njanaaee jena.ena....
Manuel Sorge*
Institute of Logic and Computation
TU Wien
Vienna, Austria
manuel. tuwien. an.ac. at
Abstract
Algorithms for learning decision trees often include heuristic local-search opera- tions such as (1) adjusting the threshold of cut (2) also exchanging the feature of that cut. We study minimizing the number of classification errors by performing fixed number of single type of these operations. Although discover that the corresponding problems are NP-complete in general, we provide a comprehensive cegumeetrized-complexxee
analysis with the of determining those properties of the problems that explain the hardness and those that make the problems tractable. For instance, we show that the problems remain hard for small number d of features or small domain size D but the combination of both yields parammereee tractability. That is, the problems are solvable in (D + 1)2d, [2]) time, where [I] is the size of the input. We also provide a proof-of-concept implementation of this algorithm and report on empirical results.
Introduction
Decision trees classify and explain data by associating labels with subsets of the feature space, characterized by set of inequalities (30) 31 35 Not only are the models simple and efficient but also relevant for explainable AI because of their interpretability [5
Many prominent algorithms utilize heuristics to decide
for learning decision trees like CART [2), C4.5 [36]. C5.0, and J48 4%
when and where in the tree to add new internal nodes that cul data based on some chosen feature and threshold value. To mitigate overfitting, one may afterwards remove cuts from the decision tree by performing different types of pruning operations such as replacing some subtree by a leaf node Typically, when and where these applied is also chosen heuristically.
12. 36 43
After finding an initial solution common and effective technique for optimization problems is to then perform local search, that is, searching for a better solution within some local neighborhood under some distance metrie. Local search for decision trees is prevalent the literature, in particular in
simulated annealing approaches 6 8), genetic algorithms as mutator 20 21 22
23 27 28 29 40
and SAT-based local search has recently shown strong performance for finding near- nptrioptimal decision
trees 41 However, local search is not applied in the standard decision-tree heuristics 2 36
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

raising the question whether there is a justification for this situation. That is, what is the potential for local search to be effective for decision trees, in particular, heuristically computed ones? To answer this question, we need algorithms that are capable of, given decision tree and training data, to find the optimum solution within local neighborhood. Unfortunately, we are not aware of any systematic anal- ysis of the algorithmics of this local-search problem. Contributing such an analysis is our main goal.
We focus on two natural types of local-search operations: Choose cut and (1) adjust the threshold of the cut or (2) also exchange the feature associated with the cut. Both have been studied extensively in heuristics
20
28 29 40) We refer to searching the local neighborhood for an
optimal modified tree as THRESHOLD ADJUSTMENT and CUT EXCHANGE. More specifically, we ask whether at most & cuts can be modified (with adjustment or exchange) simultaneously such that the resulting tree has fewer errors than the input tree. As we show, both problems are No-complet; thus we need more detailed algorithmic analysis to be relevant to practice. Thus, we identify the key parameters related to the local-search problems and characterize the influence of these parameters and most of their combinations on the complexity; see (Fiuur 2 This continues recent line of research
on parameterized learning and improvement of decision trees 7 10
14
24
25
33
34
42 26).
There are three main levels of influence that parameter p can have when a problem is NP-hard: ideally (1) fixed- parameter tractability (FPT), that is, there is an algorithm with f(p) |Z ((0) rumning time, or (2) W[1] hhardnessssss and XP-tractability, that is, there is an algorithm with running time f() [Z] (p) and it is likely not possible to remove the dependence of the exponent on p. and (3) paraNP-hardness, hardness, that is, even for constant values of the problem is NP-hard. The parameters that we study are the number n of training- -ata examples, number d of features, the largest domain size D, the size of the input tree, the number & of local search operations, the number & of nodes unaffected by local search, an upper bound t on the number errors that we aim for, and the largest number 8mxx of features in which two examples of different classes differ; see see Figure 1
See Figure 2 for overviews over our results. Broadly, we observe that CUT EXCHANGE is at least as hard as THRESHLLD ADJUSTMENT; in particular this is justified by reductions from the latter THRESHOLD ADJUSTMENT to CUT EXCHANGE. Both are also related to the problem of learning an optimal decision tree from scratch: Some of our results can be interpreted to show hardness of learn- ing decision trees even when we restrict the structure of the desired trees. Essentially, the associated reductions use scaffolding to construct useless decision tree which then has to be made useful via changing its cuts with local-search operations where the number of seaal- operations roughly corresoonds to the size of the tree to be learned. (In practice, however, the number of local search oper- ations will be lower than the tree size to be learned.) There are indeed parameter combinations where THRESHOLD A ADJUSTMENT is strictly harder than learning decision trees, and CUT EXCHANGE is strictly harder than THRESHOLDD ADJUSTMENT from a complexity point of view, see Figure 2)
On the positive side, several parameter combinations yield tractability: For instance while both prob- lems are unlikely to be sreed-paramete tractable (FPT) in either the number d of features or the maxi- mum number D of distinct values for feature alone, their combination yields an FPT-algorithm. This algorithm can also straightforwardly incorporate the parameterized decision- tree pruning algorithm of Harviainen et al. [14] on the same parameters to improve the decision tree with local search and prun- ing at the same time, where the pruming operations either (1) replace a subtree by a new leaf or (2) raise subtree Tn rooted by substituting a subtree rooted at ancestor of with T. (see Theorem 4.3).
To complement our theoretical findings, we study the potential benefits of local search, that is, is there room for improvement in the decision trees constructed by the heuristics? While it is well known that optimally learning decision trees is NP-hard [16), the heuristics might still perform (almost) optimally practical instances at least be optimal in some local neighborhood of models. For instance, recent research [4] has-perhaps unex employed by the commonly used libraries tend to be near-optimal on common benchmark datasets. We observe a similar phenomenon here suggesting near-optimality also locally, that is, while there is some room for improvement on the instances already by performing single local search operation, the decrement in errors tends to be mild (see Table
that the pruning heuristics
We proceed by fixing basic definitions and notation in Section 2 In Section 3) decision trees reduces to local search. Section 4 focuses on al algorithms for both problems, and in
we show that learning
"See Ordyniak and Szeider [34 Table 1J and Staus et al. 42 Table 3] for indication that &max is small in relevant settings and see Harviainen et al. [4 Section 6] for parameters and D.

---

FPT
BF
BF
XP and Will
paraNNT-brr
5.3
27
3.3
3344
33.3
4.1
d'
14.6
C5.4
3,3
Figure I: A Hasse diagram of the parameters, where an edge between two parameters means that the lower is upper bounded by some function of the upper one. The dashed edge applies only to the THRESHOLD ADJUSTMENT problem. The color of the left box next to each parameter indicates the complexity for THRESHOLD ADJUSTMENT and the color of the right box for CUT EXCHANGE. which happen to be the same for all considered single parameters. The texts of the boxes refer to the corresponding theorems, and BF stands for brute-force algorithm. The figure shows that for example, both problems are W[1]-hard and in XP when parameterized by and consequently they are at least W[1] haard (potentially paraNP-hard for all parameters smaller than s (for example E and have at least an XP-time algorithm (potentially FPT) for all parameters larger than s (for example n.).
Section we provide further hardness results for both problems. Our main technical highlights are as follows: (1) For the FPT-algorithm for tree size and сπтог bound for THRESHOLD ADJUSTMENT, in first step we guess the changed cuts and the distribution of errors in the final tree and in a second step we rely on recursive binary-search to compute the optimal thresholds. Our other algorithms exploit structural properties via dynamic programming. (2) Our most involved hardness result is the W-hardness for the number d (for both problems). We reduce from MULTICOLORED CLIQUE and create two features per color class and an input decision tree T which has a regular structure. However, we need to be very careful with the values of the examples in these features (especially for THRESHOLD ADJUSTMENT since we cannot change the feature of any cut). In Section 6 we summarize our experiments and their results. Finally, conclude with implications and potential research directions in Section 7
Preliminaries
In this section, recall the basic definitions and terminology of decision trees and parameterized complexity. Denote the set {1, .........,, m) } by [m]] and the set {0, 1...., m) by [0, m).
Decision trees. The set E labeled data points the d-dimensional space Rd called examples. The set of possible class labels of E is denoted by E, which we assume to be (blue, red} throughout the paper. The value of the ith feature of an example is e[i] and the label of the example is A(e).
The pair (F, A) is the training data set. For feature i and threshold
R, we define two subsets of examples [t] x] = {e E F: e[i] S x) and E [R, x] = E Fig (i, = (e E
F: e(i) > x).
decision tree is a tuple (T, feat, thr, cla) with a rooted tree T on a set of nodes V = V(T), functions feat and thr that associate feature feat(v) E [d] and threshold thr(v) E to each internal node v E V, and a function cla that associates class label cla(u) E Σ for each leaf node v E V. With minor abuse of terminology, we often call the rooted tree T decision tree without explicitly mentioning the functions feat, thr, and cla. The internal nodes are also called cuts. Each cut u V of the rooted tree T has two ordered children which we refer to as its left and right children.
Each node e E V of the decision tree T is then associated with a subset E[T, w] C E of the examples, defined recursively
V whose left child is u and right child is w, we let E u] = E T, n E feat(u). thr(u)) and E(T, w] E E [feat(w), thr(w)). For conciseness, let FE(e) Note that for any example e, the set of nodes for which e E Elv] is a path from the root of 7' to one of its leaves w. We call w the leaf of and say that 7' assigns e the class cla(w). If A(e) cla(w). then is correctly classified (by 7),, and otherwise it is misclassified and called an error.
follows. For the root of T. we let E r) F. For
E (T w) when T is clear from the context.
A continuously updated version of our paper is available on arXiv 12 and the related source code for replicating the experiments on Zenodo [
3

---

FPT
largest param.
|4.4
14.1
XP and Whrldbard
class+thoorem
14.5
142
8+1
d ++++ D
paraNP-bard
lowest param.
d+s+3
d D
A D
A + D + Ómes
a
a ++t+ D
+ D D 6max
s + d 14.6 & 13.7
& 5.3
14.6 c5.5
1/4.1 & 13.4
14.6 & 13.3
14.6 13.3 b
k
E+ D + 8mnx
+ D + 6max
t ++ D
d +++
d é 2+t
C+++ D+
(5.7
(5.4
15.6
14.1 5.2
1 & 15.1
F3.3
(a) Results for THRESHOLD ADJUSTMENT
(b) Results for CUT EXCHANGE
Figure 2: Summary of our results for combinations of parameters. In each box, the center cell indicates the complexity class (and references the corresponding theorem) which holds for all parameterizations bounded from below by the parameter of the bottom cell and from above by the parameter of the top cell. As a concrete example, the first box the middle row states that THRESHOOLD ADJUSTMENT is [[1]-hard and in XP for, for example, k, k + D, k + L, and k + D + I. Note that THRESHOLD ADJÜSTMENT parameterized by + E 4 D is W[1]-hard but XP-tractability is open.
Local search. In the present work, we consider two natural local operations that modify the decision tree (I", feat, thr, cla). The first operation is threshold adjustment, where we choose one cut e E V of the decision tree and a new threshold x E IR, and obtain a new decision tree (T", feat', thr', cla') whose only difference to (T, feat, thr, cla) is that thr' (u) = x. Similarly in our other operation, cur exchange, pick one cut
V, a new feature
[d]. and new threshold IR obtain We also allow for arbitrarily changing the labels of
decision tree with feat' (v) and thr (v) the leaves of the decision tree to accommodate the modified cuts better.
Given these two local search operations, the question is then how much performing them some number of times helps us reduce the number of misclassifications, potentially after relabeling any number of leaves. We thus consider the following problems:
THRESHOLD ADJUSTMENT/ / CUT EXCHANGE
Input: A training data set (E, A), decision tree T for (E, and k N.
Task: Perform threshold adjustments/cut exchanges obtain a decision tree with at most errors.
Reasonability. To argue about the computational hardness of the problems in practice, we apply the notion of reasonability of Harviainen et al. [14]. Roughly speaking, reasonable decision tree should be learnable by a heuristic algorithm for decision tree learning. More precisely, they propose two rules properties that a reasonable decision tree should satisfy: (1) no leaf should be empty, that is, Fl(]] * 0, and (2) the class label of each leaf v should match the majority of examples E F(()).
Parameterized complexity. We study the complexities of these problems from the viewpoint of parameterized complexity 3 3 [) that is, we not only consider total encoding length [Z] of the input instance I but also its properties. They are described by parumeters nt, d, k. and defined above, the size 8 of the decision tree, the number of unmodified cuts & == 8 k, the domain size D = maxie[e] [e[i]: e E E}| and 6max. which is the maximum number of features where two examples of different classes have different values. These parameters have also been observed to be relevant in the literature for learning 10] 24, 34] and pruning (14) decision trees, and their relationships are illustrated in Figure Note that s I by reasonability and that d < n for threshold adjustment, since we can remove all features of the examples that do not appear in the initial decision tree.
A problem is fixeed-prramete tractable (FPT) with respect to parameter if any instance I of the problem solvable in time O(f(p) poly [Z]) for some function f. For example, FPT in n for THRESHOLD ADJUSTMENT and CUT EXCHANGE follows by observing that there are at most (s + 1)"h S n" ways the examples can be partitioned to the leaves, and we can test in polynomial time for each partition whether it is obtainable with k < S operations. A problem is slicewise

---

polynomial (XP) if it is solvable in time O(f(p)- (I (())) for some functions f. Under the common assumption that FPT i I, one can show that problem not FPT for some parameter p by reducing some known Wii]-hard problem to it in time ((J(p) poly [Z]).
Tighter lower bounds can be proven conditional the exponential time hypothesis (ETH) 17 18
which states that 3-SAT n-variable formulas cannot be solved in 20(*) time. Essentially, one then shows that a fast algorithm to a problem would violate ETH through a reduction from 3-SAT AT to the problem. The strong exponential time hypothesis (SETH) [77 18 similarly states that the satisfiability problem for n-variable formulas in conjunctive normal form cannot be solved in O((2 - ))") time.
3 From Computing Decision Trees to Local Search for Decision Trees
In this section we provide parameterized reductions from restricted versions of the computation of optimal decision trees to the associated local search problems for decision trees with respect to the two operations threshold adjustment and cut exchange, allowing us to transfer hardness results.
Computation of minimal-size decision trees. Initially, reconsider the problem of computing minimal-size decision tree DECISION TREE LEARNING and strengthen an existing hardness result which will also hold for one of new restricted versions and subsequently also for CUT EXCHANGE. In DECISION TREE LEARNING the input consists of a training data set EE, A) and integers 8, I E IN, and the task is to compute decision tree T with most inner nodes making at most i errors. Gahlawat and Zehavi [1 Thm. 1] showed that DECISION TREE LEARNING is W[1]-hard for and cannot be solved in |Z] [[(( time unless the ETH fails, even if 6max 3. Here, we strengthen their result by ensuring that parameter D is constant, while arguably being simpler.
Theorem 3.1 (+). DECISION TREE LEARNING is W[1 for s and cannot be solved in [Z] ((()) time unless the ETH fails, even 8max 2 and D 2.
Computation of structure-restricted decision trees. To obtain hardness results for CUT Ex- CHANGE, we reduce from the problem of computing decision tree with a fixed structure, that is. the underlying tree of the decision tree T is fixed. In other words, we are given a tree Q and need to assign cuts to each inner node of Q. Moreover, for THRESHOLD ADJUSTMENT, we reduce from the problem of computing a decision tree with fixed structure and a fixed feature assignment, that is, the function feat(-) given, mapping each inner node of the fixed tree Q to a feature of E.
We consider the following two learning problems: (1) In FIXED STRUCTURE DECISION TREE (FS-DT) the input consists of training data set (E, A), 3, tree Q, and / IN, and the task is to assign features and thresholds to all inner nodes of Q, and classes to the leaves such that the resulting decision tree T makes at most errors. (2) In FIXED STRUCTURE FIXED FEATURE DECISION TREE (FSFF-DT) the input consists of training data set (E, A), a tree Q. a function feat(.) with fixed feature assignment, and E IN, and the task is to assign thresholds all inner nodes of Q, and classes to the leaves such that the resulting decision tree T makes at most errors.
Observe that FS- "S-DT/FSFF-D" DT corresponds to the special case of CUT EXCHANGE/THRESHOII ADJUSTMENT where & = s we assign some dummy cuts/thresholds to all inner nodes and some dummy classes to all leaves of the tree Q. We formalize that as the following observation and to obtain hardness results for both CUT EXCHANGE and THRESHOLD ADJUSTMENT via hardness results for FS-DT and FSFF-DT, respectively.
Observation 3.2. There is (parameterized) reduction from FS-DT to CUT EXCHANGE and from FSFF-DT to THRESHOLD ADJUSTMENT where
FS-DT and CUT EXCHANGE. Note that in the reduction behind Theorem 3.1 the structure of any decision tree T which is a solution is essentially fixed: The inner nodes of T always form a path, exactly one leaf of the last cut in T is blue, and all other leaves are red. Consequently, the reduction behind Theorem 3. also works for FS-DT. Since other hardness reductions for DECISION TREE LEARNING enforce similar structures of the resulting decision tree, we obtain the following.
Proposition 3.3 (+). Even if the subgraph induced by the inner nodes is a path, CUT EXCHANGE is - for s and cannot be solved in [I]o(s) time unless the ETH fails, even if = 0, D and 6 6max 3.
5

---

2. is NP-hard even if D = 2, 6max = -2 2- O, and = =0
3. is W[2]-hard for 8, cannot be solved in [Z]o(e) time unless the ETH fails, and cannot be solved in (0(f==))fo for any & > 0 unless the SETH fails, even if D = 2, i f= O, and 0,
FSFF-DT and THRESHOLD ADJUSTMENT. Next, for THRESHOLD ADJUSTMENT our goal is to show the following. (Running time lower bounds herein hold when assuming the ETH.)
Proposition 3.4 (+), Even if the subgraph induced by the inner nodes is a path, & = 0, and 6max is constant, THRESHOLD ADIUSTMENT I-ard wrt. 8 + d and cannot be solved in [I]o(s+d) time.
To prove Proposition 3.4 we first take a closer inspection of a similar hardness result presented by Harviainen et al. [14 Thm. 5.6] for decision tree pruning with the so-called raising operation and show that their reduction can also be used to show a similar hardness result for FSFF-DT. Second, we use Observation 3.2 to obtain the result for THRESHOLD ADJUSTMENT.
Proposition 3.5 (+)), Even the subgraph induced by the inner nodes is path, t= and òmax is a constant, FSFF-DT is W[ J-hard wrt. 8 + d and cannot be solved in n ne(e)) time.
Finally, we provide reduction from THRESHOLD ADJUSTMENT to CUT EXCHANGE which allows us to transfer our hardness result for parameter s d to CUT EXCHANGE. We achieve this in two steps: (1) We modify the THRESIOllD ADJUSTMENT instance I such that each feature is used at most once by adding new identical original features. (2) We replace each leaf of by a new gadget G, consisting of long path of cuts in new features and we add new dummy examples E, for each leaf which can only be correctly classified with our budget of allowed cut exchange operations if they end up in gadget G. corresponding v. Thus, cut exchange operations performed at original cuts can only change their thresholds.
From THRESHOLD ADJUSTMENT to CUT EXCHANGE.
Theorem 3.6 (*). THRESSHLLD ADJUSTMENT reduces CUT EXCHANGE. Proposition 3.7 (*). CUT EXCHANGE is W[I]-hard with respect to s + d.
4 Algorithms for THRESHOLD ADJUSTMENT and CUT EXCHANGE
Here, we provide FPT-algorithms and XP-algorithms for both problems and various parameters.
The parameter d + D. Now, show that both problems admit an FPT-algorithm for d + D via Simultaneously, these algorithms are also XP-algorithms for d. Afterwards, we show that this dynamic-progue programming approach also works if we allow both local search operations and also pruning. More precisely, in DECISION TREE PRUNING AND LOCAL SEARCH (DT-PLS) the input is a decision tree T' and have 4 individual budgets, one for the number of threshold adjustment operations, one the number of cut exchange operations, one for the number of subtree replacement operations, and one for the number of subtree raising operations. Recall that in subtree replacement operation an inner node v of I' whose 2 children are leafs is replaced by new leaf and in subtree raising the subtree rooted an ancestor of is substituted by the subtree rooted v.
Theorem 4.1
)). THRESHOLD ADJUSTMENT can be solved in O(D + 1)2d+ nx2 + ns) time.
Proof Sketch. We adapt the algorithm of Harviainen et al. [1] for subtree raising under the same parameterization. threshold sequence (I,, rx)xe a encodes for each feature E [d] an interval (1,, ra]. characterizing a subset of the feature space. Let E[(1, re)seja]] == {e E E: e(i] E (ley for i E [d] be the set of examples within the box defined by threshold sequence. Let Q/u, (4, r re)sefa ki be the minimum number of errors achievable if our decision tree is the subtree rooted at v E V on
our initial decision tree on the set of examples ([(,,, (1(4,,r;)ve(d re]q] if we make at most k'' threshold adjustment operations. Define L((,,, T:) ri)se(4) 2) as the threshold sequence identical to (le, re) except that for i = j we have the interval (max (4,, xr (.r)).)))))))))) rz). Define R(I:, re)se J.
- 2) analogously
with interval (4, max(r:, 2z)). For any cut v, when combining subresults of the left child and the right child u of v, we either adjust thr(v) or not. Thus, Q/v, (4,, rz)seld k"] is the minimum of
min Quu, L((4,, ri)reta feat(v), (h)(,,), 8] + Q[u, R((4, re)seta feat(v), thr(v))), k' 3]] and (E(0.K)
min -1l
Qww, L((4,, (x) feat()), x), 8) + Q[u, R((1, my ra)ee4 feat(v), K' - 3-1]. O

---

Theorem 4.2 (+). CUT EXCHANGE can be solved in O((D + 1)2d+1 'ndk² Indk + +n)) time. Theorem 4.3 (*)). DT-PLSS can be solved in O((D + 1)2d+1 ns) time.
The parameter 8 + t. We now provide FPT-algorithm for THRESTOLLD ADJUSTMENT with respect to 8 + by iteratively using binary search to determine the new thresholds. contrast, in Proposition 3.3 we showed that CUT EXCHANGE remains W[2]-hard with respect to 8, even if / = 0. Hence, an FPT-algorithm for 8 + is unlikely. However, if we additionally include the number d of features in the parameter. then we can obtain FPT-algorithm.
Theorem 4.4. THRESHOLD ADJUSTMENT can be solved in s((st))) poly([Z)) time.
Proof. Let A,, k. t) be an instance of THRESHOLD ADJUSTMENT and let 7" be a solution. Next, we describe our branch-and-boume algorithm: First, we guess the k nodes N where a threshold adjustment is done, that is, the k nodes with different threshold in T than in T. Clearly, by testing all (s**) (ss") node subsets of size most in one branch the algorithm finds the correct node subset N where the adjustments are performed. Moreover, since T has + 1 leaves, there are 2*+1 possible assignments of classes to the leaves. Again, by testing all 2*+1 of them, the correct one is found in one branch. In the following, we assume that the set N and this assignment are fixed.
Second, guess how many errors are done in each leaf in TV. Since T has size and is binary, T has at most + 1 leaves. Now, for each of these leaves we guess a number t; E [0, t] such that the sum of all these numbers is at most t. Let t be the corresponding error vector. Number represents the number of errors in leaf i of the solution T", Clearly, by testing all O(s²) possibilities, in one branch the algorithm find the correct error distribution as in the solution T". In the following, we assume that the error vector t is fixed.
Finally, we use binary- to obtain the concrete thresholds of the nodes N. This technique is inspired by a similar procedure to obtain the thresholds when computing a minimal size (or minimal depth) decision tree 77 10 24 34. Consider node p E N for which we have find the correct threshold lp in TV. With the binary search, we determine the largest threshold value lp in the feature of node p for which we can find thresholds for all nodes with unknown thresholds in the left subtree of p respecting our guess on the number of errors in all leaves. Moreover, if for threshold t, we cannot find thresholds for all nodes with unknown thresholds in the right subtree of p respecting our guess on the number of errors in all leaves, then we deal with a no instance: We cannot move threshold tp further to the left since then even more examples go to the right subtree of p and thus the number of errors in the right subtree cannot decrease. The pseudocode of this binary search is shown in il/oggrithmm I We defer the analysis of correctness and time complexity to the Appendix B.4
Theorem 4.5 (*). CUT EXCHANGE can be solved in (3 (I))(1) time.
The parameter k. Finally, for the parameter l we obtain XP-algorithms via brute-force.
Proposition 4.6 (+). 1. THRESHOLD ADJUSTMENT can be solved in time O (s ++ D)
2. THRESHOLD ADJUSTMENT can be solved in time O ((D + sm).
3. CUT EXCHANGE can be solved in O(((D + 1) time.
5
Complementing Hardness Results for both Problems
First, we show that both problems are W[I]-hard for d even if ( = O. This result implies that the parameter in Theorem 4.5 for CUT EXCHANGE cannot be dropped. Second, we take closer inspection of THRESHOLD ADJUSTMENT. More specifically, we provide hardness results for various parameters including k. One of our results implics that the simple brute-force algorithm behind Proposition 4.6 for THRESHOLD ADJUSMMENT cannot substantially improved, unless the ETH fails.
The parameter d+t.. t. We show that both problems are unlikely to admit an FPT-algorithm for d l. Our results are inspired by a hardness reduction of Harviainen et al. [14 Thm. 5.10] who showed W[1] -harddess for decision tree pruning with subtree raising for the same parameter. Our reductions, however, especially the one for THRESHOLD ADJUSTMENT, are substantially more involved.
7

---

Algorithm Binary search to populate the unknown thresholds of the decision tree T. The initial call is ComputeTTrresholdstE,, r). where E is the of examples and is the root T.
Global Variables:
Decision tree T, N VT) of nodes with unknown threshold, error vector t
Function ComputeThreshollde (E", ,n))
Input: An example set E' S E and node T.
Output: True if and only we can assign thresholds to all nodes with unknown threshold the decision tree corresponding to the subtree rooted at while respecting the enror vector t we only consider the examples E".
n is a leaf then
error bound according to t is met Let e be the class label of n. and i, be the entry of t corresponding to n more than t, examples of E' do not have label c then return False else return True n E N then = BinarySearch
// check
// n has an unknown threshold
else 2 = thr(n)
p right child of n, x ComputeTThresholds EE [feea((n) > 2). p)
q = left child of n, y = ComputeTTrresholdss E (feat(n)) S 2|.9] 9)
return x AND y
Function BinarySearch (E', 1E',))
Input: An example set E' C E and a node n E T.
Output: The largest threshold of feat(n) s.t. left subtree of n while respecting the error vector t if we only consider the examples E'. Set D to be array containing all thresholds of feature feat(n) in ascending order
populate all unknown thresholds in the
10
Set I, = 0, R = [length(D) D)] - -1, 1,,b 1,bb00 =
left child of
11
while L < do
12
m [[L + R2
13
if ComputeThresher else R m 1,
[featii) S Diml]. q) True then L m + 1,
14
b then return D m
16
return D(m 1). with D -1] = D[O] -1
For both problems, we reduce from MULTICOLORED INDEPENDENT SET, where the input is graph G, and x e IN, where the vertex set (GG of N vertices is partitioned into Vi,..., Vg. The question is whether G contains MULTICOL.ORED INDEPENDENT SET is W[1]-hard parameterized by k. and cannot be solved in f(x) - (x)()) time unless the ETH fails [3. In both reductions, we create two features d, and d? per class such that all cuts in features di and d? together correspond to a vertex selection in V,, We achieve this as follows: For each pair d, and d,",, we create examples which can only be separated in these two features and which have labels blue and red alternatingly. Hence, for each possible threshold x in features di and di", the resulting decision tree needs to contain either cut (d x)) or cut (d.- .r). Furthermore, for each edge create red edge example. If vertex V.j V; is selected, then all edge examples corresponding to edges having an endpoint color class i which is not Uj.j will then be correctly classified by the resulting decision tree T. Thus, can only correctly classify an edge example if we do not select at least one endpoint of the corresponding edge.
independent set consisting of exactly one vertex per class V,
For CUT EXCHANGE the input decision tree T" is path with red and blue leaves alternatingly with cuts in dummy feature d. To obtain T, all cuts of T' which are in d, need to be changed to cuts in features d, d² and di For THRESHOLD ADJUSTMENT it is more complicated since we cannot change the feature of any cut: Thus, we extend features di and de by new dummy thresholds which are used in the input decision tree 7". Since f = 0, however, 7" cannot be path anymore, Instead, we add new cuts dummy cuts new dummy features which cannot be adjusted, as we show.
Theorem 5.1 (+). CUT EXCHANGE is WhIl-hard for d even if 8max 6, l = 0 and t 0. Under ETH, the problem cannot be solved in time [Z]o(d).
Theorem 5.2 (+). THRESHOLL ADJUSTMENT is W[1]-hard for d even if and δmax = 20. Under ETH, the problem cannot be solved in time [Z](d))
Other hardness results for THRESHOLD ADJUSTMENT. Now, we prove hardness for many parameters including k. Afterwards, we present two hardness results for parameters including & + D.

---

Theorem 5.3 (+), THRESHOLD ADJUSTMENT is W[2] 1122-hardffo for k even if D = 2 and t = O. Under the ETH, the problem cannot be solved in time ((I)(())) and under the SETH, the problem cannot be solved in time ()s for any E O.
Proof Sketch. We reduce from the W[2]-hard problem HITTING SET 3 Consider an instance of HITTING SET with a universe U = {1,2,.... |0]} and a family of sets S such that we look for a hitting set of size K. We create THRESHOLD ADJUSTMENT instance with [U] features d1, d2. dlel. and for each set S in S we create a red example such that e e[d] = 0 if E S, and eld.] = otherwise. We also create one blue example e' with c'[d.] = for all E U. Our initial decision tree has [U] cuts C12 ................................ C(y) that form chain where the right child of the cut e; is 4 for all E ||0| - 1]. The right child of cjj is blue leaf. The left child of each cut is a red leaf. The feature of the cut c; is d, and the initial threshold is O. Finally, let h = K. and f = O. The correctness proof, the lower bound, and adaptation for reasonable trees are deferred to the appendix.
Our next two results follow by reducing from (PARTIAL.) VERTEX COVER instead of HITTING SET.
Corollary 5,4 (*)) THRESHOLD ADJUSTMENT is NP-hard even if D = 3, 8max = 2, and t = 0. Corollary 5.5 ) THRESHOLD ADJUSTMENT is W[IJ-hard for k even if D 3 and Ómax 2.
To achieve our final two results, we again reduce from HITTING SET/VERTEX COVER. Each cut starts in an undecided state (threshold 0) and has to be included (threshold 1) or not included (threshold - in the hitting set. Including a cut yields 1 error and thus only a fixed number of cuts can activated.
Theorem 5.6 (+) THRESHOLD ADIUSTMENT is W[2]-hard for even if
Under ETH, the problem cannot be solved in time ((I)((t)), and under SETH, the problem cannot be solved in time O(s O(st"))oo any >>
Corollary 5.7 (*)). THRESHOLD ADJUSTMENT is NP-hard even if 8 0. D 3, 6max 3.
Experiments
The goals of our small-scale empirical study were follows: (1) Assess whether our algorithms can in principle be used to study the local-search neighborhoods of decision trees that are computed from real- world benchmark data by established heuristics. (2) Evaluate the potential performance of local search in optimizing existing heuristic decision trees. (3) Assess whether performing pruning and local search simultaneously is superior the heuristics in terms of classification error. The experiments not designed to be conclusive; instead they have a proof-of-concepl nature and aim to spur follow-up work.
We used 47 datasets from the Penn Machine Learning Benchmarks library 138 including 32 previously used for minimum-size tree computation [ 32 42) and additional larger datasets. The datasets range from 72 to 5404 examples (mean 655.09. median 302.00), see the appendix for more details. We computed unpruned and pruned trees using WEKA 3.8.5's 9 C4.5 implementation (36) J48. For the pruned trees we used J48's subtree replacement hcuristic; more details in the appendix.
We implemented an algorithm based on Theorem 4.3 that, given a dataset and decision tree T, can compute for every tuple (Kad- Kex, kire) the minimum number of errors attainable by a tree obtained from T with at most had adjustment, Kex exchange, and kie subtree replacement operations (where kie counts the number of cut nodes). Since naive enumeration of all threshold sequences in the dynamic program wasteful, we instead start, for each node v in the tree, with the sequence of thresholds implied by the cuts above and then compute all modifications of this sequence obtainable by the remaining number of adjustment and replacement operations above v. This maintains optimality. Nevertheless, there is large potential for heuristic improvements. We implemented the algorithm in Python 3.10 3.10.12 and all experiments were carried out on a personal computer running Ubuntu Linux 22.04 with an 8-core Intel Core i7-9700 processor and 16GiB RAM (running up to eight instances of the algorithm in parallel).
We first checked whether the heuristically computed real-world pruned decision trees are locally optimal. That is, for each of the 47 datasets we took the pruned tree and checked whether their misclassifications could be reduced by up to two adjustment or exchange operations. For adjustment, 33 (70.21%, %) thus obtained problems could be solved within a Ih time limit, for exchange was 17 (36. 17%). The heuristically computed trees were 2-optimal or close to 2-optimal, that is, they

---

Table Error rates for different operations. Dashes indicate timeouts.
Dataset
Initial
kiad
Kad
kiex
Kex
2
banana
249
248
breast-cancer
31
30
30
30
29
cleve
15
14
14
14
cleveland
13
12
12
12
aevellnd-nomingg
23
23
23
22
22
colic
15
15
15
14
ccoli
10
8
8
8
8
heart-c
15
14
14
14
lymphography
5
5
5
5
4
profb
42
41
41
can hardly be improved with up to two local-search operations: with most two exchanges, 9 trees could be improved, and with up to two adjustments, trees. The reduction in misclassifications was at most 2. Table I shows the trees which could be improved. To summarize, for small number of local search operations the implementation is feasible and seems that heuristically computed trees close to being locally optimal.
We also looked at combining pruning with local search. We first investigated whether local search enables further pruning heuristically pruned trees: For 18 datasets, this was possible after adjustments (avg. 1.40 nodes) and for 24 after exchanges (avg. 1.78 nodes)-with one tree size nearly halving after a single exchange. Starting with unpruned trees and combining pruning with local search gave better results than sequential application: 10 and 17 trees showed error reductions of 5.16% and 8.92% on average, respectively. We also computed full pareto fronts for the tradeoff between pruning and errors (Figure 7| appendix); here local search becomes more effective with aggressive pruning. This indicates that heuristics typically select tradeoff's minimally amenable local search; full details in the appendix. Overall, our algorithms provide new insights indicating local search becomes increasingly valuable with more extensive pruning than commonly applied. Note that obtain the above results we need algorithms that find the optimum, which we here designed for the first time.
Outlook
We gave comprehensive analysis of the parameterized complexity of improving decision trees with the local search operations threshold adjustment and cut exchange. We presented both algorithmic results and complexity-thooe -thooretc lower bounds for both problems corresponding to the two operations. Based on these algorithms we provided proof-of-concee there some aalettia-aalbil limited-for improvement in the trees constructed by heuristics. The experiments were hampered by the computational hardness of the problems, which might be mitigable by designing new approaches to them, for example, by formulating them as mixed integer program.
implementation and demonstrated that
While we settled the complexity for many parameter combinations for both problems, some combina- tions still open. For example is THRESHOLD ADJUSTMENT FPT with respect d + + + I, is CUT EXCHANGE FPT with respect to d + k + !? Investigating so-called ensembles of decision trees under the local search operations threshold adjustment and cut exchange an interesting direction for future research. Clearly, our hardness result transfer to ensembles, but for the algorithms this is clear, Moreover, on the practical side it is interesting to investigate whether the effect of local search for ensembles is stronger than for single decision tree. Also, it is interesting to study the complexity of other local search operations for decision trees which change the structure of the tree, for example subtree switching 377 or subtree substitution [41]. Moreover, since our new approach yields optimal solutions for local search of decision trees, our algorithms could be used to develop new genetic algorithms with more powerful crossover operations. Finally, currently minimal-size decision trees can only be computed for size up to s = [42] and major hurdle are good lower bounds to abort parts of the branch-and-boune approach early. Our local search algorithm could help in strengthening existing lower bounds and thus make the learning of minimal-sin decision trees more applicable.
10

---

Acknowledgments and Disclosure of Funding
Juha Harviainen was supported by the Research Council of Finland, Grant 156. We also gratefully acknowledge support by the TU Wien International Office for hosting Juha Harvianen in Vienna.
Frank Sommer was supported by the Alexander von Humboldt Foundation and partially by the Carl Zeiss Foundation, Germany, within the project "Interactive Inference".
References
[1] C. Bessiere, E. Hebrard, and B. O' O'Sullivan. Minimising decision tree size as combinatorial optimisation. In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP '09), volume 5732 of Lecture Notes in Computer Science, pages 173-187. Springer, 2009.
[2] L. Breiman, H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, 1984.
[3] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipezuk, M. Pilipczuk, and Saurabh. Purameterized Algorithms. Springer, 2015.
[4] R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput., 24(4):873-9211 1995.
[5] R. G. Downey and M. Fellows. Fixed perd--arameter tractability and completeness II: On completeness for W[1]. Theor. Comput. Sci., 141(182):109-131) 1995.
[6] J. Dvorák and P. Savicky. Softening splits in decision trees using simulated annealing. In Proceedings of the 8th International Conference on Adaptive and Natural Computing Algorithmss (ICANNGA '07), volume 4431 of Lecture Notes in Computer Science, pages 721-729. Springer, 2007.
[7] E. Eiben, S. Ordyniak, G. Paesani, and S. Szeider. Learning small decision trees with large domain. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (ICAA 23). pages 3184-3192. International Joint Conferences on Artificial Intelligence Organi- zation, 2023.
[8] G. Folino, C. Pizzuti, and G. Spezzano. Genetic programming and simulated annealing: A hybrid method to evolve decision trees. In Proceedings of the 3rd European Conference on Genetic Progrumming (EuroGP '00), volume 1802 Lecture Notes in Computer Science, pages 903- Springer, 2000.
[9] E. Frank, M. A. Hall, G. Holmes, R. Kirkby, and B. Pfahringer. WEKA A machine learning workbench for data mining. In The Data Mining and Knowledge Discovery Handbook, 2nd ed, pages 2269-12777 Springer, 2010.
[10] H. Gahlawat and M. Zehavi. Learning small decision trees with few outliers: A parameterized perspective. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI '24), pages 12100-12108. AAAI Press, 2024.
[11] Guo, R. Niedermeier, and S. Wernicke, Parameterized complexity of vertex cover variants. Theory Comput. Syst., 41(3):501-520, 2007.
[12] J. Harviainen, F. Sommer, and M. Sorge. Improving decision trees through the lens of parame- terized local search. CoRR, abs/2510.127266, 2025.
[13] J. Harviainen, F. Sommer, and M. Sorge. Improving decision trees through the lens of parameter- ized local search (associated software), 2025. Link: https://doi.rr/// 10. I/zenodo.. cttt/eooooo.73300000 17350776.
[14] Harviainen, F. Sommer, M. Sorge, and S. Szeider. Optimal decision tree pruning re- visited: Algorithms and complexity. In Proceedings of the Forty-second International Conference on Machine Learning (ICMI. '25), 2025. To appear. Full version available at http://.....rr/ooo00/555/5//////

---

[15] A. Holzinger, A. Saranti, C. Molnar, P. Biecek, and W. Samek. Explainable Al methods A brief overview. In Proceedings of the Workshop xxAI Beyond Explainable Al Held Conjunction with the International Conference Machine Learning (xxAI@ ICMI. 20), volume 13200 of Lecture Notes Computer Science, pages 13-38. Springer, 2020.
[16] L. Hyafil and R. L. Rivest. Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett., 5()): 1976.
[17] R. Impagliazzo and R. Paturi. On the complexity of k-SAT, J. Comput. Syst. Sci., 62(2):367-375 2001.
[18] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity?
J. Comput. Syst. Sci., 63(4):512-55) 12-010,22200033 2001.
[19] M. Janota and A. Morgado. SAT-based encodings for optimal decision trees with explicit paths. In Proceedings of the 23rd International Conference Theory and Applications of Satisfiability Testing (SAT '20), volume 12178 Lecture Notes in Computer Science, pages 501-518, Springer, 2020.
[20] K. Jurczuk, M. Czajkowski, and M. Kretowski. Evolutionary induction of decision tree for large-scale data: GPU-based approach. Soft Comput., 21(24):7363-7379 2017.
[21] K. Jurezuk, M. Czajkowski, and M. Kretowski. Fitness evaluation reuse for accelerating GPU- based evolutionary induction of decision trees. Int. High Perform. Comput. Appl.. 35(1), 2021.
[22] K. Jurczuk, M. Czajkowski, and M. Kretowski. Multi-GPU approach to global induction of classification trees for large-scale data mining. Appl. Intell., 5165:566335 2021.
[23] D. Kalles and A. Papagelis. Lossless fitness inheritance in genetic algorithms for decision trees. Soft Comput., 14(9):973-99)) 090773399999999 2010.
[24] S. G. Kobourov, M. Löffler, F. Montecchiani, M. Pilipczuk, Rutter, R. Seidel, M. Sorge, and J. Wulms. The influence of dimensions on the complexity of computing decision trees. Artif. Intell., 343:104322, 2025.
[25] C. Komusiewicz, P. Kunz, Sommer, and M. Sorge. On computing optimal tree ensembles. In Proceedings of the International Conference Machine Learning (ICMI. '23), volume 202 of Proceedings of Machine Learning Research, pages 17364- 17374. PMLR, 2023.
[26] C. Komusiewicz, A. Schidler, F. Sommer, M. Sorge, and L. P. Staus. Learning minimum-sid size BDDs: Towards efficient exact algorithms. In Proceedings of the Forty-second International Conference on Machine Learning (ICML 225,, 2025. To appear.
[27] M. Kretowski. A memetic algorithm for global induction of decision trees. In Proceedings of the 34th Conference on Current Trends in Theory and Practice Computer Science (SOFSEM '08), volume 4910 of Lecture Notes in Computer Science, pages 531-540. Springer, 2008
[28] M. Kretowski and M. Grzes. Global learning of decision trees by an evolutionary algorithm. In K. Saeed and Pejas, editors, Information Processing and Security Systems, pages 401-410. Springer, 2005.
[29] M. Kretowski and M. Grzes. Evolutionary induction of mixed decision trees. Int. J. Data Warehous. Min., 3(4):68-B)) 82, 2007.
[30] D. T. Larose. Discovering knowledge in data: an introduction to data mining, volume 4. John Wiley & Sons, 2014.
[31] K. Murthy. Automatic construction of decision trees from data: multi-disciplinary survey, Data Min. Knowl. Discov,, 2(4):345-389, 1998.
[32] N. Narodytska, A. Ignatiev, F. Pereira, and J. Marques-Silva. Learning optimal decision trees with SAT. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI '18), pages 1362-1368. ijcai.org, 2018
12

---

[33] S. Ordyniak, G. Paesani, M. Rychlicki, and S. Szeider. A general theoretical framework for learning smallest interpretable models. In Proceedings the 38th AAAI Conference on Artificial Intelligence (AAAI '24), pages 10662-10669. AAAT Press, 2024.
[34] S. Ordyniak and S. Szeider. Parameterized complexity of small decision tree learning. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI '21), pages 6454- 6462. AAAI Press, 2021.
[35] J. R. Quinlan. Induction of decision trees. Machine Learning, 1(1):11-106, 1986.
[36] R. Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann, 1993.
[37] R. Lóvera,López, J. Canul-Reich. Mezura-Montes, and M. A. Cruz-Chávez. Induction of decision trees as classification models through metaheuristics. Swarm Evol. Comput., 69, 2022.
[38] J. D. Romano, T. T. Le, W. G. L. Cava, J. T. Gregg, D. J. Goldberg, P. Chakraborty, N. L. Ray, D. Himmelstein, Fu, and H. Moore. PMLB v1.0: an open-source dataset collection for benchmarking machine learning methods. Bioinformatics, 38(3):878-88 880. 2022.
[39] C. Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nat. Mach. Intell., 1(5):206-21,, 2019.
[40] M. Saremi and F. Yaghmace. Improving evolutionary decision tree induction with multi-interval discretization. Comput. Intell., 34(2)495-514, 2018.
[41] A. Schidler and Szeider. SAT-based decision tree learning for large data sets. J. Artif. Intell. Res., 80:875-918, 2024.
[42] L. P. Staus, C. Komusiewicz, F. Sommer, and M. Sorge. Witty: An efficient solver for computing minimum-size decision trees. In Pruceedings of the 39th Conference on Artificial Intelligence (AAAI '25,, pages 20584-20555 AAAI Press, 2025.
[43] I. H. Witten, E. Frank, and M. A. Hall. Data mining: practical machine learning tools and techniques. Morgan Kaufmann, Elsevier, 3rd edition edition, 2011.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The claims accurately reflect our contribution and the results of our experi-
ments.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Specific limitations of the current work are mentioned in the introduction, preliminaries, and conclusion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer:
[Yes]
Justification:
All our theoretical results are supported by rigorous mathematical proofs.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The source code, compilation instructions, and used datasets are available in the supplemental material. The unmodified original datasets are publicly available from third parties. The details about the performed experiments are included in the paper.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (c.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
cases, in which
5. Open access to data and code
15

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The source code, compilation instructions, and used datasets are available in the supplemental material. The unmodified original datasets are publicly available from third parties. If the paper gets accepted, the source code, compilation instructions, and used datasets will be made available in a public repository.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
www.sSuumiissiinnn.... /nips.cc/public/guuu guwde//ddee//// Cht///odeeeemeeieeeeee iss ssionciicy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
The details about the performed experiments are included in the paper. All details necessary to understand our main results are part the main paper. Further details are provided as part of the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Error bars are not suitable since we do not give bar plots. There is no randomness involved in our experiments, so we only report the results on the benchmark data and do not draw more general conclusions than merited.
Guidelines:
The answer NA means that the paper does not include experiments.
16

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eπror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In the paper describe all necessary details about the environment in which we ran our experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http::://ourrpp..cppuub/////thta
Answer: [Yes]
Justification: We have read the NeurlPS Code of Ethics and are sure that our research conforms to it.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
17

---

Justification: The paper focuses on the technical aspects of improving decision trees with local search. Our main contributions are parameterized complexity classification of the corresponding problems. Moreover, our experiments concern the local optimality of decision trees computed by common heuristies. Thus, our work has no direct societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All used datasets part of the Penn Machine Learning Benchmarks and licensed under the MIT License which is included in the released code. The creators of all heuristic algorithms that we use in experiments properly credited
Guidelines:
18

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi whrrdsswthhheeoeoo com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
19

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

Appendix
A Additional Material for Section 3
A.1 Proof Theorem 3.1
Proof. We reduce from PARTIAL VERTEX COVER where are given a graph G and two integers and T and the goal is to select at most & vertices of G such that at least r edges are covered by S. PARTIAL VERTEX COVER is W[1]-hard with respect to [. and unless the ETH fails, PARTIAL
VERTEX COVER cannot be solved in I (() no(x)) time
We create one binary feature d,, for each vertex one red example euw which has value in the two features dy and dy which are corresponding to its endpoints u and w, and value 0 in each other feature. Moreover, we add blue examples b1 ..... b,, which has value O in each feature. Finally, we set s == K and & == m T, where m = |E()) Observe that max = 2 D. Note that all blue examples have the same coordinates in each feature. In the end we argue how we can modify the instance such that each pair of (blue) examples differs in least one feature.
V(G). For each edge e: uw E B(G) we create
We now show that G has a vertex set S of size at most A covering T edges if and only if there exists a decision tree / of the DECISION TREE LEARNING instance of size with at most errors.
(=) Let S a solution of (G, k, r). Let T be the decision tree whose inner nodes are path and where there is one-to-one correspondence between vertices in S and the cuts of the form de >> 0 which are in T. Each left subtree of these cuts leads to a red leaf and the unique right leaf is blue. Now, observe that each red edge example eaw corresponding to edge ww which has at least one endpoint in S is put in one of the red leaves. Moreover, all blue examples end up in the unique blue leaf. Since at least r edges are incident with at least vertex of S, we conclude that T has the desired properties.
(<-) Let 7 be minimal decision tree with at most Since all blue examples have the same coordinates in all features, it is safe to assume that the inner nodes of T are path such that exactly one leaf of the last cut in T is blue leaf and all other leaves are red. Moreover, since each fcature is binary, we conclude that all cuts of use different features. Now let S be the set of vertices corresponding to features used in T. Since T makes at most & = m - - errors, and since all n² > m blue examples are indistinguishable, at most t t= m red examples are misclassified by T. Consequently, red edge examples are correctly classified by T. By construction each edge corresponding to one of these edge examples has at least one endpoint in S and thus S covers at least edges of G.
inner nodes making most / m errors.
A.2 Proof of Proposition 3.3
Proof. First, observe that all three results hold for FS-DT: 1. holds due to Theorem 3.1 Similarly, hardness results shown for computing minimal-size decision trees were the induced subgraph of the inner nodes form a path and exactly one leaf is blue and all other leafs are red (or vice versa) by reductions from V VERTEX COVER and HITTING SET instead of PARTIAL VERTEX COVER are known. More precisely, 2. was shown by Ordyniak and Szeider [34] Thm. 2], and 3. was proven by Ordyniak and Szeider (34] Thm. 3J. Second, together with Observation 3.2 we obtain analog hardness results for CUT EXCHANGE.
A.3 Proof of Proposition 3.5
Proof. By reduction from MULTICOLORED CLIQUE, Harviainen et al. [14] Thm. 5.6] showed that DTRAIS= is W[l]-hard for d + E even if 6,ax 6. In DTRAIS= the input consist of classification instance, a decision tree T with s' inner nodes and two integers t and f. The goal is to prune exactly - inner nodes of with the so-called raising operation such that the resulting decision tree T" consisting of inner nodes makes at most i errors. Moreover, in MULTICOLORED CLIQUE the input consists of a s-partite graph where each partite set consists of vertices, and the goal is to find a clique of size having exactly one vertex in each partite set. In their construction they create features per partite set of G. that is, 2 x features in total. Moreover, the input decision tree T has very restrictive structure: (1) The subgraph induced by the inner nodes is path (p1, PP.....P2)
21

---

where 2 9 2. (2) T has a unique red leaf, in other words, all leafs except one are blue. (3) Inner nodes .1-igg.......................... Potting correspond to possible values of feature i for each E [0.2 K 1]. Finally, they set & = 2 2 K. In the correctness part of their proof, Harviainen et al. [1 Thm. 5.6] argue that exactly one cut each feature has to remain to fulfill to error bound
Hence, the reduction of Harviainen et al. 11. Thm. 5.6] can easily be adapted for FSFF-DT by inner nodes which are arranged in a path and
giving as input a decision tree I'" with exactly é= 2 each of these inner nodes is equipped with unique feature of the 2 total features. The correctness can be shown similar as for DTRAIS_; for FSFF-DT is simpler since we do not need to argue that exactly one cut per feature remains. Also, the leaf-assignment cannot be changed due to the so-called foreing examples.
A.4 Proof of Proposition 3.4
Proof of Proposition 3.4 The proof is a immediate consequence of Proposition 3.5 and Observa-
tion 3.2
A.5 Proof Theoren 3.6
Proof. The main idea is to add sets of new examples for each leaf of the decision tree from THRESH- OLD ADJUSTMENT such that at least + 1 of those examples gets misclassified if the feature of some original cut is changed. We achieve this, by adding a gadget to each leaf of the THRESHOLD ADJUSTMENT instance. Moreover, our budget is chosen such that we and have perform exactly one cut exchange in each of these gadgets.
Construction. We first show that we can assume without loss of generality that no feature appears twice in the initial decision tree.
For all features di replace the first occurrence of the feature de by a new feature df, the second by df. and so on. Modify the examples E E accordingly, that is, let e(d:] = =[d.] for the new features de Now, the original instance to THRESHOLD ADJUSTMENT has a solution if and only if our modified instance to THRESHOLD ADJUSTMENT has solution.
We then start constructing our CUT EXCHANGE instance by using this THRESHOLD ADJUSTMENT instance as our starting point. For the budget i of allowed cut exchange operations, we set k = k'+ 1, where ke' is the budget of allowed threshold adjustment operations and s' is the size of the THRESHOLD ADJUSTMENT instance. Also, all examples of the initial THRESHOLD ADJUSTMENT instance are referred to as original.
Moreover, we index the leaves arbitrarily. For each leaf v with index j E [s' + 1]. we create 2(t + 1) 1) + 2(m + t + +) + new leaf examples whose leaf initially v and remains if only threshold adjustments are performed. Recall that n is the number of examples in the THRESHOLD ADJUSTMENT instance. Consider the root-to-leaf path vn, U2,..., Um for u, where U/m v. Then, add k red leaf examples eJ,1 "j,....., j, k red leaf examples 5,,1 f..:.... ",,.. and two blue leaf examples 50 53.0 For each of these leaf examples, we create & 1 copies. Moreover, we create two red leaf examples ett " Next, we create n + + 2 copies of both of these examples. Finally, we add another blue leaf example ej.
Now, we define the values in each feature. All features which are constructed far are referred to as the original features. First, we set the coordinates of all leaf examples in the original features as follows: If Ut+1 is the left child of Us we set e, ey(feat(r:)] ej, [feat(:))]]
-oo and for all 1 E [0, + 1] co and
-o,, and otherwise, let ett, (ff( = 5,, [fet((u;)] = co. Moreover, for each other original feature d', that is, d' # feat(u:) for all 8; on the path to leaf u. we set e, [d'] oo and for all I [0, k + 1] we let e,,
let ett (fea((())))))
set ey (f(fet((1;))
-oo, and +f(dd) oo.
We continue by creating is + new gadget d3,1, d2,2.... ... djkks and aj d3,s for each leaf with index j. We set (,,4,,))) = e,, [d = for 1 E kk). Moreover, we set @fold = eT [d,,a] = ct,od 3 = 0 and we set e, eddjj.] = =ejddj,l = O. For each other combination of leaf example e and a gadget feature d', we set e(d"] co. It remains define the coordinates of
22

---

d51 <
red
d,2 <1
red
d
red
dya 0
blue
red
Figure 3: The gadget used for misclassifying leaf examples that do not correspond to the jth leaf v in Theorem 3.6) Note that the class of is not relevant for this gadget.
the original examples in the gadget features. For each original example we do the following: We set e|dj,al 0 for each j E ss' + 1]. For each remaining gadget feature d' we set e[d"] = oc.
replace the jth leaf of the initial decision tree by gadget that is As the last step of the reduction, a chain of l + inner nodes as follows: The chain has k + cuts in features dz,1, d,,2,-.. dj.x. a dz.a with threshold value 1 for the cuts in features dz for 1 E [k] and red leaves the left children, except for the cut in feature aj which uses threshold 0 and that has blue leaf as the left child and red leaf as the right child. This is illustrated in Figure 3
Call the added cuts gadget cuts and the
other cuts original cuts.
which is red leaf contains the red leaf examples 5. E,r- (2) The left child of cut dj,a O, which is blue leaf contains the blue leaf examples ej. (3) The right child of cut dj.a 0, which is a red leaf contains the red leaf examples + 5,,+11 the blue leaf examples e 65.0- and the original examples ending up at the jth leaf. Since there are n original examples, for examples ej. $3,0 we have f + 1 copies each, and for examples - f.++1 have n + 2 copies each, conclude that this leaf contains more red examples than blue examples. Hence, this tree is reasonable.
Observe that the so-constructed tree is reasonable: (1) The left child of cut d3a
Correctness. We claim that this instance CUT EXCHANGE has solution with k = + 8' cut exchanges if and only if the original THRESHOLD ADJUSTMENT instance has solution with k threshold adjustments.
(+) Suppose that solution to the THRESHOLD ADJUSTMENT instance I exists. In the first step, we change the corresponding original cuts in the CUT EXCHANGE instance by assigning the thresholds of the solution to I. Second, for each leaf v of the solution to I, we do the following: If is a blue leaf, then we change the cut dj.a < d3.a < 1, and otherwise, if is a red leaf, we change the cut dj < 0 to d3,3 < 1. Clearly, we perform at most k = k + s' + cut exchange operations. Observe that after these cut exchanges all leaf examples are correctly classified: (1) The red leaf examples e3 Gza end up in the left child of cut dz. < 1 which is red leaf. (2) The blue leaf examples <),0: Ej,u1 Ej end up in the left child of cut dj.a 1 or d3 < 1, respectively, which is blue leaf. (3) The red leaf examples 35 9,,+1 end up in the right child of cut dj.a 1 or dj 1, respectively, which is red leaf.
Hence, it remains to consider the original examples: Consider the jth leaf in the solution I. If is
blue, then we replaced cut dj.a. < O with cut dj.a < 1. Consequently, all examples ending in o in the solution end up in the left child of dj,a < 1 which is blue leaf. Otherwise, if is red, then we exchanged cut dg.a < O with cut dj,3 < 1. Consequently, all examples ending in v in the solution end up in the right child of d < 1 which is a red leaf. Thus, the same set of original examples is correctly classified and thus we have at most f errors in total.
(+) Suppose now instead that solution to the CUT EXCHANGE instance exists. First, note that to separate the red leaf examples e/ 2 of,, and e,, -,22. .... 2 from the blue leaf examples tt and e, the tree needs to contains the cuts dz < for each E [A] since feature dy,1 is the unique feature in which e) Sj, differ from e..0 ',.0- Since there are + 1 copies of each leaf
23

---

examples, lack of such cut causes at least + 1 errors. Moreover, in order to separate the blue leaf examples oo 5,0 from the red leaf examples ej, 9 ( 5,++1 the tree needs to contain either the cut djaa < or d3.3
since these examples only differ in features dj,a; dj,3. Again, since for each of these examples we have at least + copies, lack of such cut causes at least + 1 errors. Moreover, observe that the cut dz.a < or d3,3 < has to appear after any cut in feature d3a since otherwise the blue leaf examples ',,0 53,0 cannot be separated from the red leaf examples e J. causing at least & + 1 errors. Furthermore, note that by the fact in which all of these leaf examples end up, the leaf labeling of the gadget is fixed, that is, is identical to the initial labeling shown in Figure 3)
Note that since the initial tree neither contains the cut dzaa < 1 nor the eut d3.s < 1, this consumes s' ++ cut exchange operations of our budget of k = k2 + + 1.. Consequently, the remaining budget for the number of cut exchange operations is k'.
Assume now that we changed the feature of some inner node z (except the case that z has a cut d < 0) to d' in our solution to CUT EXCHANGE, and without loss of generality, assume that the features on the inner nodes between the root and remain the same (but the thresholds may change). There are two cases: either (1) is original cut or (2) is gadget cut.
(I): Let w be a child of z whose subtree does not have the feature d' and let j be the index of some leaf there. Such a child exists, since each cut has unique feature in the initial decision tree. Let be the other child of z. Consider the case where w is the left subtree of 2; the proof analogous for the right subtree. In the initial decision tree T,, we have e,, E E w| for all / E [k + 1]. However, st = oc, and thus c5 E E ul in the modified decision tree T Now, we have budget to perform at most k 1 additional cut exchange operations, and therefore there is an example ej,y that ends up at the same leaf as <j.o, since none of the features d'J,,, .d,,,.....44 dj.x appear in the subtree rooted at u. This results in least ++1 misclassifications because there are + 1 copies of both examples. Hence, no feature in an original cut can be changed without yielding at least t + 1 errors.
(2): Assume that has gadget cut different from di O. Note that the features on that path from root to 2 were not changed, and thus E 2] and E 2] contain the same set of leaf examples for the original decision tree T and the modified decision tree TV. If d' is an original feature, then there cannot be a path containing cuts in features dj.1, di.2,.... dj.a and in feature dj.-- or dj.s, and thus get least ( errors. The same argument applies if we make the feature of any cut in the subtree rooted at = be an original feature. Therefore, the cut exchange operations performed in a gadget must essentially just permute the features dy.,, which can only affect the classification of the leaf examples belonging to that gadget as other examples have value oc in those features. As the leaf examples e J. S, are initially all correctly classified, there is no possible gain from doing that, and another solution can be obtained by not performing those operations.
Since one can avoid changing any features in original cuts and we apply at most - (s' 1) = k cut exchange operations in the original cuts, the solution ADJUSTMENT by performing the same threshold adjustments in the original cuts. Moreover, by setting the leaf labels to the dominate class, we then obtain a solution for the THRESHOLD ADJUSTMENT instance.
then be mapped back to THRESHOLD
A.6 Proof of Proposition 3.7
Proof. We can reduce any instance of THRESHOLD ADJUSTMENT to CUT EXCHANGE in polynomial time by Thhoremm 3.6 such that the size of the decision tree and the number of features in the new instance are bounded by a function (quadratic) of the size of the decision tree in the THReSHOLD ADJUSTMENT instance. The result then follows from THRESHOLD ADJUSTMENT being W[1]-hard with respect to the same parameters by Proposition 3.4
B Additional Material for Section 4
B.1 Proof Theorem 4.1
Proof. We adapt the algorithm of Harviainen et al. 14 for subtree raising under the same parameter-
ization. Let Dj = [eli]: e E F.) (-o0) for i [d] be the set of distinct values for feature with
an extra value of - co. A threshold sequence (4, r s)e encodes for each feature i [d] an interval
24

---

(a with 4 I r; and 4,,7 E Di, characterizing a subset of the feature space. We thus let
E[(k, ri)uetul = {e E: < e[1] S ra for all i E [d]
be the set of examples within the box defined by a threshold sequence. Let Q a dynamic programming table whose entry Q(v, (4, re) k'] is the minimum number of misclassifications achievable if our decision tree is the subtree rooted at v E on our initial decision tree T on the set of examples E[(4, re)se(a) [4] if we make at most k' threshold adjustment operations. In other words, we have a positive answer to THRESHOLD ADJUSTMENT if Q(r. (-50, oe) A:] S t when the [4] J. x) as the threshold sequence identical to (4, ri vetd except that for i = j we have the interval (max (4, n., m:). Define R((4, ra sedd, J, analogously with an interval (4, max(r;, x)).
root of the initial decision tree is r. Define L( re)
For a leaf node v and all k' < k. it suffices to count the number of examples in E T Re)ee whose class labels differ from the majority, since the leaf can be relabeled have the label of the majority. For cut v, there are two cases to consider when combining subresults of the left child w and the right child of a: either we adjust the threshold of v or not. Thus, we get a dynamic programming recurrence
min Q(u, (((4))))) feat(e), thr(u)), k"E(0,,)))
Q(u, R((,, T:) (ea(()))eaat))))) (h), k"].
Qlv, (li, (l) k]= min
min ke [0E[0,"'11] D
min @ Qwu, [(4,, rx)ee4 feat(v), k")
Q(u, R((,,, T:) re) feat(v), k" 1].
To recover one of the possible solutions, backtracking in the dynamic programming table is straightforward.
Note that the number of entries is bounded from above by n (D + 1)2d k, and computing the entry for each cut takes O(D k) time. For each of the leaves, the computation takes (nn) time. Thus, the total time complexity is O(D + 1)2d+1nnd 'nk ns).
B.2 Proof of Theorem 4.2
Proof. We adapt the algorithm of Harviainen et al. 14 for subtree raising under the same parame- terization, proceeding analogously to Theorem 4.1 The only difference is that when we modify cut, we may also change its associated feature. For a cut e with left child w and a right child u, the dynamic programming recurrence is thus
min k"E(o,A]
Qwu, I((4,, fea(()) fe)a(t), thr())),
+ Quu, R((,, re)ie feat(t), thr(w))), teat(()),tr(()), k' k"),
Quu, (4,, (()ss)) M) min
min min min Q(u [((4, J. k" -11 aED,
+ Qlu R((,, r.)e x) k'' - Kk - 1].
The time complexity of computing each state increases by factor of d, resulting in the total time complexity of O(D + 1 + nss.
B.3 Proof of Theorem 4.3
Proof. Essentially, we combine the two dynamic programs from Theorems 4.1 and 4.2 while also allowing subtree replacement as a pruning operation. Formally, in DT-PL.S are equipped with numbers kad, kex, kire kra which denote the number of allowed threshold adjustments, cut exchanges, subtree replacement operations, and subtree raising operations, respectively. As Theorem 4.1] we let D; = {eli]: e E3} U {-o) for E [d] be the set of distinct values for feature i with an extra value of oc. Again, a threshold sequence (4, ri)ieid encodes for each feature [d] an interval (li, ri] with < r; and 4, r; Di, characterizing subset of the feature space. We thus let
r((44))))E[4] = {e E:
eli] Ta for all i e [d]]
25

---

be the set of examples within the box defined by threshold sequence.
Now, however, the definition of table S and the updates complicated incorporate the 4 different operations.
The minimum number of misclassifications achievable if our decision tree is the subtree rooted at E on our initial decision tree T on the set of examples E[(4,, rx)ve(a] if we make (1) at most kld threshold adjustments,
Qlu, (1 raleeja Kad Mex Mir Klal
(2) at most Kex cut exchanges,
(3) prune exactly ke nodes with subtree replacement, and
(4) prune exactly k/a nodes with subtree raising.
Note that for subtree replacement we demand exactly K/e operations instead at most since assume the input decision tree T is reasonable and thus subtree replacement operation on T' can reduce the number errors. We also demand exactly kia raising operations since usually they increase the number of errors. Thus, have positive answer DT-PLS if Q[r, (o)e)) kad, Kex, kire kral S t when the root of the initial decision tree is Again, we define L((4,, Ta (e) J. x) as the threshold sequence identical to (4, re)ie(d] except that for i = we have the interval (max (1,, rs) and we define R((,; (((1,)r))eed) re)setd) J: analogously with an interval (4, max x)).
Consider a leaf node u. We set a corresponding table entry with ky 2 1 or K/ 2 1 to oo since in v no subtree replacement operation can be performed. For the remaining table entries corresponding to v, that is, K/ = 0 and kig = O, we do the following: For all kad S. Kad and Kex S kex. it suffices to count the number of examples in [ rs)se(4] whose class labels differ from the majority, since the leaf can be relabeled to have the label of the majority.
For cut v, there are five cases to consider when combining subresults of the left child and the right child u o: (P1) We adjust the threshold of v, (P2) we make a cut exchange, (P3) we perform subtree replacement
u, (P4) perform subtree raising at by the subtree rooted at u or the subtree rooted at w or (P5) v is not changed. Thus, we get a dynamic programming recurrence
and substitute the subtree rooted
Qlv. (1i, ri)eetq Kad Kex- Mer V/l = min(X1. X2, X3, X4, Xs) [0, Kadl kox E [0, Med. K/ [0, M/l and ki E [0, kfal for
where we always have knd
X1 min ky Ki A2 Kn ae Duni()) <k
min Q(u, L((,, re)xe(4; feat(e), Kad Mox hif kial
+ Quu
feat()) feat(e), 2), Kad k"d 1, K, Kon ky k/ Kra k/ll
X₂ min min min Q(w, T.((4: ra)se(d), feat()), x), Kad Ki Mio kill kn ki ki an
Ki jE(d] wED, ki <ki
+ Quu R((4, T re)ieja feat(v), x), kiad Kad Kex hil kig
k/al, k/e kra
minn(Blue(() (()))(a)) Red Red(((i,)))seaa)) if 8n M/ + kia and Kr 1,
X3
oo,
otherwise.
Q(u, (4,, ri) re)sejd feat(u), (h), Kag Mox- kig h/ h/ hill 8w = kifl + k Q(ue, (li, ri)veta feat(w), thr(w), Hag Max Ko kil K kml if 8.. k" + k
X, min Md R 2 0
26

---

X5
min Q/w, ((4, Ta)ead (e) thr(e)), Kad Kex
kie kirs]
Aad Rixe Aiee kig
+ Quu, Ri(4,, rt).etdd feat(), thr(e)), Kad
kad Kexx
K Kíe
kre:
Kía
krra)
where is the number of inner nodes in the subtree rooted at v, Su is the number of inner nodes in the subtree rooted at w, and sw is the number of inner nodes in the subtree rooted at u, respectively. Moreover, Blue rt)se(a)) and Red((4, (()e()))))) are the number of blue and red examples in the box (4,, re)d respectively.
Note that in X3 and X4 only node v has to be removed with the respective operation; the remaining nodes in the subtree of u. u, or w can be removed with any of the two operations.
To recover one of the possible solutions, backtracking in the dynamic programming table is straight- forward.
Note that the number of entries is bounded from above by n. (D + 1)2d k where & max(Kad, kex, kree k and computing the entry for each eut takes O k-)) time. For each of the s leaves, the computation takes (n) time. Thus, the total time complexity is O((D + 1))d+1 nss).
B.4 Missing details of Theorem 4.4
We next argue that Algorithm is correct. Clearly, if Algoorti I Joutputs True threshold assignment to each node in N respecting the error vector was found and thus the input instance is a yes-instance. For the converse assume that there exists at least one solution. Now we argue that [Algorithm I] outputs True. We show this via induction over NN J. For the base case | = O, no threshold needs to be determined and the algorithm simply checks if the error bound of each leaf is fulfilled. Now, assume an the induction hypothesis that the statement holds for all instances where |N| < q. Since the algorithm does nothing for nodes where the threshold is already known, is safe to assume that the root of I" has an unknown threshold. Moreover, assume that the left subtree Te of r has nodes with an unknown threshold and that the right subtree T, of has 22 nodes with an unknown threshold. Clearly, 21 < [N] and x2 < |N]. Tree T, witnesses that there is threshold assignment for all 22 nodes with an unknown threshold
T, for E[ > thrr"), where thr(r") is the threshold of the root r in a fixed solution. An analogous statement is true for Tg. Thus, in Line 4 we find threshold 2 thr(p") because, by the induction hypothesis, the recursive calls to Lines 6 and 7 in
which D[m) < thr(p") ) will return True. Again, by the induction hypothesis we obtain threshold assignments for all other nodes with an unknown threshold. Consequently, AAlgorithm 1 is correct.
It remains to analyze the running time of our algorithm: k nodes where a threshold adjustment performed. Moreover, there are (s') possibilities for the error vector. Finally, it remains to analyze the running time of Algoorihh I Observe that the number of recursive calls is ((og((D)) Moreover, the depth is bounded by s, the number of inner nodes of T, since after each recursive call one additional threshold is fixed. Consequently, Algorithm 1 has Donsequeetlyy/Agoriimm
There are O(s") possibilities for the up to
a running time of ())())(()) Analogously to Kobourov et al. [24] Theorem 3.2. one can show that log( O(+) E O(22. D1/s). Hence, we obtain the desired running time bound.
B.5 Proof of Theorem 4.5
Proof. We modify the algorithm behind Theorem for the FPT-algorithm for + t for THRESHOLD ADJUSTMENT as follows: After the guess of the k nodes where an operation is performed, we additionally guess which feature is used in any of these k nodes. Note that we need to consider at most d² possibilities and clearly in one branch this guess is correct. Afterwards, the algorithm behind Theorem 4.4 works completely analogously. Consequently, obtain additional factor of d in the running time.
B.6 Proof of Proposition 4.6
Proof. 1. We enumerate over all subsets of adjusted nodes of size most & in (ss*) time. For each of these subsets, we try all combinations of the new thresholds in time O(D*). To each leaf
27

---

we assign the most-dominant class label. Finally, we verify whether performing these adjustments results in at most misclassifications in time (ns)). In total, we use O 1+++D"n) time.
2. We use a straightforward brute force algorithm. We enumerate over all (D + 1)* possible combinations of adjustments and test if we made at most of them. To each leaf we assign the most-dominant class label. Further, we test if we misclassify most examples in (ss)) time each iteration.
3. We brute force over all subsets of at most k cuts to modify and enumerate over all possible d features i and D + 1 thresholds in Dr. To each leaf we assign the most-dominant class label. Finally,
we verify in (ns) time whether we get at most /. errors.
C Additional Material for Section 5
C.1 Proof Theorem 5.1
Proof. Our construction is inspired by similar construction of Harviainen al. 04 Thm. 5.10] who showed W[ for decision tree pruning with the so-called raising operation for the same parameter.
We reduce from MULTICOLORED INDEPENDENT SET where each color class has the same number p of vertices. An example instance is shown in part a) of Figure Formally, the input is graph G, and k E N, where the vertex set V(G) of N vertices is partitioned into Vi,..., Vv and [V] = N. The question is
p for each whether G contains an independent set consisting of exactly one vertex per class V. MULTICOLOORD
[x]]. More precisely, V- {uf oz :...... rf') ] and p
INDEPENDENT SET is W[1]-hard parameterized by x and cannot be solved in f(x) n((x) time
unless the ETH fails 33. The property that all color classes have the same number of vertices is only used to simplify the proof.
Outline. For an overview of our reduction, we refer to Figure 4 The idea is to create two features d: and d: per color class i such that all cuts in features d; and di" correspond to a vertex selection in Vi, We achieve this as follows: For each pair di and di of features we create examples which can only be separated in these two features and which have labels blue (separating examples) and red (choice examples) alternatingly. Hence, for each possible threshold x in features de and di the resulting decision tree T needs to contain either cut (dF,, x)) or cut (dp xz). Furthermore, for each edge we create a red edge example. If vertex of E V/2 is selected, then all edge examples corresponding to edges having an endpoint in color class which is not U will then be correctly classified by the resulting decision tree T'. Thus, we can only correctly classify an edge example if we do not select at least one endpoint of the corresponding edge. Next, we have another feature d' with only 2 thresholds to ensure that all red choice examples corresponding to selected vertices are correctly classified by the resulting decision tree T and that an edge example gets misclassifidd as blue if we select both endpoints of the corresponding edge. Finally, the inner nodes of the input decision tree T" are path with red and blue leaves alternatingly with cuts in dummy feature d. Thus, in order to obtain T, all cuts of T which are in feature d need to be changed cuts in features di. di, and dł, respectively. Construction.
Description of the data set: A visualization is shown in part b) of Figure 4
For each edge (v7, vu} E E(G) we add an edge example e(uf, vj). To all these examples we assign label red.
For each E [x]] and each E [p 1] we add a blue separating example b(i, x).
For vertex of E V; we create a red choice example cf.
We add a red dummy example r, for each i E [(p [(p- (ip-1)-k= + 1] and a blue dummy example b for each i (p-1)- ss..
We create red enforcing example r" and a blue forcing example by To make the input tree I' reasonable, we add Z copies of b", where Z is the total number of red examples
28

---

2
d)
45
of
red
red
1/3
4
blue
67
1/
1/3
13
15
V/
red
red
47 2
8)
blue
1
bluu
1.5
2
2.5
c R(())
6]
of (012) FDD)
A Rest
red
red
45
d: Rest
B(e))
6[1.1]
E(v
6 (0.2)
B(e))
45
< B[e))]
62, 13
E(v <3
Rests
blue
blue
45
1.5
d3 Rest c E((e))
M2, 1) E(()) <2
B(eg)
6(3, 1)
E((g)
Rest
red
45
dg
Rost c) B(e)) 6(3,1)
E(v5)
Pr edgo examples
Rest
blue
2 10
blue
d"
2
3
2(p
1)
blue
red
blue
2
b2
0g
Rest"
Figure 4: visualization of the reduction from the proof of T'heorem 5.1
Part a) shows a MULTII
COLORED INDEPENDENT SET instance. For the sake of the Illustration, the property that all partite sets have the same size is dropped and thus 2(p 1)x + 2 = 10. A multicolored independent set is depicted in orange. Part b) shows the corresponding classification instance. Here, E(u?) ) is the set of all edges incident with vertex v/- Rest,, Rest." Rest". and Rest" refers to all other examples shown in that feature (the precise set differs in each feature and is always a subset of all examples having the default threshold of that feature). All possible cuts in the classification instance shown by "I". Moreover, cuts in the input decision tree are shown in violet and cuts of the solution decision tree are shown in brown. Part c) shows the input tree T". Part d) shows one possible solution tree T..
we create. For simplicity, in the following, we will only talk about the concrete forcing example b".
Note that we add = [E(G) edge examples, N choice examples, - k = (p- x separating examples, 2(p 1) + 1 dummy examples, and further examples. Thus, the number of examples polynomial in the input size.
For each E [x]. we add two features de and d?" also add two other features and d. Thus, we have 2 A + 2 features.
remains describe the coordinates of the examples in the features. Initially, we declare a defauls threshold default(d") for each feature d'. Then, each example e has the default threshold in each feature, unless we assign e different threshold that feature.
For each feature d; we set default(d,) (dx)) = for each feature di" we set default(d?)) = 1, for feature d", set default(d") 2, and for feature d, set default(d) 2(p +.
For each edge example e(uf' uz) we set eld,] c(d?) z, eld,1 eld?] 2. and e(d") = In each other features e set to the default threshold.
For the separating example e = b(i, .r) we set eld;] eld?"] = x + 1/2. In each other features e set to the default threshold.
For the choice example = of we set e(d,] eld?'] ] = æ. In each other features e set to the default threshold.
The red enforcing example v* has the default threshold in every feature. For the blue forcing example 6", we set b" [ddd"] and in each other feature we use the default threshold.
29

---

For the red dummy example rs. we set r:[d = 2i - 1, and in each other feature we use the default threshold. Finally, for the blue dummy example d;. set by = 2i, b,(d*] = 1, and in each other feature we use the default threshold.
So far, our construction is very similar to the one of Harviainen et al. [14 Thm. 5.10]: Additionally to their construction we have the blue and red dummy examples and the feature d. Anything else is identical. The input decision tree, however, is substantially different.
The inner nodes of the input tree T" are a path with cuts only in feature d. Moreover, for all cuts the leafs are alternatingly labeled with red and blue, starting with red. Observe that T consists of (p 1) 2x 1 inner nodes. This completes our construction.
Description of the input tree T For a visualization of T", we refer to part c) Figure 4
(p- (p 1)- 2x 1. Thus, t= O. Note that each edge example differs at most 4 times from the default thresholds, that each separating and each choice example differs exactly 2 times from the default thresholds, that d' differs exactly once from the default thresholds, that r" always has the default thresholds, and that each dummy example differs at most 3 times from the default thresholds. Thus, δmax = 6.
Parameters dmax. Error bound and E: Finally, we set 0, and =
Note that since L = 0. we can perform a cut exchange on any node and thus the sole purpose of T' is to fix the structure of the inner nodes and the leaf labeling.
Reasonability of the input tree T': Observe that each Icaf except the blue leaf of the last cut in T contains exactly one example of the same color. Moreover, observe that this blue leaf of the last cut of T" contains the red enforcing example, all red choice examples, all red edge examples, all blue separation examples, and all Z copies of the blue forcing example, where Z is the total number of red examples, we conclude that this blue leaf contains more blue examples than red examples. Consequently, T' is reasonable.
Correctness. We show that G has a multicolored independent set if and only if all cuts of T" can be exchanged to obtain a tree T making at most ( = 0 errors.
(+) This direction of the correctness proof is almost analogous to the same direction of the correctness proof of Harviainen et al. [14] Thm. 5.10J. For completeness, we give all details. More preciscly, the solution decision tree T in both proofs is identical and here we additionally need to argue that all dummy examples are correctly classified by T. For a visualization of T, we refer to part d) of Figure 4
Let S = fu.t i E [k]] a, E [p]} be a multicolored independent set of G. We perform a cut exchange on all nodes of T" such that in the resulting tree T, in feature di we have exactly one cut at thresholds x E {1.5, 2, 2.5, .p}...p} for which x S az Similarly, for each feature di in tree T, we have exactly one Moreover, in I we have the unique cut in feature d' Furthermore, in T we first have the cuts in feature di in ascending order, then the cuts in feature df in descending order, then in feature dē in ascending order and so on. The last cut of T is in feature d'. In other words, T has the cuts {df < 1.5, dř < 2,..., di < 01,dd d? > p- 1/2,.... di > 01. a1...., de > ar,, d' < 1] in that specific order. Moreover, the class assignment to the leaves is not changed.
thresholds x E {1, 1.5, 1.5, 2.5, ..... P pp-11 1/2) for which a, S
Since T' has (p - 1). 2k + inner nodes and since perform cut exchange each of them, obtain k = (p - 1) 2x + 1 and { = 0. Thus, it remains to verify that T makes no errors.
Outine: First, we make an observation for examples using the default threshold in a feature and second we use this observation to show that all examples are correctly classified by the solution tree T.
Step 1: Recall that T has no cut in feature d. Observe that if any example e lands at some inner
node of T corresponding to cut in feature d' where d' = di or d' = d; for some i E [x] and e 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. Moreover, any example e with the default threshold in feature d' is put into the left subtree of the cut in feature d². Since 7 is a path, any 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 example e to land in a different leaf, we only need to consider cuts of T in features where e has a different threshold than the default threshold.
30

---

Step 2:
We distinguish the different example types.
By construction, the red enforcing example r' always has the default threshold. Thus r* ends up in the left child of the last cut of 7 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, by ends up in the right 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 2 = x x 1/2 and x [p - 1] and recall that 0; E IN is the index of the selected vertex of color class i. Without loss of generality, assume that 2 < ag. By Step 1, will end up in the cut de < 1.5 of T' Also, recall that the next cuts in T' are di < 2, ... di < o; in that specific order. Consequently, goes to the left subtree of the cut d5 < 2 + 1/2, which by construction is blue leaf. Thus, e is correctly classified as blue by T.
Step 2.3: Consider a red choice example = of where x E [p].
First, consider the case that + a, Then the argumentation is almost identical to the blue separating examples: Without loss of generality, assume that x < ag By Step I, e will end up in the cut d < 1.5 T. Also, recall that the next cuts in T are di < 2, ....., d, < a; in that specific order. Consequently, e goes to the left subtree of the cut d < x + 1/2, which by construction a red leaf.
Second, consider the case that x = aq. Observe that in all cuts of I in features dē and di" example will always go to the right subtree. Since e has the default threshold in each features different from d, and d/. example e ends up in the left leaf of the last cut d' < 1 of T which is a red leaf.
Thus, in both cases is correctly classified red by T.
Step 2.4: Consider a red edge example e = (of ). By assumption, is a multicolored independent set. Hence, at least one of the two endpoints of and vz is not contained in S. Without loss of generality, assume that of o S and that i j. The argumentation is analog to the red choice examples ef where x * a4: Without loss of generality, assume that x < ag. By Step 1, e will end up in the cut d < 1.5 T'. Also, recall that the next cuts in T are d <. 2,.... de < a, in that specific order. Consequently, e goes to the left subtree of the cut d, < x + 1/2, which by construction is a red leaf. Thus, is correctly classified as red by T. Step 2.5:
remains to consider the dummy examples. First, consider a red dummy example Th- Recall that Th uses the dummy thresholds in all features except d. Since is not used in T, the red dummy example Th, analogously the red enforeing example r", ends up in the left child of the last cut of T (which is d² < 1) which is a red leaf. Second, consider a blue dummy example by Recall that by uses the dummy thresholds in all features except d and d', Hence, analogously to the blue forcing example b", the blue dummy example bn. ends up in the right child of the last cut of T (which is d" < 1) which is blue leaf.
Consequently, the tree T has no classification errors.
(+) Let T be a solution of the cut exchange problem, that is, up to all cuts of the initial tree 7" have been changed such that 7 makes no errors.
Outline: This direction of the correctness proof follows a similar route as the corresponding direction of the correctness proof of Harviainen et al. [4] Thm. 5.10]. Step 4, however, is substantially different.
We first show that T has to include the unique cut in feature d". Second, we show that T needs to contain at least on of the two cuts di of our choice of the size of the initial tree T" and f = 0 we then conclude that for each i and each x exactly one of the cuts of x and d? > x 1/2 has be preserved. Fourth, we show that the cuts T in a feature di (or d? do not have gaps, that is, if x is the largest (smallest) threshold, such that the cut df
and d? > x 1/2 for each i and each x. Third, because
(d? > x) is included in T, then also all cuts di < z for each < x (d, > z for each x < 2) have to be contained in T. For example, the tree shown in part d) of Figure 4 which has 0 errors fulfills this property. 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 multicolored independent set.
31

---

Step 1: Note that the blue forcing example b* and that the red enforcing example r* only differ in the binary feature d'. Thus, T has contain the cut d' 1.
Step 2: Our aim is to show that at least one of the cuts d. < x and dp > > 1/2 for any i E [x] and x E {1.5, 2, 2.5,.... PP has to be included in T. Without loss of generality assume that xr is b(i, I - 1) we
an integer. Note that x 2 2. By construction, for the blue separating example have e[d;] e|d?] = x - 1/2 and for the red choice example
of we have eld]5] = eld?]= x. Furthermore, note that b(i, x--1 1) and cg have the default threshold in each other feature. Consequently, only the cuts di < x and d?? > x 1/2 can separate b(i, x 1) and cf. Since T has no classification errors, we thus conclude that at least one of the cuts dē < x and di > x - 1/2 has to be included in T.
Step 3: Recall that 8 = (p-1) (pp-1) 1)- 2x +1 1 and f. = 0. By Step 1,7 T has to include the cut d' > 1. By 1/2 for any i [x]] and x E {1.5, 2, 2......... p) ........
Step 2. at least one of the cuts dí < and d.
has to be contained in T. Note that these are exactly (p - 1) 2x pairs of distinct cuts. Consequently, T has to contain exactly one of the cuts d, < x and d? > x 1 1/2.
Step 4: We show that for each E [K] there is a threshold z; such that T contains all cuts dī < z Ig. Assume towards contradiction that this is not true. Let P. S {1.55, 2, .........p be the subset of consecutive thresholds including 1.5 such that for each 2; E P. the tree T contains the cut di < Iz. Analogously, let P." C {1.5, 2, 2.5,..... ......... pp} be consecutive thresholds including such that for each T2 E P." the tree T contains the .......-PP)). p). Now consider the cut d? > T2 10-2-1. 1/2. According to our assumption, U?? * {1.5, 2, 2.5, .............. ..............
where S Ix and all cuts di > where
the subset
first cut di < x or di > x 1/2 of T (from the root) such that x E {1.5, 2, 2.5. ... \ (P& U PP?)) ). Without loss of generality assume it is the cut d5 < x. threshold in P. Clearly, = < z. Moreover, 2 S 1- because otherwise if z = I 1/2 then we would have E P. contradiction to the fact that P,S. is maximal. Also, observe that for threshold x 1/2 we have x 1/2 & P. U p2, Without loss of generality, we assume that x is an integer. We now exploit the fact that x & P. UP? is the first threshold such that either d; or di > I 1/2 is contained in T. Since also x- 1--1/2 4 P. UP? and according to our choice of x at the time when in T cut d5 < x considered, neither the cut di x - 1/2 nor the cut d? x- 1 was considered. Thus, the red choice example c.- and the blue separating example b(i, x - 1) are both moved into the left subtree of the node with cut de < x which is a leaf implying that one of them gets misclassified, contradiction to the fact that O. Thus, P.C and P form a partition of (1.5, 2.2, ...
By choice, E P. Let be the largest
We would like to note that one can additionally show that all cuts de < x contained in T appear in ascending order in T, that is no cut di < appears before a cut d < x for some 2 > x. This fact, however, is not necessary to obtain the multicolored independent set.
Step 5: Consider one fixed i E [no]. Let I; be the largest threshold such that the cut di < x2 is contained in in T. In other words, x; is the largest threshold contained in P.S. Thus, each threshold which is smaller than x is also contained in P. and all thresholds larger than I; are contained in P?? Next, assume towards contradiction that x is integer, that is, x; = 9 + 1/2 for some integer E Ip- ip-1] Now, observe that the blue separating example b(i, q) is put in the right subtree of each cut di < for each = S x; and for each cut de the only features such that b(i, q) does not use the default thresholds. Now, since the red enforcing example ,d always uses the default thresholds, we conclude that T cannot distinguish b(i, q) and r" and consequently T makes at least one error, contradiction to the fact that t = O. Hence, x, is an integer.
for each æ S z. Recall that di and di are
We let v.' be the selected vertex of color class i. Furthermore, let S := (uf : i E [<]]]
Step 6: It remains to verify that S is a multicolored independent set. By definition, S contains exactly one vertex of each color class. Hence, it remains to show that S is an independent set.
Observe that since T has no classification errors, it is sufficient to show that T cannot distinguish the blue forcing example b" and red edge example e = (vf", vz)) if both endpoints of and vf are contained in S: Let e e(vf rz) be an edge example where vf,, vj E S. Note that analogously to Step 5, the red edge example e ends up in the right subtree of each cut features d,s, di df. and dz Since the blue forcing example b" uses the default thresholds in these 4 features, this is also true for b* Now, observe that the only other feature where e or 6 to not use the default thresholds
32

---

is d'. But in d' we have e[d"] 1- = b" [d"). Thus, T cannot distinguish the blue forcing example b* and the red edge example (v% vf). Consequently, S is also an independent set.
Lower Bound. Recall that d = 2 K + 2, mmx = 6. = 0, and f = 0. Since MULTICLLORED INDEPENDENT SET is W[1]-hard with respect to K. B3, we obtain that CUT EXCHANGE is W[1]- hard with respect to d even if mmax = 6, = 0, and = O. Furthermore, since MULTICOLORED INDEPENDENT SET cannot be solved in f(t)) ((())) time unless the ETH fails [3, we observe that CUT EXCHANGE cannot be solved in f(d) [Z](() time if the ETH is true, where |Z] is the overall
instance size, even if mmax 6 0, and t 0.
C.2 Proof of Theorem 5.2
Proof. Our construction is inspired by similar construction of Harviainen et al. 04 Thm. 5.10] who showed W[[]-hardness for decision tree pruning with the so-called raising operation for the same parameter. Our construction, however, is substantially more involved due to the restrictive nature of the threshold adjustment operation.
We reduce from MCL.TICL..RED INDEPENDENT SET where each color class has the same number p of vertices. An example instance shown in part a) of Figure Formally, the input is graph G, and K E IN, where the vertex set V(G) of N vertices is partitioned into Vi,.... Vx and [V
p for each i E [x]] More precisely, Vi = { u, u...... of)) } and p K = N.. The question is whether G contains an independent set consisting of exactly one vertex per class V. MULTICOLORED
INDEPENDENT SET is W[1]-hard parameterized by k and cannot be solved in fxx n2(()) time
unless the ETH fails 3 The property that all color classes have the same number of vertices is only used to simplify the proof.
Outline. For overview of our reduction, refer to FFigure 5| Similar to [heeremm 5.1 the idea is to create two features di and de per color class such that all cuts in features d; and di correspond vertex selection in V4. We achieve this follows: For each pair d, and dł of features we create examples which can only be separated in these two features and which have labels blue (separating examples) and red (choice examples) alternatingly. These are the important thresholds of features d, and d,- Hence. for each possible threshold x in features d, and di" the resulting decision tree T needs to contain either cut (d5 .x) or cut (d? .z). Furthermore, for each edge we create red edge example. If vertex v E V; is selected, then all edge examples corresponding to edges having an endpoint in color class i which is not U; will then be correctly classified by the resulting decision tree T. Thus, we can only correctly classify an edge example we do not select at least one endpoint of the corresponding edge. Next, we have another feature d' with only 2 thresholds to ensure that all red choice examples corresponding to selected vertices are correctly classified by the resulting decision tree T and that an edge example gets misclassified blue if we select both endpoints of the corresponding edge.
In the proof in Theorem 5. for cut exchange, the initial tree T" was path with red and blue leaves alternatingly. For the threshold adjustment operation we need a more complex structure of T": Since we are only allowed do threshold adjustments, cannot add a dummy feature with dummy cuts as in the proof in Theorem 5.1 for cut exchange. Instead, we extend each feature d, and de by dummy thresholds which are used in the initial tree T'. Since T' is reasonable, we also add new dummy examples rf and of alternatingly in features de and d:- This, however, creates a new problem: since = 0 doing threshold adjustment in feature d, moves both red and a blue dummy example in the same (left) subtree. Thus, as in the proof in Theorem the left subtree is not simply a leaf, but another inner node with a cut in a new rescue feature p; to separate the differently labeled dummy examples. Our construction of these rescue features together with the tightness of the budget k ensures that in any optimal solution no threshold adjustment in any rescue feature is possible. In other words, all threshold adjustments need to be done within the features d, and di"
Construction. Compared to Harviainen et al. 114 Thm. 5.10] and to reduction in Theorem 5.1 our construction here is significantly more involved. On the one hand, we need way more examples and features and on the other hand, the input decision tree is not only a path. Next, we describe our construction in detail.
Description of the data set: A visualization is shown in part d) of Figure 5
33

---

Figure 5: A visualization of the reduction from the proof of Theorem 5.2 Part a) shows MULTICOLORED INDEPENDENT SET instance. For the sake of the illustration, the property that all partite sets have the same size is dropped. A multicolored independent set depicted orange. The vertex selection in the partite set Vi. and the final cut in feature d" Part b) shows the part of the input tree T" corresponding to the vertex selection in the partite set Vi together with the final cut in feature d' Part c) shows the part of a solution tree T corresponding to the vertex selection in the partite set V, together with the final cut in feature d" The cuts where threshold adjustment was applied are marked orange and they indicate the selection of vertex of V,. Part d. shows the corresponding classification instance, Here, ((v)) is the set of edges incident with vertex Rest refers all other examples not shown that feature (the precise set differs in each feature and is always a subset of all examples having the default threshold of that feature). Features at) and x; for æ E {p, 9) and j E {2, 3) are not shown. Note that thresholds -4 to -I only exist for features di and that thresholds d? only exist for features d? All possible cuts in the classification instance are shown by 4I". Moreover, we use a 4 coloring to distinguish cuts of the initial tree 7'' and a solution tree T: 1) cyan cuts are used by both T" and T, 2) brown cuts are only used by T', orange cuts are only used by T. and 4) black cuts are neither used by T' nor T.
Rest(of)
Rest(or)
100
5
4 3-
blue
|
|
red
6(1, 21,2) i/
6(1, 22 b | dEiirra 1(1,1)0)'0 8/2
Due
100
PE
blu
EEGl)r D(L ((.1))) 1) W3 e (n 1 [b], 2) 11 |e E (v Best
Rest
Rost
| 2ebdrrd |
bue
blue
red
Resf B(e))) M(11))) w. 1et let (e by [[L, ()) bo (uG)))
Blue
blue
3
red
2,5
6(1, 1)/1))///// b
2
red
dlvl 14 (22 1 (L ra
1622 (2 1 l ( ( 14
Rest(r))
Restip?)
Rest(d")
(33 ()3 1)r2 1 (e))))
5
1603 1 1) wy Ie (e
blue
W
blue
|
|
red
by 2
edge examples
bls
blue
1.5
red
Dlee
red
Rest (i
rod
Rest Eldd)
Dlus
6/4
15
19 15
d5 10
b/
d5: A
d7
d3
d3
d":
34

---

For each edge {uī vf} E E(G) we add an edge example e(uf, vz). To all these examples we assign label red.
For each E [x] and each pp- 1] we add a blue separating example b(i, x).
For vertex of E V, we create red choice example ci.
We create red enforcing example r" and blue forcing example b". To make the input tree T" reasonable, we add (N² + copies of b". For simplicity, in the following, we will only talk about the concrete forcing example 6*.
For each feature dī and each j [2(p 1)] we add blue dummy example bj5 and red dummy example rys. Analogously, for each feature di and each j [2(p 1)] we add blue dummy example bj," and red dummy example r
For each i [k] and each E [2(p 1) + 1], add blue filler example bj and red filler example ry*
Note that we add M == [ edge examples, N choice examples, N-H = (p-1) K. separating examples, 8(p 1)- dummy examples, (4(p - 1) + 2) k. filler examples, and 2 further examples. Thus, the number of examples is polynomial in the input size.
For each i E [x]. we add six features d,,, di P. p T. and q. We also add another feature d". Thus, we have
features.
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 e has the default threshold in each feature, unless we assign e different threshold in that feature.
For each feature d,, we set default(d)) = p. for each feature di, we set default(d?)) = 1.
For each feature P.C. we set default(p,)) = 2. Analogously, for each feature p?" we set default(p," 2.
For each feature q. we set default(())) 2(p 1) + 1. Analogously, for each feature q7" we set default(g) (p +
For feature d', set default(d") = 2.
Now, we are ready to assign the coordinates to all examples.
For each edge example e = e(uf, uf) we set e[45] = c(dp] = x, eld, = cld?)
2, and el [d' = 1. Next, we distinguish three different values of x: (1) if x = 1, we
set elp, 5
1. (2) if = p. we e epp²1 1. (3) if
< p. set e|a,51
2r
and e/q, = 2(p
1. We do similar for 2, that is, (1) = 1, we set elp, = 1. (2)
if = p, set elp"]] 1. (3) i <2 p. set e(g,5] 2= and end 2(p 2 +1.
In each other features is set to the default threshold.
For the separating example set e|p;1] 2x, and elp;" = 2(p 1 x). In each other features is set to the default threshold.
b(i,x) we set e[d,5] = e[d?] x + 1/2. Moreover,
For the choice example e = c we set c[d,] = c(d?] ] = x. Next, we distinguish three
different values of x: (1) if 1, we set elp 1 = 1. (2) if r p. set elp;"= 1. (3)
if < x < p. we set e|g," = 2x and elg. 2(p - x) + 1. In each other features is set 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.
Let E [K] and
[2(p- 1)]-
35

---

(A) For the blue dummy example bj5, we set setel/d]] =
-p++11
Note that -((p 1) - cldF] 1 -1. Moreover, if j is even, we set clg,- =
(B) For the blue dummy example e = b3², we set e e(d])
+ 2(p 1) - j = 3p 1 - j.
Note that p + 1 - e[d]] 3p- 2. Moreover, if j is even, we set elq;"| = j.
(C) For the red dummy example = r we set e e[dr] 2(p - 1) 1 +j = 22 +1
Note that 2 1) S eld]] v 1. Also, set e = 1. Moreover, if > and is
odd, we set elg = j.
(D) For the red dummy example E = rj" we set el eld;] = p + 2(p 1) -j= 1 j. Note that p- + - c[dF] S 3p - 2. Also, we set elp?] = 1. Moreover, if > and j is odd, we set elg?" = j.
Let E [s] and j E [2p - 11.
(A) For the blue filler example e life. we set el4,) (j 1)/2 11/2 eld?] and e(d') 1. Next, we distinguish the precise value j: (1) if = 1, we set elq,"
(2) if 2p 1,
we set e|g?] 2. (3) if 1 < j < 2p 1 and j is odd, we set elg, = j and e|q;'|
2p + 1 - J. (4) otherwise, j is even, we set elg,- = j. and e e(g? = 2p jj-
(B) For the red filler example e ry. we set e(d,) (j + 1)/2 = =e[d?]. Next, we
distinguish the precise value of j: (f) j 1. we set elp,) = 1 if = 2p
we set elp?" = 1. (3) if j = 2, we set elg." = 3. (4) if 1 < < 2p - 2 and j is odd,
we set elg, = = elq²). (5) otherwise, if 2 < j and j is even, we set c(q = j + 1.
and elg, =j j-
Description of the input free T": For a visualization of parts of TV, we refer to part b) of Figure 5 Intuitively, tree T' consists of path P of cuts in features d5. di. and d", and each left subtree of this path (except for the unique cut in feature d') consists of a unique cut in features af or x? where I E {p. q).
First, we formally describe path P: It consists of the cuts de < <2pp + < < + 4,...
of <
-1,d5 <1, d > 3p 3..... di > p, dž < -2p + 3. ...... dz > p. <. Second, we describe the remaining cuts: (1) The left subtree of the cut d < -2p + 3 consists of the cut p. < 2. (2) The left subtree of the cut d/ > 3p 3 consists of the cut p. < 2. (3) The left subtree of the
cut d. < 2p + 2 + j for j 2 consists of the cut of < jj= + 1. (4) The left subtree of the
cut di > 3pp - 2 j for j 2 2 consists of the cut of 11
the leaves: The left leaf of the cuts p < P < 2. gf < <j, and q," < for even j is red and their right child is blue. For all remaining cuts, that is for cuts 9;- j. q. <) j for odd j. and for d' 2, the left child blue and the right child is red.
Finally, it remains describe the class assignment
Observe that T' consists of exactly 8(p 1) K 1 cuts.
Parameters 6max, Error bound and E: Finally, we set == 0, and l: = (p- - 1). 2x. Note that each edge example differs at most 13 times from the default thresholds, that each separating and each choice example differs exactly 6 times from the default thresholds, that by differs exactly once from the default thresholds, that r" always has the default thresholds, that each dummy example differs at most 3 times from the default thresholds, and that each filler example differs 7 times from the default thresholds. Thus, 9max I 20.
Reasonability of input tree T": Observe that each leaf attached cut in feature x; or 2द for e {p. t) and i E [k] contains exactly one dummy example of the same class. Moreover, observe that the red leaf of the cut d' < contains all blue separating example, all red choice examples, all red filler examples, and the red enforcing example. Thus, the red leaf contains more red examples than blue examples. Finally, consider the blue leaf of the cut d' < 2. This leaf contains all red edge examples, all blue filler examples, and the (N2 + 1) copies of the blue forcing example. Thus, the blue leaf contains more blue examples than red examples. Consequently, the input tree T' is reasonable.
36

---

Correctness. We show that G has multicolored independent set if and only if k: = (p- 1)-2kc cuts T we can perform a threshold adjustment operation obtain a tree T making at most 0 errors.
(+) Let 5 = {oet : E [x=], at E [D]] be a multicolored independent set of G. We now show how to construct tree T from T" with most k (p 1) 2x thresholds adjustments such that 7 has O errors. For a visualization of parts of T', we refer to part c) of Figure 5
For each color class i, we perform a threshold adjustment operation in the first 2(a; 1) cuts of T" in feature d, and in the first 2(p ap;))) cuts in feature d²" Moreover, the newly adjusted thresholds in di range from 1.5 to a, in that order and the newly adjusted thresholds in d, range from p 1/2 a, in that order. Note that these are 2(p - 1) threshold adjustment operations per color class and thus k (p- - 1) 2n: threshold adjustment operations in total. Now, we describe these operations in detail: We change cut d, < -2(p - 1) + 1 = -2p + 3 to d, < 1.5, d, < -2p + to de < 22 and so on, until de < 2(p 1) 2(0;
2(p az) to d, < dg Moreover, we change cut d > 3p 3 to d > 1/2, dp > 3p- 40-4100 to d > p-pp-1 and so on, until d² > 3p - 2 2(p 0.) = p+ 20;- 2 to de > ag. Moreover, note that we do not change the class of any leaf.
Observe that the new tree? might not be reasonable anymore: For example, consider the selection of vertex of E 1/2 shown in part c) of Figure 5: The cut dř < -1 puts all examples into its right subtree since its parent has the stronger cut d,
Now, it remains to verify that T makes no erTors.
Outlin:: First, we make observation for examples using the default threshold in a feature and second we use this observation to show that all examples are correctly classified by the solution tree T.
Step 1: Observe that if any example e lands at some inner node of corresponding to a cut in feature d' where d' = de or d' = de for some i E [x] and has the default threshold in that feature d', that is, eld'] Moreover, any example with the default threshold in feature d' is put into the right subtree of the cut in feature d' which is a Ineg leaf. Consequently, any example e which has the default threshold in each feature will be contained in the red leaf of the cut d' < 2. Also, in order for example to land in a different leaf, we only need to consider cuts of T in features where e has a different threshold than the default threshold.
default(d'). then e will always go to the right subtree of that node.
Step 2: We distinguish the different example types and show that T makes no errors.
Step 2:1: 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 red leaf. Furthermore, the unique feature in which the blue forcing example b* does not have the default threshold is d". Thus, b* ends up in the left child of the last cut of T which is a blue leaf.
Thus, examples r" and b* are correctly classified by T.
Step 2.2: Consider a blue separating example = b(i, 2). Recall that 2 == 1 and x E [p 1] and recall that a; E NN is the index of the selected vertex of color class
First we consider the case z S aj. This implies that at least one threshold adjustment is done in feature dfS. By Step
will end up in the cut di < 1.5 of T. Afterwadss, the next cuts are dē < 2,, de < 2..,....dd dd < ag in that specific order. Consequently, goes to the left subtree of the cut df < < 1/2 (note that + 1/2 is an integer and 2 + 1/2 2). Observe that the root of this left subtree is the cut g. < h for some h < 2p 1 such that h is odd. Consequently, e is put into the which is a blue leaf. Thus, is correctly classified as blue by T.
left subtree of the cut q,
Second, we consider the case > ag Observe that all cuts in feature d. have the form d. < h with some threshold h S a, < z. Hence, e is put into the right subtree of each cut in feature d of T. Now, the argumentation is analogously as in the first case for feature d? and since T contains the cut de > a; example e is put into the left subtree of one of the cuts in feature di-
Step 2.3: Consider a red choice example e = of where x E [p].
First, consider the case that * a, Then the argumentation is almost identical to the blue separating examples:
37

---

(A) assume that I < d;. By Step 1, will end up in the cut de < 1.5 of T. Also, recall that the next cuts in T are d 2, d. < 2.5, dr < a; in that specific order. Consequently, e goes the left subtree of the cut de < + 1/2. If, I = 1, then the root of this left subtree is the cut p. < 2.
Otherwise, if o 2 2, then the root of this left subtree is the cut g < h for some S 2p- - such that h is even. Observe that in both cases e is put into the left subtree of the cut P3 < 2 or of < h which is a red leaf.
(B) assume that x > ag Observe that all cuts in feature di have the form di < h with some threshold h I a, < x. Hence, is put into the right subtree of each cut in feature di of T. Now, the argumentation is analogously as in the first case for feature df and since T contains the cut d? > ag. example e put into the left subtree of one of the cuts in feature d?.
Second, consider the case that & = ag. Note that in T all cuts in feature d5 have the form df < h for some h S a, and that all cuts in feature de have the from de h for some h 2 ag. Thus, is put into the right subtree of each of these cuts. Since uses the default threshold in feature d', e is put into the right subtree of the cut d' 2 which a red leaf.
Consequently, in all cases e is correctly classified as red by T.
Step 2.4: Consider red edge example e = (uf", vz). By assumption, S is multicolored independent set. Hence, at least one of the two endpoints of and vz 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 < 0g By Step 1, e will end up in the cut d, < 1.5 of T. Also, recall that the next cuts in T are d < 2, ...... de < 0; in that specific order. Consequently, goes to the left subtree of the cut de < x + 1/2. If, x = 1, then the root of this left subtree is the cut p3 < 2. Otherwise, i 2 2, then the root of this left subtree is the cut 9f < h for some h S 2p 1 such that h is even. Observe that in both cases is put into the left subtree of the cut D," < or q."
which is a red leaf. Thus, e is correctly classified as red.
Step 2.5: (A) Consider red filler example
r..- The argumentation is very similar to the red choice examples. First, consider the case * a; and assume without loss of generality that a, (the case j > ag follows by considering feature d? instead). By Step 1, e will end up in the cut d5 < 1.5 T. Also, recall that the next cuts in T are di < 2,... ..... di < a; in that specific order. Next, observe that the cut di < (j + 1)/2 puts e into its left subtree. If = 1, then the root of this subtree is p < 2 and puts into its left subtree which is red leaf. Otherwise, if > 2, then the root of this subtree is g." < j + 1. If j is even, cut of < j + 1 puts e into its right subtree which is a red leaf. Otherwise, j is odd, cut 9;- <) j + puts into its left subtree which is a red leaf.
Second, consider the case j = a;. Again, observe that in T all cuts in feature df have the form dif for some h S a; and that all cuts in feature di have the from di > h for some h 2 a, Thus, is put into the right subtree of each of these cuts. Since uses the default threshold in feature d" e is put into the right subtree of the cut d' < 2 which is a red leaf.
Hence, e is correctly classified as red.
(B) The argumentation for a blue filler example e = bj* is very similar: If j A 0g then the cuts p < 2 and 9; <j + 1 will put into its blue leaf. Otherwise, if as then e ends up at the cut d' < and then e is put into the left subtree which is a blue leaf. Consequently, e is correctly classified as blue.
Step 2.6: (A) Consider red dummy example e =rj First, assume that a; 2. Then the first cut of T in feature de d, < 1.5. Hence, e is put into the left subtree of the cut d < 1.5. The root of this subtree is the cut P < 2. Consequently, e is put into the left subtree of the cut p. < <2 which red leaf. Second, consider the case that a; = 1. Then, the cuts of T in feature d. are di < 22p + 3, di < 22p + 4, ... ,d < -1, de < 1 in that specific order. If = 1. then is put into the left subtree of the cut d, < -2p + whose root is the cut D < 2. Otherwise, if j 2 2,
then is put into the left subtree of the cut d, < -2p + 2 +j whose root is the cut of <j + 1. In
both cases e is then put into the red leaf of this cut.
The argumentation for a red dummy example rj> follows analogously with the features d; ,p7 and 9, instead of d; p,5 and q.
38

---

(B) The argumentation for the blue dummy examples = b/ and by follows analogously as for the red dummy examples. The difference is that the cuts p. 2 and q," < + put e into the blue leaf of this cut.
Consequently, all dummy examples are correctly classified by T.
Thus, all examples are correctly classified by T and we deal with yes-instance for THRESHOLD ADJUSTMENT.
(=) Let T be solution of the THRESHOLD ADJUSTMENT instance, that is, to up to k (p
1)- 2x cuts of I' a threshold adjustment operation was applied such that the resulting tree T has
= 0 errors.
Outline: Observe that in T' the classification paths of all blue separation examples b(i, is identical to the classification paths of the red enforcing example. First, from that observation we conclude that in T one of the following two cases has to occur: (a) T contains a cut d5 < h for some such that S h + 1 or (b) T contains a cut d? > h for some h S Second, we show that if T contains a cut d, < for some E {1.5, 2,5, .P]. then T also needs to contain the cuts di < a for all x E (1.5, 2, 2.5..... ht. Analogously we show that, if T contains the cut di > h for some h E {1, 1,,, 2,, ................................ 1/2). then T' also needs to contain the cuts di > x for all x e {h, h + h 1.....,, 1/2]. Third, this structure of cuts in dē and de tightens the budget k and allows us to define a selected vertex of the color class i. Finally, we argue that all selected vertices form multicolored independent set.
Step 1: As discussed above, the classification paths of all blue separation examples b(i, xx) is identical to the classification paths of the red enforcing example e in T". Recall that e [ = x+11/2 = e e(d?" and that ex uses the default thresholds in each feature. Also observe that T" all cuts in feature di have the form d, < h for some h < 1 and all cuts in feature di have the form df > h for some h 2 p. Moreover, recall that e and e* are put into the right subtree of each cut in d5 and de errors,
in TV. Since T makes
conclude that I needs to have (a) cut d < h for some h such that æ & h + 1 or (b) a cut df > for some S æ, in order to put e into the left subtree of this cut and consequently separate from e*.
Step 2: Consider the set Z of cuts di in Z. We now argue (a) that T also needs to contain all cuts di < h for any 1.5 < h < 2 and (b) that the cuts of Z need to appear in T in ascending order with thresholds, that is, first cut de < 1.5, then
in T where h E {1.5, 2.5.,....... p). Let d, < < be a cut
cut d, < 2, and so on.
Assume towards contradiction that (a) is wrong, that is, T contains a cut ds x but not the cut dē < x - 1/2. Without loss of generality we assume that x is an integer. Now observe that each cut in feature df handles the following examples incidentally: (a) the red filler examples r 22 and (b) the blue filler examples 1 1// That means that each cut of 7 either puts all 4 of these examples into its left subtree into its right subtree. This is true since by our assumption T does not contain the cut d. < x - 1/2. Moreover, observe that since T contains the cut de < 2., at some cut df h for h 2 x all these 4 examples are put into the left subtree of the cut d, h. Now, observe that this left subtree consists of a single inner node with a cut in feature p. or q; Next, note that each cut in feature p. or 9, can only separate exactly one pair r bi* of filler examples, but not two. Thus, at least one filler example gets misclassified by T, a contradiction the fact that / = 0.
Thus, if contains the cut df < x for x 2 2, then T also needs to contain the cut d, < x - 1/2. Note that the above argumentation implies that the cut di < cut d, < x because otherwise still at least one filler example gets misclassified.
1/2 needs to appear before the
Analogously, one can show that if T' contains the cut d? > x for some x < < 1, then T also needs to contain the cut di > x + 1/2 and that in T cut de > + 1/2 needs appear before the cut d? > x.
Step 3: Let b(i, be the blue separation example such that T contains cut de < 1 and such that æ is maximal. Next, we distinguish the value of x. If x = p-- - 1, then since T contains the cut de p. by Step 2, T also needs to contain the cuts de < h where 1.5 < h < p. Observe that these are 2(p 1) cuts in total.
Otherwise, if x < p- 2 (this includes the case that does not exist), then by Step 2, T also needs to contain the cuts di < h where 1.5 < h S x + 1. Observe that these are 2x cuts in total.
39

---

di <
red
dg <
diu1-1
red
dil <
red
blue
Figure 6: The initial decision tree in the reduction of Theorem 5.3 from HITTING SET.
Since < 2, the blue separation example b(i, 1) exists. By Steps and 2, T contains (a) a cut d. < x + or (b) a cut di > æ. By our assumption, (a) is not possible and thus contains the cut d > I. Again, by Step 2, we can conclude that T also needs to contain the cuts di > h for each æ - p 1/2. Note that these are 2(p - 1 æ) cuts in total. Thus, in total T needs to perform least 2x + 2(p and d,".
2(p 1) threshold adjustment operations in features dã
Recall that the budget is k 2(p 1) 1)x. Since there are color classes and in each pair d5 and de of features T needs to perform at least 2(p 1) threshold adjustment operations, we conclude that to obtain T exactly 2(p 1) threshold adjustment operations per features d and d? are performed and that in no feature 4;" or 47" any threshold adjustment operations is done.
exists, we say that oft Vi is selected, and otherwise, x does not exist, we say that ia Vi is selected. Let S be the set of all selected vertices.
Step 4: We now argue that S is multicolored independent Clearly, S contains exactly vertex per color class. Hence, remains to verify that S is an independent set.
Observe that since T has no classification errors, it is sufficient to show that T cannot distinguish blue forcing example 6 and an red edge example e = (vf, vz)) if both endpoints of and vf are contained in S: Let e = e(wff be an edge example where of vi E S. Observe that according to Steps 1-3 all cuts of in feature de have the form d < for some h S x and all cuts in feature d/ have the from d? > h for some h 2 Hence, is put into the right subtree of each of these cuts. Analogously, we can argue that ends up in the right subtree of each cut in features d5 and dz. Since the blue forcing example b" uses the default thresholds in these 4 features, this is also true for b" Thus, both and d" end up in the cut d' < 2. Both examples, however, are put in the left subtree of this cut. Thus, T cannot distinguish the blue forcing example b* and the red edge example e = (v vz). Consequently, S is also an independent set.
Lower Bound. Recall that d 6 INDEPENDENT SET is W[1]-hard with respect to x 3. we obtain that CUT EXCHANGE is -hard with respect to d even if 8 = 20, and t 0. Furthermore, since MULTICOLORED INDEPENDENT SET cannot be solved in (K) (()) time unless the ETH fails [3, observe that CUT EXCHANGE cannot be solved in (d) [Z ( time if the ETH is true, where [Z] is the overall instance size, 8max = 20, and 0.
1, 6mx 20, and = 0. Since MULTICOL.ORED
C.3 Proof Theorem 5.3
Proof. We reduce from the W[2]-hard problem HITTING SET. Let (U,S, k) be an instance of HITTING SET with a universe U and family of S such that we look for hitting of size Essentially, we create a cut and a feature for each element of the universe and an example for each set of the instance.
Without loss of generality, assume that the elements of the universe are 1,2..... .,, U0) We create a THRESHOLD ADJUSTMENT instance with [U] features d2,dg- .g...... d/uj and for each set S in S create red example such that e(d.] Of S. and e[d] 1 otherwise. We also create one
40

---

blue example e' with e'[d]] = 1 for all i E U. Our initial decision tree has |U] cuts C1. 2...... Clu that form a chain where the right child of the cut is c++1 for all E {1, |6|| 11. The right child of cjjj is blue leaf. The left child of each cut a red leaf. The feature of the cut e, is d, and the initial threshold is O. An illustration of the initial decision tree is provided in Figure 6 Finally, let k and = 0.
We claim that this instance of THRESHOLD ADJUSTMENT has a solution and only if the HITTING SET instance has solution. First, assume that the HITTING SET instance has hitting set H. Then, adjusting the thresholds of cuts e; to for all i E H results in 0 misclassifications: For the blue example, all thresholds example e corresponding to some set S E S, there is some cut G with i E H whose threshold was adjusted to and the example thus goes red leaf since e[d,] by construction.
most 1 and so it still goes to the blue leaf. Similarly for any red
Assume now instead that the HITTING SET instance has no solution. Let us prove by contradiction that then the THRESHOLD ADJUSTMENT instance has no solution. Suppose the opposite, that is, there exists a solution by somehow adjusting some set of cuts C. First note that we cannot have increased any threshold above 1, since that would result in us misclassifying the only blue example the leaf is not relabeled, and otherwise some red example gets misclassified. Consequently, the blue example ends up in the only leaf that is originally labeled blue, and thus its label cannot be changed.
Consider now the set H = {i: e2 E C). It cannot be a hitting set, since our HITTING SET instance has no solution. Thus, there is some set S E S with S n H = 0. Take now the red example e corresponding to S. The only was we can classify
red is that the threshold of c; is greater than eld.]. This is not possible for any E S, since those cuts remain unadjusted by the fact that SnH = 0. and no threshold could have been increased above 1 without
For all & S, we have that e[d.] misclassifying the blue example. Thus, e has to get misclassified. By contradiction, the THRESHOLD ADJUSTMENT instance has no solution.
Note that the instance is not yet reasonable, since some leaves are initially empty. The following modification to the instance suffices for making the it reasonable here and for the following proposi- tions of the section. Let n' be the number of examples in the instance before making this adjustments. For each feature d, with i E [[U']. we create n' + red examples with e[d,] -o for j 2 and e|dy] = oc otherwise. We create also n' + 1 blue examples e with value oo for all features. Now, no leaf is empty, and each leaf has more than nt new examples, so their labels match the majority. The proof of W[2]-hardnesss even with these new examples goes identically to as above.
We have shown that the above reduction is correct. Note that k = K. D = 2 and t 0 for the constructed instance. Thus, THRESHOLD ADJUSTMENT W[2]-hard with respect to k even D 2 and t 0. It is known that HITTING SET cannot be solved in O(UU Eses (8)))(()) time assuming ETH, and not in O(U (<-)) time for any > 0 assuming SETH, see Corollary 14.23 and Theorem 14.42 by Cygan et al. 3 (note that DOMINATING SET straightforwardly reduces to HITTING SET). The ETH-baaedd lower bound for THRESHOLD ADJUSTMENT follows because
and the constructed instance of THRESHOLD ADJUSTMENT has size polynomial in [U] + (S). Further, since: |U| the SETH-basee lower bound for THRESHOLD ADJUSTMENT also follows.
In the following propositions of the section, we do not construct our reduced instances to be reasonable for conciseness. However, an adjustment identical to that of Theorem 5.3 suffices for making them reasonable up to and including Corollary 5.7
C.4 Proof of Corollary 5.4
Proof. The reduction is similar to Theorem 5.3 but we reduce from the NP-hard problem VERTEX COVER instead of HITTING SET. Take an arbitrary VERTEX COVER instance (G, k) such that we look for a vertex cover of size x. from the graph G (V,E), We then perform the same reduction as in Thm. 5.3, treating V as the universe and E' as the family of sets, each of which is of size two. O
C.5 Proof of Corollary 5.5
Proof. The reduction similar to Theorem 5.3 and Corollary 5.4 but we reduce from the W[1]-hard problem PARTIAL VERTEX COVER. Take arbitrary PARTIAL VERTEX COVER instance (G, r)
41

---

where we look for a subset of k vertices from the graph G = (V, E) such that at most edges are uncovered. We perform the reduction similarly to Theorem 5.3 treating V as the universe and E as the family of sets, each of which is of size two. The differences to that reduction are as follows: for all E U. This prevents us from increasing any threshold above 1 as we would get more than errors. On the other hand, we can now misclassify at most T = examples corresponding to the edges of G. The rest of the proof then goes analogously.
let = r and create t + blue examples e with e|d:]
C.6 Proof of Theorem 5.6
Proof. We again reduce from HITTING SET. This time, the idea is that each cut is initially in an undecided state (threshold 0) and has to be included (threshold 1) or not included (threshold -1) in the hitting set. Our initial decision tree is constructed the same way as in Theorem 5.3 However, our examples are different.
We add a single blue universe example e for each element u E U such that eld,,] -1 and otherwise e|d. = for all i E U with i + u. These examples are initially misclassified. For each set S in S, we create + 1 copies of a red example such that e(d,] = 0 if E S, and e|d,] otherwise. These are also initially misclassified. Finally, we create + 1 copies of a blue example e' with e' e'(d.) for all E U. These are initially correctly classified but get misclassified if any threshold is adjusted to be more than 1. Finally, set h = |U] and / t= K.
We again claim that this THRESHOLD ADJUSTMENT instance has solution if and only if the initial HITTING SET instance has a solution. The other direction goes almost identically to the proof of Theorem 5.3] if a suitable hitting set H exists, we increase the threshold of the cut e, to 1 for all E H and decrease the threshold to -1 for cuts G with i E U H. Consequently, we get [H] S errors.
Assume now instead that the HITTING SET instance does not have a solution and suppose that THRESHOLD ADJUSTMENT has a solution. We know that most K cuts can have threshold above 11 since otherwise more than / universe examples get misclassified. We can argue identically to Theorem 5.3 that if C is the set of cuts whose scores are above -1 and H = {i: a E C}, then there exists some set S E S that H does not hit and the corresponding example is misclassified. Since there are + 1 copies of that example, this would result in us exceeding the error budget. Thus, no solution to THRESHOLLD ADJUSTMENT exists.
Thus the reduction is correct. The ETH and SETH- lower bounds for THRESHOLD ADJUST- MENT follow in an analogous way to Theorem 5.3
C.7 Proof of Corollary 5.7
Proof. Direct adaptation of Theorem 3.6 reducing from VERTEX COVER analogously to Corol lary 3.4
D Additional Material for Section 6
Data sets and initial decision trees. We used 47 datasets from the Penn Machine Learning Benchmarks library [38] 32 of the datasets were used before for computing minimum-size trees [I
32 42 and since the number of examples was usually small we added further larger datasets. The
datasets range from 72 to 5404 examples (mean 655.09, median 302.00); for the full details, see Table 2 We transformed the data sets as follows (similarly to Janota and Morgado (I9):: First, we replaced each categorical feature by set of new binary features indicating whether an example is in the category. Second, we converted 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 remaining examples. Finally, if two examples of different classes had the same value in all features, we removed one of them arbitrarily.
We computed unpruned and pruned trees using the C4.5 heuristic for decision-tree computation (36 implemented WEKA 3.8.5 [9. The unpruned trees were obtained by running WEKA's J48 classi- fier with the flags -no-cv -B -M 0 -J -U. The pruned trees were computed by the replacement heuristic implemented in J48 when run with the flags -no-cv -B -M 0 -J -S. Overall, the tree
42

---

Table 2: Dataset statisties.
Dataset
Examples
Features
Class 0
Class
Class Ratio
analcatdata boxing2
132
3
61
71
1.16
appendicitis
106
7
85
21
0.25
australian
690
18
383
307
0.8
backache
180
55
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
147
245
1.67
cleve
302
27
164
138
0.84
cleveland
303
27
139
164
1.18
cleveland-nominal
130
17
61
69
1.13
colic
357
75
134
223
1.66
contraceptive
1358
21
764
594
0.78
corral
160
90
70
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
884
182
0.21
glass
204
9
128
76
0.59
glass2
162
9
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
25
150
120
0.8
hepatitis
155
39
123
32
0.26
Hill. dalley-withoutt noise
1212
100
600
612
1.02
hungarian
293
29
187
106
0.57
ionosphere
351
34
126
225
1.79
irish
500
5
278
222
0.8
lupus
86
3
34
0.65
lymphography
148
50
67
81
1.21
hatecullr.bbooogyypooooee
106
228
53
1.0
monk2
601
6
395
206
0.52
new-thyroid
215
5
150
2.31
phoneme
5404
5
3818
1586
0.42
pima
768
8
500
268
0.54
ciooperative-patient.oo
72
22
50
22
0.44
pmn synth
250
2
125
125
1.0
profb
672
9
448
224
0.5
schizo
340
140
200
1.43
soybean
622
133
545
77
0.14
tae
106
5
71
35
0.49
titanic
2099
8
1418
681
0.48
tokyol
959
44
346
613
1.77
yeast
1479
8
1050
429
0.41
size s ranges from to 607 (mean 71.23, median 29.00); number features ranges from to 88 (mean 1.35, median 8.00); the domain size D ranges from to 321 (mean 17.26, median 6.00); the number of classification errors ranges from 302 (mean 20.66, median 1.00). For the full details, see Table 3]
43

---

Table 3: Decision trees used in experiments: The first entry is for the unpruned tree T, the second for the tree computed by the replacement heuristic.
Dataset
Size
# Features used T
Domain used
Errors
analcatdata boxing2
48/9
3 3/3
11/5
0/
appendicitis
15 10
6/6
5/3
0/2
australian
90 / 46
13/11
29 /
0/22
backache
26 / 13
13/9
7 7/2
0/7
banana
607 / 186
2/2
321 107
1/249
biomed
21/3
6/3
6/1
0/
breast-cancer
95 /5131
25 25/21
8/6
2/31
bupa
111 /72
5/5
21/18
0/25
cars
22 15
7/7
7/5
0/3
cleve
57 29
15 13/13
12/5
0/15
cleveland
55/31
16/
10/6
0/13
cleveland-nominn
46/8
15/8
1/1
6/23
colic
51 28
27 18
6/4
0/
contraceptive
486 / 120
21/21
33/21
10/217
corral
13/13
5/5
1/1
0/0
dermatology
5/3
4/3
1/1
0/2
diabetes
137 96
8/8
24/16
0/24
ecoli
25 /5
5/3
11/2
0/
flare
93/15
8/7
5/4
125/ /
glass
26
7/7
717
0/1
glass2
22 16
6/5
615
0/4
haberman
92/21
3/3
30/9
2/38
hayes-roth
/4/12
11 10
1/1
0/1
heart-c
57 29
15
1215
0/
heart-h
57 /2
20 18
13/6
0/14
heart-statlog
54/
17
1317
0/15
hepatitis
18
10
3/2
0/3
Hill hallly-wwihhoe noise
250/228
88 / 85
63/47
0/11
hungarian
57 /2
19 19
13/6
0/
ionosphere
21/19
12/11
4/4
0/1
irish
2/2
1/1
2/2
0/0
lupus
/
2/2
20/2
0/13
lymphography
23/
18 11
1/1
0/5
molecular biology promoters
10
11 11
1/1
0/1
monk2
40/
6/6
1/1
0/0
new-thyroid
13
5/5
4/4
0/2
phoneme
504 341
5/5
159/99 999/9
0/98
pima
137 96
8/8
26/
0/24
postoperativve-atiin---aa
23 21
13/13
1/1
0/1
prnn_synth
39
2/2
24/5
0/23
profb
185 / 115
9/9
14/17
0/42
schizo
83 69
12/
15
0/8
soybean
13
12
1/1
0/8
tae
41 22
5/5
13
0/11
titanic
336 61
8/8
61/20
157
302
tokyol
46 34
24 22
10/5
0/6
yeast
315 125
8/7
43/
0/ 129
Further pruning pruned trees. The above indicates that misclassifications may not be strongly reducable by local search. We next wanted to know whether it is possible further prune the trees after local search, keeping the number of misclassifications at most the same. Indeed, in the solved problems, for 18 it was possible prune further after at most two adjustments and for 24 this was possible after two exchanges. The average nodes pruned were 1.40 and 1. 1.78, respectively. In one case, the tree size could be almost halved after one exchange. The full details for the improvable instances are shown in Table
Combining pruning with local search. Next, we wanted know whether we improve pruning perfomance over the heuristics. Thus, started with the unpruned heuristically computed trees,
44

---

Dataset: flare
hex kaa
180
hex Mad
hex laad
Min. # errors achievable
170
kex Mad
hex Mad
160
150
140
130
20
40
60
80
kre
Dataset: hayes-roth
kex 0, Aad =
kex 0, Aad
Rex 0, Aad =
Min. # errors achievable
20
kex 1, kad
kex 2, Kad =
15
10
5
0
0
8
10
12
14
Kre
Figure 7: Pareto fronts for number of achievable errors vs. number of pruning operations Aif for various local search parameters.
45

---

Table Number nodes for decision trees that can be pruned without increasing errors after local search, Dashes indicate timeouts.
Dataset
Tree Size
Initial Errors
kidd
kaad
kex
kex
banana
607
249
breast-cancer
95
31
2
bupa
111
25
cleve
57
15
2
2
2
cleveland
55
13
2
2
2
cleveland-noming
46
23
colic
51
15
0
0
contraceptive
486
217
corral
13
0
0
diabetes
137
24
2
ecoli
25
10
flare
93
159
glass
28
1
glass2
22
4
haberman
92
38
2
heart-c
57
15
1
heart-h
57
14
heart-statlog
54
15
hungarian
57
14
ionosphere
21
1
lymphography
23
5
O
pima
137
24
eestoerraivee-patinn--aaa
23
1
0
profb
185
42
soybean
28
8
0
tae
41
11
0
yeast
315
129
pruned them to the same size as the heuristically computed pruned trees while also allowing to two local search operations in the process. In the solved problems, this was the case for 10 trees with adjustments and 17 with exchanges, where the errors were improved by 5.16% and 8.92% on average, respectively. The full details are shown in Table 5] Since heuristic chooses only one possible tradeoff' between errors and number of pruned nodes, also looked at the full pareto fronts these goals, defined by zero local search operations, one or two. A plot of the pareto fronts for two representative instances is shown in Figure 7 The behaviour of error decreases for local search is relatively consistent over different tradcoffs but local search becomes much more effective for large numbers of pruned nodes, especially for cut exchange.
Summary. Overall, we have indication that our algorithms can feasibly used to gain new insights into the amenability of small real-world decision trees. It seems that the heuristics choose tradeoffs between pruning and errors that are only very weakly amenable to local search. (Note that such observations are only possible to make with algorithms that find the optimum values, designed here for the first time.) When pruning more nodes than the heuristics commonly choose, local search may be effective and important.
have
46

---

Table 5: Error numbers obtainable when combining pruning with local search. Dashes indicate
timeouts.
Dataset
Pruned Nodes
Heur. Errors
kad
kad
kex
kex
2
australian
44
22
22
21
breast-cancer
64
31
30
30
30
cleve
28
15
14
14
14
cleveland
24
13
12
12
12
eleveland-noming
38
23
23
23
22
22
colic
23
15
15
15
14
contraceptive
366
217
217
216
dermatology
2
2
2
2
2
ecoli
20
8
flare
78
159
157
157
157
156
haberman
71
38
37
37
37
37
heart-c
28
15
14
14
14
lymphography
5
profb
70
42
41
41
soybean
15
8
7
titanic
275
302
301
301
yeast
190
129
127
126
47


Reviews:
[{"review_id": "AFYFfZysOw", "reviewer": "Reviewer_9RB4", "summary": "This work studies the problem of doing a fixed number of heuristic local-search algorithms like adjusting the threshold of an existing cut or changing the feature of a cut after a tree has been already learned. First, this work shows that these are NP-complete in general and hence, provides a fixed parameter parameterized complexity. For instance, they show that the problems remain hard for a small number d of features or small domain size D but the combination of both yields fixed-parameter tractability.", "questions": "- If we exchange feature of a cut and that feature appears as a sub child of that node, do we leave it unchanged?\n- What about other local search operations like removing a leaf from the tree?\n- I am confused about line 71 where the authors say that the local algorithms are optimal but the error decrease is mild. Could the authors please clarify that?\n- From table 1, it seems that local search algorithms don’t help that much. Why are they so popular in practice if that is the case?\n- Could the authors comment on the algorithms runtime that they have provided in terms of what they can hope to further improve?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- I find it interesting that this local search operations on an already learned tree is such a common practice but no one has studied this from a fixed parameter tractability perspective. Hence, I feel this work bridges this gap.\n- The paper is overall well written but the diagrams like figure 1, 2 are confusing and difficult to understand.\n\nWeaknesses\n-  This work does not explore some dataset settings where their theoretical results could be more practical like when are each of the parameters for which the algorithms are tractable smaller and hence in practice, the results hold.\n- The authors have not discussed the technical hardness/novelty of their hardness results and what are the key challenges in obtaining the results.", "was_revised": true, "final_justification": "I would like to keep my score for this work. Although the experimental results are still limited, I feel that the paper has a novel theoretical contribution which would be useful for the community", "rebuttal": "Thank you for the review and the feedback! We respond to the Reviewer's concerns and questions separately below.\n\n**Figures 1 and 2**\n\n- We will try to make the figures clearer by adding explanations to the paper along the lines of what follows:\n\n- In Figure 1, the parameterized tractability of the problems increases as one traverses the Hasse diagram upwards. For example, both problems are W[1]-hard and in XP when parameterized by $s$, and consequently they are at least W[1]-hard (potentially paraNP-hard) for all parameters smaller than $s$ and have at least an XP-time algorithm (potentially FPT) for all parameters larger than $s$. The leftmost cell of each tells the complexity classes for threshold adjustment and the rightmost for cut exchange, which happen to be the same for all considered single parameters.\n\n- Figure 2 is admittedly very information-dense as it concisely summarizes all our results for parameter combinations. There, the result implied by the coloring of the box applies to all parameters bounded from below by a function of the parameter in the bottom cell and from above by a function of the parameter in the top cell. As a concrete example, the first box of the middle row states that Threshold Adjustment is W[1]-hard and in XP for, for example, $k$, $k + D$, $k + t$, and $k + D + t$.\n\n\n\n**Used data sets**\n\n- Our data sets are standard benchmarks used in many other papers on learning/optimizing decision trees (Bessiere et al., 2009; Narodytska et al., 2018; Romano et al., 2022; Staus et al., 2025).\n\n- The most practical algorithm and the one used in our experiments seems to be the one whose running time depends especially on the number of features $d$ and the maximum domain size $D$, which both range from a few to hundreds in the test instances and thus cover a variety of settings.\n\n**Technical hardness**\n\n- While some of our results are adaptations from previous work, we wish to emphasize that many others are relatively involved; consider, e.g., the proofs of Theorem 3.6 (Threshold Adjustment reduces to Cut Exchange) or Theorem 5.2 (W[1]-hardness for $d$), requiring meticulous analysis and designing novel gadgets. We will update the manuscript accordingly to highlight our technical contributions more.\n\n**Are features of descendants modified?**\n\n- No, both operations only apply to the chosen cut.\n\n**Other operations**\n\n- The parameterized complexity of removing leaves is well-understood (Harviainen et al., 2025), and we also include those operations in some of our results: see Theorem 4.3 and the experiments, in particular Appendix E. One can also simulate pruning operations by threshold adjustment (and thus also cut exchanges), since setting the threshold to an arbitrarily large/small value essentially removes one of the subtrees. To keep the scope of the paper focused, we did not consider other operations here, but those would provide an interesting future research direction. \n\n**Near-optimality locally**\n\n- On lines 67–72, we discuss that the surprisingly good performance of heuristics for learning and pruning. In particular, the constructed trees are near-optimal in the local neighborhood, which in this case is defined as the set of decision trees obtainable by performing $k$ threshold adjustments/cut exchange operations. On some instances, there are better trees in the local neighborhood of the tree obtained from heuristics, but the improvements are mild. For example, with the *breast-cancer* instance, performing one adjustment/exchange reduces the number of errors from 31 to 30. With 'mild' we mean that the error reduction is quite small.\n\n**Popularity of local search**\n\n- We suspect that the contrast between the limited improvement observed in our experiments and the popularity of local search is at least partially explained by the quality of the decision tree that is used initially. When local search or genetic algorithms are applied in practice, perhaps the initial decision tree tends to be mediocre and thus easy to improve at first, whereas better heuristics produce a near-optimal tree that is harder to improve.\n\n**Improving the running time**\n\n- Our proof-of-concept implementation is written in Python and loops over all the dynamic programming table entries, which can be inefficient in Python. In addition to implementing the algorithm in a faster language like C++, one could look for heuristic improvements like avoiding enumerating unnecessary table entries.\n\n- Even though the exponential time hypothesis (ETH) incurs some restrictions on the optimal asymptotical time complexities, there is also room for improving the exponents in the running times. More precisely, currently the exponent is $2d$, but the ETH only excludes an exponent of $o(d)$."}, {"review_id": "QqBYGqc1MA", "reviewer": "Reviewer_eGr1", "summary": "The paper provides a parameterized complexity analysis of local search post-processing for decision trees, specifically through cut exchange and threshold adjustment operations. Threshold adjustment allows the thresholds of internal decision tree nodes to be modified, whereas cut exchange additionally allows for node features to be exchanged.\n\nSpecific theoretical contributions include (1) an extension of previous W[1]-hardness result for decision tree construction under a binary feature domain, (2) introduction and formal connection of the cut exchange and threshold adjustment problems, (3) W[1], W[2], and NP hardness results for both problems across several cases, and (4) FPT and XP algorithms for both problems w.r.t various parameter combinations.\n\nBeyond these contributions, a small-scale empirical investigation was also conducted. Results show that local modifications (<2 operations) were not able to significantly improve heuristically constructed trees, suggesting that such algorithms may not be broadly applicable and that heuristically constructed trees are optimal within limited local domains. The latter may help to explain challenges faced by other decision tree construction mechanisms based on local search (e.g., Markov chain Monte Carlo).", "questions": "Q1 In what settings might the proposed local search algorithms (or variants) prove empirically useful?\n\nQ2 What broader connections could be made between this work and subfields such as general decision tree learning, greedy heuristics, post-processing, etc?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "The paper is clear and well-formatted though somewhat verbose in its notation.\n\nThe significant theoretical contributions of the paper appear novel, breaking ground on the complexity of local search in decision tree construction. The strengthened W[1]-hardness results for general decision tree construction in the binary domain may also be of independent interest.\n\nThis said, the conducted experiments suggest little applicability for the proposed local search problems (cut exchange and threshold adjustment) for which most of the parameterized complexity analysis was conducted. \n\nGiven this limitation and a lack of stated impactful future extensions, I would not recommend this paper to be accepted in its current form. This said, I could be convinced provided evidence of impactful future extensions or further examples of connections or implications for general decision tree learning.", "was_revised": true, "final_justification": "Thank you for the responses to myself and others. I am convinced that (1) the technical contributions made by this paper are more rigorous and significant than I previously expected and that (2) the hardness results for local optimization combined with the empirical results showing minimal potential upside of such optimization could have more far reaching implications to the field of decision tree learning. I have increased my score from 3 to 4 as a result.", "rebuttal": "Thank you for for your review and your feedback! \nWe also want to thank the reviewer for pointing out this curious similarity between the issues of local search and MCMC.\nWe respond to the Reviewer's concerns and questions separately below.\n\n**The conducted experiments suggest little applicability for the proposed local search problems**\n\n- We would like to mention that this conclusion was not possible before. Prior to our work there was no evidence whether the trees computed by these heuristics are locally optimal with respect to a small number of threshold adjustments and cut exchanges. Only thanks to our algorithmic study, we could develop efficient algorithms for this task. Moreover, only our implementations based on these algorithms allowed making this experiment. As shown by our complementing hardness results, this is quite surprising and in the future one should investigate this phenomenon further, that is, find explanations as to why the trees computed by these heuristics are often locally optimal for small values of k.\n\n- Also, in our experiments we showed that combining pruning and local search is better than doing this sequentially, that is, first prune the tree and then apply local search. This combined approach might be useful in setting where even a small improvement in the number of errors can be quite important, for example in healthcare.\nMoreover, threshold adjustment and cut exchange are used extensively in genetic algorithms (see references 18-21, 24-26, and 27 of our paper). Our algorithms could be quite helpful there to lead to much better rate of convergence. We did not test this hypothesis since it's beyond the scope of our paper. Moreover, the precise setting is not as clear as for the heuristics which we tested since many different genetic algorithms exist and its not clear which of them should be included in our experiments.\n\n\n**What broader connections could be made between this work and subfields such as general decision tree learning, greedy heuristics, post-processing, etc?**\n\n- We could imagine that the FPT-algorithm for parameter d+D which we used in our experiments can be extended to also cover other local search operations which modify the structure of the tree. We already showed (Theorem 4.3) that pruning and local search can be combinded in a single algorithm. As written above, our experimental results showed that this combined approach yields better results in terms of errors than applying both sequentially. This insight could help in developing new post-processing heuristics which lead to better results (same size but less errors) than the existing ones.\n\n- Also, since our new approach yields optimal solutions for local serach of decision trees, our algorithms could be used to develop new genetic algorithms with more powerful crossover operations.\nMoreover, currently minimal-size decision trees can only be computed for size up to s=20 (see citation 39 of our paper). A major hurdle to also solve instances where s>20 is the lack of good lower bounds to abort parts of the branch-and-bound approach early. Our local search algorithm could help in strengthening existing lower bounds and thus make the learning of minimal-size decision trees more applicable."}, {"review_id": "YNS8tL3wVd", "reviewer": "Reviewer_GnjU", "summary": "This paper studies optimizing decision trees by performing a fixed number of local-search operations. \nThey define two types of local-search operations:\n\n1. Adjusting the threshold of a cut\n2. Exchanging the feature of that cut (and setting a new threshold)\n\nThe authors show that these two subproblems are NP-complete in general.\nThey further investigate the parameterized complexity of these subproblems with respect to a bunch of parameters.\nThey also found that some combination of parameters can make the problems FPT.\n\nHowever, I found that the studied subproblems are not really \"local\", and its complexity is reluctantly linked to the hardness of learning a global tree.", "questions": "W1 and W2:\nThe authors define the two subproblems as minimizing the classification errors after $k$-step local-search operations.\nThe $k$ steps relate the subproblems to the well-known learning problem for a full decision tree.\nThis looks like a somewhat abusive use of local operations.\n\nAlthough $k$-step local search indeed exists in the literature, I believe it is not the most natural and popular one.\nThe first local-search operation of interest should be the 1-step operation.\nIt is also the most computationally feasible one.\n\nHow do we efficiently solve the 1-step subproblem? \nIs it hard?\nWhat is the effect of optimizing a tree by a sequence of 1-step operations?\nThe authors skip these questions and go directly to the $k$-step version.\nThis renders the study incomplete in my opinion.", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical analysis of the parameterized complexity of two local-search operations for learning decision trees.\n2. The analysis is comprehensive by involving a bunch of parameters.\n3. Giving dynamic programming algorithms for the two subproblems with respect to a combination of some parameters.\n\nWeaknesses:\n\n1. The definition of the two subproblems is not natural (See below).\n2. A most straightforward 1-step local-search operation is not discussed in the paper.\n3. FPT algorithms are mainly of theoretical interest, and are less relevant in practice.", "was_revised": true, "final_justification": "Thank you for the rebuttal.\nThank you for pointing me to the experiments where \"heuristically computed trees were 2-optimal or close to 2-optimal\".\nMy concern about the non-local search has been addressed. \nI suggest the authors motivate the k-step local search differently in the revised paper to avoid confusion.\n\nI also agree with other reviewers that the paper in its current form has a small impact on the applicability.\n\nI slightly improved my score.", "rebuttal": "Thank you for your feedack!\nBelow, we separately respond to your questions.\n\n\n**How do we efficiently solve the 1-step subproblem?**\n\n- The 1-step subproblem corresponds to the special case k=1. Consequently, according to Proposition 4.6, both Threshold Adustment and Cut Exchange can be solved in polynomial time.\nIn our experimental study we investigated whether heuristically computed decision trees can be improved in terms of the number of errors by k=1 or k=2 modifications. Our results show that this is usually not the case. Consequently, allowing for a sequence of 1-step operations does usually not improve a decision tree since usually even a single 1-step modification yields no improvement.\n\n\n**Although k-step local search indeed exists in the literature**\n\n- We completly agree that the 1-step operation is the most important one. As we have written in our response to the previous question, considering 1-step operations is usually not sufficient to improve a tree computed by a heuristic. Hence, it is necessary to consider larger neighborhoods and to develop efficient algorithms for this case which we did in our work.\nSimilar concepts of searching in a larger neighborhood are for example used in MCMC where the convergence of algorithms such as Metropolis–Hastings to the stationary distribution can be speed up by allowing more complex modifications to the current state of the Markov chain.\n\n\n\n\n\n\n\n**W1 and W2: The authors define the two subproblems as minimizing the classification errors after k-step local-search operations.**\n\n- Our operations are local in the sense of neighborhoods, not in the changes that are made in some local area of the tree. More precisely, consider a graph where each node is a decision tree and two vertices (decision trees) D_1 and D_2 are adjcant if tree D_2 can be produced by applying k threshold adjustments/cut exchanges to D_1. Now, the neighborhood of a vertex (decision tree) is the set of decision trees which can be produced with k local search operations. Increasing parameter k yields a larger neighborhood. Consequently, we think our neighborhood definition is quite natural.\n\n\n**FPT algorithms are mainly of theoretical interest, and are less relevant in practice.**\n\n- While the majority of works regarding FPT-algorithms only focus on theory, a lot of FPT-algorithms pave the way towards fast implementations, for example consider the problem of computing a minimal-size decision tree: First an FPT-algorithm with inpractical running time was presented (see reference 31 of our paper), which then triggered the development of another FPT-algorithm (see reference 23) which then was the foundation of the currently fasted implementation to compute minimal-size decision trees (see reference 39). \nAlso, some of our algorithms, for example the d+D are of practical interest since without this algorithm we could not discover that the trees computed by common heuristics are locally optimal."}, {"review_id": "v2Ud1Xwgdg", "reviewer": "Reviewer_btpa", "summary": "This paper investigates the problem of improving decision trees through parameterized local search, focusing on two canonical operations: adjusting the threshold of an internal node and swapping its feature with a new one. While both problems are shown to be NP-complete in general, the paper provides a detailed analysis of their parameterized complexity across a wide range of structural and data-dependent parameters. The authors identify several tractable parameter combinations, most notably proving that the problem becomes fixed-parameter tractable when the number of features and the maximum domain size are both small. Efficient algorithms are proposed for these cases, including a dynamic programming method and a combined approach that incorporates pruning. A proof-of-concept implementation is evaluated on 47 benchmark datasets, showing that standard greedy decision tree learners already yield models that are nearly optimal in their local neighborhoods, with only marginal gains observed through local search.", "questions": "1. Can you elaborate on the intuition behind why improving a tree locally can be harder than learning one from scratch in some parameter regimes?\n\n2. Given that local search leads to only minor improvements in most experiments, do you view this as a sign of strong heuristics or limitations of the local neighborhood?\n\n3. Would your framework extend to other local operations such as subtree swapping or merging? Are any such cases tractable?\n\n4. In practice, what ranges of d and D do you consider manageable for your exact algorithms to run efficiently?", "limitations": "yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n\n- Provides a rigorous, systematic parameterized complexity map for two decision-tree improvement problems.\n\n- Identifies non-trivial FPT results and proves W[1]/W[2]-hardness under other settings.\n\n- Offers new algorithmic contributions, including exact dynamic programs and pruning-aware extensions.\n\n- Connects and extends recent theoretical results in decision tree learning and pruning.\n\n- Clarity of exposition is high for a theory-heavy paper; good use of figures and algorithm pseudocode.\n\n**Weaknesses**:\n\n- Empirical improvements from local search are very limited (1–2 errors on most datasets).\n\n- Theoretical algorithms do not scale well; many instances time out for k=2.\n\n- Focused only on two types of local moves; omits more structural modifications, e.g., subtree switches.\n\n- Heavy reliance on parameterized complexity may limit accessibility to broader ML audiences.", "was_revised": true, "final_justification": "While I appreciate the clarifications and author engagement with the questions raised, several concerns remain either unaddressed or insufficiently acknowledged in the current framing of the paper. The empirical gains are minimal, and framing this as a strength seems overstated without clearer practical implications or guidance for future work. The restriction to only two local operations limits the generality of the results, and the omission of more structural moves weakens claims about the overall difficulty of local tree optimization. Scalability remains a concern, and the implementation, while a useful proof of concept, lacks clear potential for practical deployment. Lastly, accessibility remains limited due to dense parameterized complexity framing with little effort to connect to typical ML workflows. The contribution is solidly theoretical but should be more clearly positioned as such.", "rebuttal": "Thank you for your careful evaluation!\n\nBefore addressing your questions, allow us a comment:\n\nYou mention that the fact that empirical improvements from local\nsearch are very limited is a weakness. We consider this a strength:\nThis is an important finding that is impossible without algorithms\nthat are guaranteed to find the optimum in the local neighborhood and\nit informs future research and has direct implications for practice.\nI.e. it is likely not necessary and useful to locally optimize\ndecision trees computed by standard heuristics except in the regimes\noutlined in our paper. Our resources are more usefully spent\nelsewhere.\n\nAs to your questions:\n\n**1. intuition behind why improving a tree locally can be harder than\n   learning one from scratch:**\n\n- To clarify this, our reduction from learning to local search basically\nuses scaffolding to construct a useless decision tree which then has\nto be made useful via changing its cuts with local-search operations.\nIn the reduction the number of local-search operations roughly\ncorresponds to the size of the tree to be learned. Thus, on the one\nhand local-search in a k-step neighborhood is harder than learning a\nsize-k tree but on the other hand in practice the number of local\nsearch operations will be much lower than the tree size to be learned.\n\n- Note, however, that this intuition is not universally true, since for\ninstance for parameter s + t, Threshold Adjustment is fixed-parameter\ntractable whereas Decision Tree Learning is W[1]-hard for s even for t\n= 0 (see Ref. [31, Thm 2]).\n\n**2. local search leads to only minor improvements in most experiments,\n   do you view this as a sign of strong heuristics or limitations of\n   the local neighborhood?**\n\n- We think it is rather a strength of the considered heuristic: Since\nthese local-search operations are applied in the many cited sources,\nthere must be many situations where they do improve the trees\nconsidered there effectively. This can be for two reasons: The trees\nin these applications are worse to start with or their heuristics are\nable to search a subset of a much larger neighborhood which happens to\ncontain better trees. Both implicit questions would make an\ninteresting follow-up work.\n\n**3. other local operations such as subtree swapping or merging**\n\n- We think this is interesting but since this is the first study on this\ntopic, we had to focus our ressources on the seemingly most-used\noperations (and still, note the length and content of our paper).\nSubtree merging and swapping seem quite different in their structure\nand thus many of our techniques will likely not be directly\napplicable. Some ideas from the dynamic program for parameters d and D\nmight transfer over, however.\n\n**4. In practice, what ranges of d and D do you consider manageable?**\n\n- Note that we wouldn't consider our proof-of-concept implementation\npractical yet. There is huge potential for improvement, both on the\nimplementation side (since it is in Python) and algorithmic side (we\nthink there are many possible heuristic improvements to the code that\nmaintain optimality which we did not have time for). That said, the\ncurrent implementation usually completes within 1h if d_T + D_T <= 20\n(with outliers in both directions), where d_T is the largest number of\ndimensions on a root-leaf path in the input tree and D_T the largest\nnumber of thresholds on a root-leaf path. This implies it completes if\nd + D <= 20 but these can be even larger.\n\n**Further comments:**\n\n- **poor scalability:** We agree, but note that this is a proof of concept\n  that is supposed to show that the algorithm is implementable and\n  that it already yields results on standard benchmark data without\n  much engineering. Note that with efficiency improvements and larger\n  data we don't expect the running time to scale strongly with\n  increased k, as the theory shows. Still, our main contribution is\n  the theory.\n\n- **parameterized complexity may limit accessibility to broader ML\n  audiences:** Please note that this paper follows an ongoing vibrant\n  tradition of parameterized complexity analysis at top-level ML\n  venues, see References [7, 10, 12, 22, 23, 30, 31, 38] just for\n  decision trees and closely related problems."}]

Author rebuttal:

Meta-review: This paper studies the problem of improving decision trees through a fixed number of local-search operations, specifically threshold adjustment at internal nodes and feature exchange with new thresholds. The authors show that both problems are NP-complete in general, but provide a detailed parameterized complexity analysis that identifies tractable cases, such as when both the number of features and feature domain size are small, yielding fixed-parameter tractability (FPT). They extend existing hardness results, formally connect the two problems, and present FPT and XP algorithms under various parameter combinations. Empirical results on benchmark datasets indicate that standard greedy decision tree learners are already near-optimal in their local neighborhoods, with local modifications yielding only marginal improvements, offering insight into the challenges faced by local search–based decision tree construction methods.

In general the main positive aspects about the paper is that it addresses an interesting question and also makes theoretical contributions.

On the negative side, we find that the usefulness is rather limited. Partially, a significant computational effort need to be made to obtain marginal improvements. The utility/cost ratio seems to be a bit poor.

Looking at the discussion, the group of reviewers is a bit divided, but I find that the arguments of the reviewers who recommend rejection are a bit subjective and not sufficiently strong to prevent the work from being presented. Therefore, I will recommend acceptance as a poster.

This being said, I find the authors' statement that "marginal improvement is a strength of this paper" quite disturbing. If this is what you are after, this should maybe be the main message and focus of the paper.
Decision: Accept (poster)