Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
Authors: Christian Komusiewicz
Andre Schidler
Frank Sommer
Manuel Sorge
Luca Pascal Staus
Venue: ICML 2025 poster (2025)
Keywords: parameterized complexity
NP-hard problem
binary decision diagrams
classification
combinatorial optimization
Primary area: theory->optimization
TL;DR: We present improved algorithms and running time lower bounds for minimizing Binary Decision Diagrams (BDDs) under certain conditions (e.g. small domain and solution size), and show practical applicability through a proof-of-concept implementation.

Abstract: Binary decision diagrams (BDDs) are widely applied tools to compactly represent labeled data as directed acyclic graphs; for efficiency and interpretability reasons small BDDs are preferred.
Given labeled data, minimizing BDDs is NP-complete and thus recent research focused on the influence of parameters such as the solution size $s$ on the complexity [Ordyniak et al., AAAI 2024].
Our main positive result is an algorithm that is efficient if in particular $s$, the domain size $D$, and the Hamming distance between any two data points is small, improving on previous running-time bounds.
This algorithm is inspired by the witness-tree paradigm that was recently successful for computing decision trees [Komusiewicz et al., ICML 2023], whose extension to BDDs was open.
We extend our algorithmic results to the case where we allow a small number of misclassified data points and complement them with lower bounds that show that the running times are tight from multiple points of view.
We show that our main algorithm holds practical promise by providing a proof-of-concept implementation.

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
Christian Komusiewicz André Schidler 23 Frank Sommer 22 Manuel Sorge"
Luca Pascal Staus
Abstract
Castro et al., 2019), knowledge compilation (Abío al., 2012; Lai et al., 2013; Serra, 2020) and constraint propaga- tion (Andersen et al., 2007; Perez & Régin, 2015; Verhaeghe et al., 2018; Latour et al., 2019). In the context of classifica- tion, a BDD is rooted directed acyclic graph in which each internal node represents a separating hyperplane and each terminal node is uniquely associated with a class, For rea- sons of efficiency of working with BDDs and interpretability, it is erucial that the size of the BDDs is small; throughout the paper by size we mean the number of inner nodes.
Binary decision diagrams (BDDs) are widely ap- plied tools compactly represent labeled data directed acyclic graphs; for efficiency and in- terpretability reasons small BDDs are preferred. Given labeled data, minimizing BDDs is NP- complete and thus recent research focused on the influence parameters such as the solution size s on the complexity [Ordyniak et al., AAAI 2024). Our main positive result is an algorithm that is efficient if in particular s, the domain size D, and the Hamming distance between any two data points is small, improving on previous running- time bounds. This algorithm is inspired by the witness-tres tree paradigm that was recently success- ful for computing decision trees [Komusiewiez et al., ICML 2023], whose extension to BDDs was open. We extend our algorithmic results the where we allow small number of mis- classified data points and complement them with lower bounds that show that the running times are tight from multiple points of view. We show that our main algorithm holds practical promise by providing a proof-of-concept implementation.
Compared to decision trees, another widely-studine concept with particular relevance to explainable AI, BDDs can offer smaller sizes and less redundancy (Oliver, 1993; Oliveira Sangiovanni- Vincentelli, 1996; Shotton al., 2013; Ignatov & Ignatov, 2017). Optimizing in particular the size of decision trees has received immense attention from the point of view of implementations (see the surveys by Carrizosa et al. (2021); Costa & Pedreira (2023)) and algorithms and complexity (Ordyniak & Szeider, 2021; Eiben et al., 2023; Komusiewicz et al., 2023; Ordyniak et al., 2024; Gahlawat & Zehavi, 2024; Schidler Szeider, 2024; Harviainen et al., 2025; Kobourov al., 2025). Computing minimum-size BDDs is comparatively less studied (Hu et al., 2022; Florio et al., 2023; Cabodi et al., 2024; Ordyniak et al., 2024). While both are NP-hard (Hyafil & Rivest, 1976; Bollig & Wegener, 1996), one reason for this difference may be that the search space of possible solutions is much larger than for decision trees (Florio al., 2023); the topology needs to be optimized jointly with choosing the correct separating hyperplanes. Therefore it is even more important to find ways shrink and efficiently traverse the search space. In this work we contribute to that research direction.
1. Introduction
Binary decision diagrams (BDDs), also known as decision graphs and decision streams, are fundamental data structures used to describe (Lee, 1959; Akers, 1978; Bryant, 1992) and classify data (Oliver, 1993; Oliveira & Sangiovanni- Vincentelli, 1996; Mues et al., 2004; Shotton et al., 2013; Ignatov& & Ignatov, 2017; Florio al., 2023). BDDs have wide variety of applications, ranging from circuit veri- fication (Lee, 1959; Akers, 1978; Bryant, 1992) and opti- mization (see the survey by Castro et al. (2022)) to artificial intelligence topics such as planning (Sanner et al., 2010;
An algorithmic paradigm that was successful in the context of decision trees is that of witnesses (Komusiewicz et al., 2023): In this paradigm one builds the tree incrementally, identifying each time an incorrectly classified, dirty, example, which necessitates new separating hyperplane that classifies the example correctly. Then one uses the dirty example as a witness that this separating hyperplane is necessary, mandating that the example is classified the corresponding subtree. This reduces the search space and led to a new state of the art in computing minimum-size perfect decision trees, that is, decision trees with zero misclassifications (Staus et al., 2025).
'Equal contribution 'Institute of Computer Science University of Jena, Germany "Institute of Logic and Computation, TU Wien, Austria *Computer Architecture, University of Freiburg, Germany. Correspondence to: Luca Pascal Staus <luca. staus @ wii-innnadde>>
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
It was previously open if and how the witness paradigm could be applied to computing minimum-size BDDs (Or- dyniak et al., 2024). Indeed, only impractical enumerative approaches were known with large rumning- time guarantees. In this paper, we show that the witness paradigm is directly applicable to computing BDDs, that it yields practically relevant algorithms with much improved running-time guar- antees, and we give a proof-of-concep implementation that can already compute minimum-size BDDs of sizes up to 7.
pagliazzo & Paturi, 2001; Impagliazzo et al., 2001).
Relevant parameters for this analysis are the size of the de- sired (O)BDD, the number d of features, the largest domain size D of feature, and the largest number 8 in which two examples in E differ?. To our knowledge, the only work performing such an analysis is Ordyniak et al. (2024) who obtained an FPT algorithm for BSBDD and its ensemble version with respect to 8, D, and s.
Results. Our main result is an algorithm that applies the witness paradigm to BDDs in nontrivial way: We show that a BDD can be built incrementally, by successively iden- tifying an incorrectly classified, dirty, example e E E, and finding separating hyperplane that changes its current, in- correct classification path in the BDD. By doing that, we learn the new information that in all solutions the example e needs to reach this separating hyperplane in its classification path. We can thus label new edge in the BDD with e as witness and mandate that e has to traverse this edge. This reduces the search space tremendously. The result is an algorithm for BSBDD with running time (((6s" " sn) (Theorem 3.3), where n = |E], improving on the previ- ously best-known ((35)) .n (1)) (Ordyniak et al., 2024). Morcover, it avoids inherently enumerative approaches and instead is a search-tree algorithm with large potential for heuristic optimizations such as early termination rules. Our algorithmic approach is very versatile: We show that it can be extended to classification with errors (ERROR BSBDD), to computing OBDDs, and to computing minimum size en- sembles of BDDs. Indeed, it shows that BDDs are strongly extendable, a desirable algorithmic property of data struc- tures that represent data, which was previously open (Or- dyniak et al., 2024). Apart from other algorithmic results, we provide several tightness results based on the ETH that show, for instance, that the dependency of the exponent on is optimal, and that dependency on other parameters of the exponential part of the running time cannot be removed. Proofs marked with (+) are deferred to the appendix.
Problem statements. In the learning problem for BDDs, we are given a set E' S Rd of training data, labeled with classes by a labeling function A. We may first aim to find the minimum-size BDD that perfectly classifies the training data, that is, there are no classification errors. This can be formulated as search problem as follows:
BOUNDED-SIZE BDD (BSBDD)
Instance: A data set (E, A) and an integer s E I. Task: Find a BDD of size at most s that (per- fectly) classifies (E, A).
We call the corresponding size-minimization problem MINIMUM-SIZE BDD (MSBDD). Note that algorithms solving BSBDD can solve MSBDD with an additional factor of s in the running time by successively increasing 8 = 1, 2, and solving BSBDD until a solution is found.
The requirement of perfect classification is often too strong for practice and thus we also study the generalization ER- ROR BSBDD of BSBDD in which we additionally given an integer I. and we ask to find BDD of size at most s that classifies all examples in E' correctly except for at most t misclassifications.
Finally, researchers often study ordered BDDs (OB- DDs) (Akers, 1978; Hu al., 2022: Cabodi et al., 2024). An OBDD is associated with an order over the possible separat- ing hyperplanes and each root-terminal path in the desired BDD has to respect this order. In the corresponding problem variants we replace BDD with OBDD in the problem name and ask for an OBDD instead.'
To demonstrate the practical potential, we provide an imple- mentation of our main algorithmic result. We compare to state-of-th of-the-art SaT-based approach (Cabodi et al., 2024) on standard benchmark data. Despite its proof-of-concept status, our implementation computes optimal BDDs of size up to seven, is faster than the SAT-based approach for BDD sizes up to four, and in general solves 79% of the instances that also the SAT-appoocch solves within a 1h time limit.
Methods. All of the above problem variants are NP-hard and thus cannot expect efficient algorithms in general. Thus, we apply an approach based on parameterized algo- rithms (Gottlob et al., 2002; Flum & Grohe, 2006; Nieder- meier, 2006; Cygan et al.. 2015; Downey& & Fellows, 2013): We try to identify small parameters of the input or desired output and fisignfixeddpee srred-parameter (FPT) algorithms with running time / [p)) try to prove that such algorithms are not possible, based on reasonable, widely accepted tomplexity-theoreic assump- tions such as the Exponential Time Hypothesis (ETH) (Im-
where / is the input size. Or we
2. Preliminaries
For E N, we denote [n] == 2 nn. tor E Rd, we denote by x the ith entry in æ. Let Σ
For vec-
"See Ordyniak & Szeider (2021, Table 1) and Staus et al. (2025, Table 3) for indication that this parameter small in practical data.
Note that do not assume that an ordering is given. The ordering has to be computed alongside the OBDD.
2

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
be set of class symbols. A data set with classes E is a tuple (F,, A) of set of examples F _ RR and their class labeling X: E + Σ. Note that this definition captures data sets with ordered features because such features can be mapped into R. We assume that (F,, A) does not contain two examples with identical coordinates but different class labels. For a fixed data set (E, A), we let n := [ denote the number of examples and d the dimension of the data set.
to one of the leafs such that as with start vertex s goes to the left if and only if e is on the left side of cut(s:) for all i E [e]. In other words, at each split vertex we decide if an example goes to the left or right child based on whether the example is on the left or right side of cut(s). For each vertex v E (B) we define EiB, v] as the set of all examples e E E where v appears on (n(e). Similarly, for all ares a E A(B) we define E|B, a] as the set of all examples 6 E E where appears on (e))). We say that these examples are assigned to e and respectively. If B is clear from the context, we just write Elv]. By definition, each example e E E' is assigned to exactly one leaf i of B. We say that E is the leaf of e in B and denote E by leaf( (e)) or just leaf(() if B is clear.
For each dimension E [d], we let Thr(i) be smallest set of thresholds such that for each pair of examples e1, 62 E E with ei < e2 [i], there is a threshold h E Thr(i)) with [ < h < e2 f2 Note that such a set Thr( can be computed in (n log time and that [Thr(()] S D. A cut a pair (i. h) where E [d] is a dimension and h E Thr(i) a threshold in dimension d. CE) is the set of all cuts. The left side of cut with respect to E' C E is E (i, h)] = {e E E' eli] < h). and the right side of a cut with respect to E' is E (i. = {e E E' : e(i] > h}.
We call B reduced if each are has at least one example as- signed to it. Clearly, any BDD can be turned into reduced BDD without changing the leaf of any example by remov- ing any vertex or are a with Elu] = 0 or E[a] = 0 and contracting any are with an out-degree one start vertex.
To define BDDs we use special directed acyclic graphs (DAGs). These DAGs G have one root denoted by root(G)
An example e E E is dirty in B if we have X(e) * cla(leaf(e)) The set of all dirty examples in B is Dir A BDD classifies (E, X) if no example is dirty. In this case we call B perfect.
from which all other vertices are reachable. We write (G) to denote the set of vertices of G and A(G) to denote the
set of ares of G. The arcs in these DAGs are tuples (s, h, c) where is the start vertex, h is the end vertex, and e is either& E or and indicates whether the are goes to the left child or the right child of 8. We say that 8 is an in-neighhor of h and h is an out out-neighbor of s. If only one are with start vertex s and end vertex h exists or if the direction is irrelevant, then we just write (s, h). We define the in-degree of vertex h the number of arcs where h is the end vertex and similarly we define the out-degree of a vertex s as the number of ares where s is the start vertex. Additionally, each vertex is only allowed to have at most one left child and one right child, meaning the maximum out-degree is 2. A path in a DAG G is a sequence of ares (a),.... a&) such that the end vertex of a; is the start vertex of 0++1 for all e [k- 1].
3.
There is a naive brute force algorithm that solves BSBDD in polynomial time when & is constant. Theorem 3.1 (*). BOUNDED- BDD can be solved in time (5a .....d.. D) 12)011))
3.1. An efficient Algorithm to solve BSBDD
Next, we present much faster algorithm for BSBDD than Theorem 3.1 where we replace the number d of dimensions with the much smaller parameter 8. Our algorithm WiDBDD is a branch-and-bouud algorithm that starts with a BDD of size zero and then branches into all possible refinements of this BDD that increase its size by one. This repeated recursively until the maximum size is reached. To limit the number of refinements that have to be considered, Wi BDD annotates the ares of the BDD with examples called wit- nesses. WitBDD must then ensure that if an are is annotated with a witness, that witness must also be assigned to that arc. However, for this to work we first introduce a modified definition of BDDs called witness BDDs.
We write Pa) to denote the set of all paths in G.
A binary decision diagram (BDD) is special DAG B as described above and each vertex in V(B) is either a split vertex with out-degree 2 or a leaf with out-degree zero Let ((B) be the set of all split vertices and L(B) the set of all leafs. Furthermore, cut, S(B) -> Cuts F)) maps every split vertex to cut and cla L(B) + Σ labels each leaf with class. We drop the subscript if B is clear. We assume that cla is injective meaning there can only be at most one leaf for each class in Σ. The size of B, denoted as size B)= = [S(B). is the number of split vertices. Note that a BDD is not allowed to have two arcs with the same start and end vertex. Part a) of Figure shows an example BDD with three split vertices $ 82, 83 and two leafs.
A witness BDD (WBDD) is DAG W as described in the previous section. Additionally, the root of W must have in-degree zero and out-degree one. Each vertex in V(W) that is not the root is either split vertex with in-degree one and out-degree 2, a merge vertex with in-degree 2 and out- degree one or leaf with in-degree one and out-degree zero. Let S(W) be the set of all split vertices, M (W) the set of
For each example e we define its classification path cp(e)= ae) in B as the unique path from the root of B
3

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
a) b)
a)
d)
O-Insertion
L
Leaf-Insertio
Inssertionn
18
82
82
82
m71
7111
95
83
7111
11/2
171/2
Figure 2. A sequence of see-ste--rfinments leading from size- zero witness BDD to the witness BDD in part b) of Figure 1. The ares that get refined are drawn in orange and the resulting new ares are dashed. First, a d--Inserion creates the new split vertex 81 and merge vertex mi. Then, a Leaf- casf-nnsetionn adds the new split vertex 82 and new blue leaf. Finally, an H- H-Insertion adds another new split vertex s3 and a new merge vertex 1122.
Figure 1. Part a) shows BDD B and part b) shows equivalent WBDD W. We turn B into W by adding a new root vertex r and the two merge vertices my and m2. To revert this transformation we contract the outgoing arcs of the three newly added vertices.
all merge vertices and L(W) the set of all leafs. Further- more, cutw : S(W - CE') maps every split vertex to a cut, claw: L(W + Σ labels each leaf with a class and witw A(W) + 2 {0) assigns non-empty set of examples called witnesses to each are. We drop the subscript if W is clear. We assume that cla is injective, meaning there can only be at most one leaf for each class in E. The size of W, denoted as (W), is the number of split vertices. Since we know the in- and out-degree of every vertex we obtain the equation
There are three types of one-step-refinements which are demonstrated in Figure 2. For all three types, we first sub- divide the are an add new split vertex with cut(s) (i, h). The endpoint q of the are a1 becomes the left child of 8 if e E Els (i, h)]. and q becomes the right child other- wise, Which vertex becomes the second child of depends on the type of the mme-step-refnemmen
The first type is called a leaf-insertion. A one-step- refinement is leaf-insertion if there is no leaf l with cla(f) X(e) and ag L. For such refinement we add a new leaf with this class and make it the second child s.
Siz) [S(W) = [M(W) + [L(W) - (1)
which shows that the total vertex count is 2 Siz + 2. Note that WBDD is explicitly allowed to have two ares with the same start and end vertex as long as one goes to the left and one goes to the right. We need this property only during branching in WitBDD; the result will not have such ares. Part b) of Figure 1 shows an example WBDD with three split vertices 81, 82, 83, two merge vertices mi, m2, the root vertex and two leafs. All remaining definitions from the previous section are the same for WBDDs. We call a WBDD W consistent if for all examples E E the set of ares {a E A(W): e E wit(a)} forms a path that is a prefix of the classification path ew of e W. In particular, this means we have wit(a) (a S E a] for all a E A(W).
The second type is called an H-insertion. A one-step- refinement is an H-insertion if it is not a leaf-insertion and 01 # 02- For such a refinement we subdivide the arc dg add new merge vertex m which becomes the second child of
The third type is called a --insertion. A one-stee-reinnemeett is ---insrrion if a1 02. Recall that we first subdivide are aj to create a new split vertex 8 and second, we subdi- vide the new are (s, q) to add a new merge vertex m which becomes the second child of s.
When a one-step-refinemett subdivides an a it creates two new ares a' and a". We set wit(a') wit(a") = wit(a). For the arc a, from s to the second child of s we set wit(a,) = {e}. Additionally, we add e to the wit set of all ares on the classification path of e up to and including the are from the start vertex of a to s.
In the appendix we show that perfect reduced BDD of size exists if and only if perfect consistent WBDD of size exists. For an example see Figure 1. Thus, we only need to consider consistent WBDDs in Wit.DD.
We now define rreestep--efineeeett for consistent WBDDs. Given a consistent WBDD W, a one-step-refinenee mod- ifies W by adding a new split vertex and either new leaf define one-step- refinement as a tuple (a1, a2, h. e) where and a2 are ares in W. (i, h) E CU) is cut and e e Dirty(W) is a dirty example that is assigned to o₁ In particular this means
Figure 2 shows how applying these three types of one-step- refinements to WBDD may look.
or new merge vertex. Formally,
We write W I R to denote that the WBDD R was created by applying the mne-step-refimement to W. Note that some one-step-refinemenn may create an inconsistent WBDD or a graph which is not even a DAG: This can happen with a one- step-refinement (a1, 022 i, h, e) if the examples in wit(a:)
that aj has to be on the classification path of e. Additionally, ag allowed to be _.

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
Algorithm 1: WitBDD
the WBDD is bounded by 8. That means that Ref oefing is called O (R*)) times where R is the maximum number of iterations of the loop in Line 5. Since the loop is not called if W already has size s we can assume that we have si)) < 8.
Input: A consistent WBDD W, data set (E, A), and a maximum size & E IN.
Output: A perfect consistent WBDD of size at most 8 or 1 if none could be found.
For a one-step-refinmeen in R) we first need to choose an arc d1- This are must be on the classification path of e. This path can visit each non-leaf vertex at most once and contains exactly one leaf. Due Equation
Function Refine (W, (E, A), 8)
WWW classifies (E, X) then return W W has size s then return e some dirty example from (W)) forall (a1, 02, t,,,c) E Re(W, e) do
(1) we know that there are at most 2 (W)) + 2 < 28 vertices in W. Hence, the number of arcs on the classification path of e is also at most 2s. For 02 we can choose any are in A(W) To bound this, we can add up the out-degrees of all vertices. This gives us 2 |S(W)) [MW)) + 1. Since we have at least one leaf and size(W') s we get the following inequality:
Apply r to W to create a new consistent WBDD R
R' < Refine (R, (E,
R' + 1 then return R'
return T
2 [-IS(W)+ + [M(W)) +1 3 (W) + +15 3s.
and the example e are not on different sides of the cut hi), if the new are from a to d2 creates a cycle, or a₂ = 1 but a leaf with the class of already exists. No such refinement will lead to a perfect BDD. Thus, we write Ref(W) to denote the set of all valid one-step-refinements, that is, all one-step-refinements where It is still a consistent WBDD. We write (e,(W, e) to denote the subset of valid one-step- refinements where e is the dirty example.
Hence, there nesses of and e must be on different sides of the cut (i, h) we have at most d choices for the dimension i and at most D choices for the threshold h.
most 3s choices for 0g- Since the wit-
This bounds the total number of one-step-refinemmens that are considered in Line 5 by 6s28D. Applying a one-step- refinement can be done in (sn) time and checking if all examples are classified correctly and if not finding dirty example can also be done in (sm) time.
We can now describe the branching algorithm WitBDD. Initially we choose any example e E and construct consistent WBDD W with exactly one are between the
root and a leaf L. We set wit((r, ())= = {e} and cla(e)= = X(e). We then call Re Refine inn in Algorithm 1. Refinee takes a consistent WBDD W as input and checks if a sequence of
To prove Lemma 3.2 we first need to define embeddings. An embedding maps each are in WBDD W to a path in a different WBDD W' subject to certain conditions.
une-step-rfinnmment exists that can turn W into a perfect consistent WBDD with size at most s. For this, we first check if Win is already perfect. If not, we then check if W has already reached the maximum size. If that is also not the case we choose some dirty example in Line 4. We then iterate over all possible valid creestep-refinemenne the dirty example in Line 5, apply them to W in Line 6 and recursively call Refine in Line 7. If a perfect consistent WBDD found that has size most s we immediately return it. Otherwise the loop runs until all possible one-step- refinements have been checked.
Definition 3.4. Given two consistent WBDDs W and W we say that W admits an embedding & : A(W) + Path(W") into W" if the following conditions hold:
S(W) S S(W") and M(W) S. M(W") and L(W) S L(W") and (oot(W)= root(W").
with e as
2. For all s E S(W) we have cutw (s) = cutw (s) and for all E L(W) we have claw (f) claw.
3. For all a E A(W) we have:
(a) p(()) is a path from the start vertex of a to the end vertex of a and they are the only vertices from V(W) that appear on v(aa).
Lemma 3.2. For given data set (E, A) and positive inte- ger 8, Wi BBD correctly solves BSBDD.
(b) For all ares a' on sf(a) we have witw (a) S
Before we prove Lemma 3.2. we will first show that the algorithm has the desired running time.
wit
(c) If s1 E S(W), then a goes to the left in W if and only if the first are yf(a) goes to the left in W'.
Theorem 3.3. BSBDD can be solved in (((6s2D)) sn) time.
4. For all 01, 42 E A(W) with a + az, the only vertices appearing on both ( and ((az) may be their start and end vertices.
Proof. We first bound how many times Refine is called. Clearly, the recursion depth is at most s since the size of
5

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
The idea of the proof is first show that the starting WBDD of the algorithm admits embedding into some perfect WBDD P of size at most if such a WBDD exists. We then show that for any WBDD W that admits an embedding into P and that has at least one dirty example e there exists a one-step-refinemee that the algorithm considers that creates a WBDD that also admits an embedding into P. We then finish the proof by showing that if (W) size(P), then W must be perfect because P is perfect.
definition of 21, the are on cp(e) with start vertex 21 must go to the right which is contradiction to being on the left side of cutw (s1) = cutp(si). Hence, we have 21 a $1
With this we now know that &1 & V(W). We now set (i. h) = c1)) Without loss of generality, we as- sume that e is on the right side of (i, h).. Due to Item 3b in Definition 3.4 and the definition of 21 we know that all witnesses in wit(a1) must be on the left side of (i, h) while is on the right side. This ensures that the one-step- refinement creates a consistent WBDD and is therefore contained in Ref(We,)
Proof of Lemma 3.2. We assume that a perfect WBDD P of size most 8 exists. If not then the algorithm will clearly return 1 since any WBDD generated by the algorithm has size at most s. We assume that the witness labeling of P is maximal, that is, (a) = E(P, a] for all a E A(P).
We now just need to find a suitable are dg. To do this we will first try to find the vertex 22 which is created when the subdivides 02. This vertex must come after ž on the classification path of e in P. Let Q be the suffix of cp(e) that starts at the vertex following 21. Also, let Vi be the image of y, i.e. Vo = (sa(a) E A(W)). We now define 22 as the first vertex on Q that also appears on some path π E V.
We start by showing that the WBDD W of size zero that Re f i ine is initially called with admits an embedding into P. We know that W only has root r and one Icaf t. The root of WBDD is always the same and since P is perfect, there must be a leaf in P that has the same class as l. Hence, Items and 2 of Definition 3.4 are fulfilled. We now just need to map the are (r, E) of W to a path from r to é in P such that Items 3a to 3c and 4 are fulfilled. Let e be the witness in witw (r, f). Since P is perfect, we know that the classification path of e in P' must start in and end in f. Thus, by mapping (r, f) to this path we fulfill all conditions.
We now differentiate between two cases based on whether such a 2g exists or not. We first assume that it does not exist. In this case there cannot be leaf in W that has the same class as e. If this leaf & did exist it would have an in- neighbor e' in W. The path (((", E) would then intersect Q which contradicts z2 not existing. In this case we set 022 = 1 and the one-step-refinet
becomes a leaf-insertion.
Next, we assume that we already have some WBDD W that admits an embedding &p into P. We want to show that if Refine is called with W, then at least one of the WBDDs R that are created inside the for-loop must also admit an embedding into P. Let e be a dirty example in W. If such an example does not exist then W is already per- feet and
We now look at the other case where 22 does exist. Let 02 be the are in W with (fa2) = n. Also let $2 be the start vertex and h2 the end vertex of a2 We need to show that 22 is merge vertex in Z and that 22 does not exist in W.
Let 0g be the are in W with (((2) = IT Also let s2 be the start vertex and h2 the end vertex of 02 We first want to show that 22 must be a merge vertex. To do this we assume towards a contradiction that 2/ only has one incoming are. We now want to find an are 01 in W such that 22 is not the start vertex of a' but still appears we can just use a' == a2. If 22 82 then we set a' to the incoming are of 22 in W. Now, if 22 is not the start vertex of Q then the parent of 22 in P must appear on both so(a") and Q. This is a contradiction since 22 should by definition be the first such vertex. If 22 is the start vertex of Q then 21 must appear on the path p<aa) in P. Due to condition Item 4 in Definition 3.4, we must have 01 = a'. We know that 22 appears on cp(e) right after ø1. We also know that s0(11) diverges from that path at but still has 22 hı as its end vertex. That is only possible if 22 has two incoming ares which contradicts it having only one. This proves that 22 must be merge vertex.
done. We now need to find one-step- refinement r = (a1, i,,i, e) E Ref(WW,) e) with W 4 R such that R admits an embedding T into P.
We start by identifying d1 and the vertex 21 which is created when the one-step-refimement subdivides a1. Let a be the first are on the classification path ew ew(e) of e in W such that sa(a) is not fully included in cp(e) and let 21 be the start vertex of the first are in sp(a1) where the two paths do not match. For this to happen there must be exactly two ares in P with 21 as the start vertex which means that æ1 is a split vertex. Note that such an are 01 must exist since e is dirty in W but not dirty in P. Let $1 be the start vertex and hy the end vertex of a1 We need to show that 2 is not equal 8 or h and therefore not vertex in W.
p(a'). If 22 + 82
Clearly, we have 21 F h since h1 is not the start vertex of any are in ((a)). We also have 21 # 81. To see this we use Item 3c in Definition 3.4. Without loss of generality, we assume that a goes to the left in W, that is, aj = (8), f,, f). Hence, e is on the left side of cuty in ((11) must therefore also go to the left in P. By the
We now want to show that 22 is not equal to 82 or hi and therefore not a vertex in W. For this let us assume towards contradiction that 22 is equal to 82 or hg. Since 22 is a
The first are
6

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
merge vertex it has exactly two incoming ares a' and a" in W with start vertices s' and s". Each start vertex of the two incoming arcs of 22 in P must appear at least of the paths po(a) and c(a"). If 22 is not the first vertex on Q then one of those start vertices must also appear on Q which contradicts 22 being the first vertex on Q that appears on some path in V. If 22 is the first vertex on Q then #1 must be one of those two start vertices. This means 22 appears on exactly one of the paths v(aa) and ppa");; 22
are a in W is mapped itself by g. With Item 3c this guarantees that the structure of W must be the same the structure of P. Finally, with Item 2 we can see that the classification paths of all examples will be the same in W and P. Consequently, W must also be perfect.
3.2. Extensions of WitBDD for more general Problems
Ordyniak et al. (2024) presented a general theoretical frame- work for learning smallest interpretable models, such as decision trees and BDDs. More precisely, they presented a framework of so-called strong-extendabiiiiyy to compute perfect decision trees and a weaker framework of so-called extendability to compute perfect BDDss With the help of extendability, they showed that BSBDD can be solved in (6- D))) time. They posed as an open question whether this running time can be significantly reduced.
cannot appear on both since that would violate Item 4 of Definition 3.4. Without loss of generality, we assume that #2 appears on paaa) which means we must have a' = a1. We know that the classification path (p(e) diverges from (0(a1) at 21. But since 22 follows 21 on that path we know that 2 must also appear on c(a"), contradicting our assumption that it appears on exactly one of the incoming paths.
We now know that 22 & V(W) and that it must be merge vertex in P. With this we have found the two vertices that are created by the one-step-refinement when subdividing ai and a2. If 01 = 02 then r becomes a P-insertion. Otherwise, becomes an H-insertion.
Next, we argue that BDDs are in fact strong-extendable by invoking WitBDD, In order to verify this, an annotated model (M, A) is required such that M is not a model for the input classification instance and A is some annotation. Moreover, let e be a dirty example, that is, an example which is not correctly classified by M. Afull set of strict extensions for an annotated model (M, A) and example is a set E of strict extensions of (M, such that every model M' that correctly classifies e and is an extension of (M, A) also has an extension of some annotated model in E. Now, observe that our notion of witness BDD together with the definition of rece-seep-effinmeeee correctness of our algorithm Wi tBD shown in Lemma 3.2 verifies that BDDs are strongly extendable.
Now, that we have found suitable one-step-refinement r' we need to show that R with W 1 R admits an embed- ding T into P. Due to how was constructed we know that Items and 2 of Definition 3.4 are fulfilled. We just need to deal with Item 3 of Definition 3.4. For this we de- fine T (a) = ((a) for all ares a that exist in both W and R. We now need to find suitable path in P for all ares that are added by r. The ares that are created by subdividing a1 or 02 are assigned to the corresponding subpaths of (p(a1) and (a()). By construction the newly added vertices #1 and 22 must exist on these paths. Next we need to assign a path to the are ag from ž1 to 22. For simplicity we set 22 to the newly added leaf in the case that r is a leaf insertion. We define T(az) as the subpath of cp(e) that starts at ø1 and ends at 22. By definition of 21 and 22, this path must exist and 21 and 22 must be the only vertices from V(R) that appear on it. With this, Item 3a is fulfilled. Item 3c of Definition 3.4 is also fulfilled by construction. For all ares a on the classification path of e in A up to Z2 the path p(a) muss be fully included in the classification path of e in P. Item 3b of Definition 3.4 must also be fulfilled since these are the only ares where e is added as a witness and when subdividing an arc the witnesses are just copied from the original arc. Since we chose 21 and ž2 as the first vertices that fulfill their respective conditions we clearly have that no two paths overlap in P' outside of their start and end vertices. Hence, Item 4 is also fulfilled. This proves the statement.
and embeddings, and the
Ordyniak et al. (2024, Theorem 3) showed that strong- extendability leads to an efficient algorithm to solve en- sembles, that is, a set S of BDDs with least one split vertex each, where the classification of an example is the majority vote of all BDDs in S. By we denote the total size of all BDDs in the ensemble. We denote the ensemble variant of a problem by adding ENSEMBLE to the problem name. Thus, we obtain the following.
Corollary 3.5. ENSEMBLE BSBDD can be solved in time ((6s22D)) sn).
Moreover, the framework of strong-extendabilge is not only limited to perfect BDDs; it can also be applied to ERROR BSBDD, that is, computing a minimum size BDD with at most errors: Now it not sufficient anymore to choose an arbitrary dirty example in Line 4 of Algorithm 1. If there are at most errors, and the WBDD has size at most s, we found solution. Otherwise, we choose an arbitrary subset S of t + 1 dirty examples. If a solution exists, at least one of them has to be classified correctly. Next, we branch on all one-step- ree--teeeetin for each dirty example in S in Line 5. The correctness of this algorithm can be shown analogously
Finally, to prove the correctness of the algorithm we only need to show that W is perfect if size(W) size(P", From Item of Definition 3.4 and Equation (1) we see that must have V ((W)= V(P). This also means that any
7

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
to Lemma 3.2 and thus we obtain the following:
5. Experiments
Corollary 3.6. ERROR BSBDD and ENSEMBLE ERROR BSBDD can be solved in time ((6625D(( + 1))* sn).
We implemented Algorithm I to gauge how it performs in practice. More precisely, our implementation solves MS- BDD and MSOBDD, the optimization problems where we search for perfect (O)BDD of minimal size. We are not aware of existing implementations for MSBDD and hence compare against the SOTA SAT-implementation for MSOBDD due to Cabodi et al. (2024). Since the imple- mentation of Cabodi et al. was not publicly available, we re-implemented their SAT-encoding.
Moreover, as we discussed in the introduction, Wit can not only be used to solve decision problem BSBDD (and its generalization), but WitBDD can also be used to solve the optimization variant MSBDD. Thus, solve the optimization problems, we obtain additional factor of in the running times.
Also, Wi RDD works for OBDDs by simply checking be- fore Line 7 R is ordered and only calling Re f in if that the case. Hence, we obtain the following.
Experimental setup. For our experiments we used 35 datasets of the Penn Machine Learning Benchmarks (Ro- mano et al., 2022) that were also used by Staus et al. (2025) in their experiments see Table 1 in the appendix. Each of these instances is a binary classification problem. Analogously to Cabodi et al. (2024), we randomly sampled multiple subsets of the ex- amples from each data set: Specifically, for each data set we constructed 10 instances by randomly selecting 10% of the examples and 10 instances by randomly selecting 20% of the examples. This gives total of 700 instances. For each instance we set a time limit of 60 minutes. Our ex- periments were performed on Intel(R) Xeon(R) Platinum (360Y(2) CPUs with 2.6 GHz and 24 cores and 256 GB RAM. Each individual experiment was performed on a pri- vate core with a RAM limit of 2 GB. For the SAT encoding we increased the limit 20 GB. We implemented WDD in C++ and the foTmmormulttion in Python with CaDiCal 1.9.5 as the SAT-solver. Our source code is available in the supplementary material.
Corollary 3.7. BOUNDED-SIZE OBDD can be solved in time (((62_DD)* sn)).
computing optimal decision trees;
Note that this generalizes to the ensemble model and the model with up to f errors.
4. Further Parameterized Complexity Results
Next, we study whether ERROR BSBDD can be solved efficiently when the number d of dimensions is small. Kobourov et al. (2025, Theorem 1) showed that minimum- size decision trees with zero errors, that is, f = O, can be computed in polynomial time when d is a constant, In the conclusion they argue that also a minimum-size decision tree with at most errors can be computed in polynomial time whenever d is a constant. We now show that, in con- trast, ERROR BSBDD remains ha-hard even if d = 4.
Theorem 4.1 (+). ERROR BSBDD and ERROR BSOBDD are NP-hard and cannot be solved in f(s + d) . ((std) time, unless the ETH fails, even if d = 4.
Heuristic running time improvements. Compared to the pure theoretical description, Wi WDD incorporates some first heuristic improvements. Some improvements are also used for the SAT-encodings to make the comparison fair.
In contrast, when the number of dimensions d and the maxi- mum domain size D are bounded, then minimum BDDs can be computed efficiently also for unbounded error param- eter f. This result also holds for OBBDs.
1) Data reduction rules. For WitBDD and for the SAT- encoding, apply some simple data reduction rules that were described by Staus et al. (2025) for computing minimum-size decision trees. These rules reduce redun- dancy in the dataset by removing examples that have the same value as another example in all dimension, dimen- sion where all examples have the same value, and cuts that are equivalent other cuts. It is straightforward show that these rules can also be applied to BSBDD For further details, we refer to Staus et al. (2025, Appendix B).
Theorem 4.2 (+). ERROR BSBDD and ERROR
BSOBDD are FPT D + d.
Ordyniak & Szeider (2021) showed that computing mini- mal size decision tree is unlikely to admit an FPT algorithm for 8, even if D = 2 and t- = 0 and that it is NP-hard even if DD = 2,8 8- = 2, and f = 0. Their reduction works for BDDs and OBBDs as well giving the following hardness.
Proposition 4.3 (+)) BSBDD and BSOBDD (1) cannot be solved in f(s + D)- no(++D) time, unless the ETH fails, even if D= 2, and (2) are NP-hard, even if D = 8 2.
2) Dirty example priority. Any dirty example e in Line 4 of Algorithm is possible. Ideally, we want e to minimize the number of recursive calls in Line 5. Since it takes too long to calculate this number exactly for all dirty examples e, we instead try to approximate as follows for each e: We count
Recall that our witness- -Diesss--DDDaaa algorithm presented in Theo- rem 3.3 has a running time of O(G628D)) sn). Proposi- tion 4.3 shows that the exponential dependence on s cannot be significantly improved without violating the ETH.
Pnttps://dbl http:://ddooo//////// .rrg/11 100.//0.000 10. 5281 /enodo. 15489411
8

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
the number of cuts that separate e and the witness of the last on the classification path of and multiply this number by the length of the current classification path
10a
X
Running times in [ms]
10a
WOOM
3) Budget one improvement. If the difference of the size of the current WBDD and the maximum size s is only one then all dirty examples must be correctly classified with a single one-step-refinemae
10a
10
100000000 xx
p. Thus, when WiDBDD chooses an
are aj for p. all dirty examples must be assigned aj; oth-
10?
erwise we cannot classify them all correctly. Consequently, we can discard all ares ai which violate this property.
10
100%
+ +
SAT WitBDD
10a
4) Pair lower bound. Staus et al. (2025, Section 4) describe a Pair Lower Bound (PairLB) for computing the smallest perfect decision tree. This bound is also valid for BDDs: In the PairLB one constructs SET COVER instance where the universe consists of all pairs of examples of different classes. For each cut in the dataset, subset consisting of all pairs that are separated by e is added to the SET COVER instance I. The set X of all cuts in a perfect BDD is a solution to I. Hence, any lower bound for I is a lower bound for the smallest size of any perfect BDD. To compute such a lower bound, we solve the LP relaxation of an ILP formulation for SET COVER, using Gurobi 10.0.3. (Gurobi Optimization, LLC, 2024). This lower bound is used starting value for s in WDtRD and the SAT-encoding.
2
3
7
Optimal BDD sizes
Figure 3. Comparison of Wit and the SAT encoding based on optimal BDD size. The dashed line represents the timeout.
bigger than 4 the SAT encoding was on average roughly 37 times faster than WitBDD with a median speedup of 7.
The reason for this is most likely that the search space of Wi BDD increases by lot as the size bound increases. For instances with optimal size of at least the function Ref fine was called on average roughly 360-10% times with median of 14 10 On instances with an optimal size < 4 the average was only 4 10 with a median of 3038.
5) Packing lower bound. For WitBDD, we additionally use the SET COVER instance I from the PairLB to compute a packing of the cuts such that each set in the packing has at least one example pair that can only be separated by cuts in that set. The number of sets in the packing is lower bound for I and therefore also for the smallest size of perfect BDD. The advantage is that this lower bound can also be used during the run-time of WitBDD: At the beginning of each recursive call, we can check how many sets of packing are not yet covered by some cut in the current BDD. This number is lower bound for the number of further one-step- refinements needed correctly classify all examples.
In a nutshell, the experiments show that our basic proof-of- concept implementation outperforms the SOTA for small BDD sizes (s 4) while it is substantially slower for medium-size BDDs (5 < S 8) and larger BDDs (s > 9) are out of reach of the current methods.
6. Conclusion
We provided a branch-and-bound algorithm Wi RDD with running time 0(66228D)'-s) sn) for computing minimal size BDDs. This significantly improves upon the previous best known running time guarantee of (ō D 20()) (Ordyniak et al., 2024). Moreover, we provided proof-of-concept implementation WitBDD and showed that WitBDD holds practical promise against the SOTA SAT-formulation. In our opinion, Wi WDDBDD holds a lot of potential for further improvements: Since it is mrunchandd-buudd algorithm, symmetry breaking techniques and improved lower bounds should give substantial speed-up.
For WitBDD we simultaneously use five different packings to improve the likelihood that in some packing the number of uncovered sets is too large. The first packing is computed greedily while the remaining four are computed randomly.
Experimental results. WitBDD solved 443 instances and the SAT encoding solved 557 out of the 700 instances. All instances that were solved by WDD were also solved by the SAT encoding. Figure shows the running times of the two algorithms compared to the sizes of the optimal BDDs. It shows that WitBDD generally performs better than the SAT encoding on instances with small optimal size. In fact, on the 353 instances with an optimal size of at most 4, Wit t BDD is on average roughly 828 times faster than the SAT encoding with a median speedup of 64. However, on the remaining 90 instances with an optimal size that is
While we presented our results to compute minimal-siz BDDs, our techniques also work for computing minimal- depth BDDs: in Algorithm I we just need to restrict the one-step- nne-step-refinements to those that do not violate the depth constraint. Since each BDD with depth at most h has at most 2 inner nodes, this gives an ((6h22D)22 . algorithm for this problem.
22*n) time

---

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
Acknowledgments
Castro, M. P., Piacentini, C., Ciré, A. A., and Beck, J. C. Relaxed BDDs: An admissible heuristic for delete-free planning based on a discrete relaxation. In Benton, J., Lipovetzky, N., Onaindia, E., Smith, D. E., and Srivas- tava, S. (eds.), Proceedings of the Twenty-Ninth Interna- tional Conference on Automated Planning and Schedul- ing (ICAPS 2019), pp. 77-85. AAAI Press, 2019, doi: (w..0/iaap..v9....3....
André Schidler was supported by Austrian Science Fund (FWF) grant 10.55776/P36420 and an Amazon Research Award (Fall/2023). Frank Sommer was supported by the Alexander Humboldt Foundation. Luca Pascal Staus was supported by the Carl Zeiss Foundation, Germany, within the project "Interactive Inference".
Impact Statement
Castro, M. P., Ciré, A. A., and Beck, J. C. Decision diagrams for discrete optimization: A survey of recent advances. INFORMS Comput., 34(4):2271-222 -2295, 2022. doi: 10.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
1287//00C:2022.1170
Costa, V. G. and Pedreira, C. E. Recent advances in decision trees: An updated survey. Artificial Inteli- gence Review, 56(5):4765-4800, 2023. doi: 10.1007/
References
140462-022-102777
Abío, I., Nieuwenhuis, R., Oliveras, A., Rodríguez- Carbonell, E., and Mayer-Eichberger, V. A New Look Constraints. Journal of
Cygan, M., Fomin, V., Kowalik, I.., Lokshtanov, D.,
Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, Parameterized Algorithms. Springer, 2015. doi: 10.1007/ 978-3-319-21275-33
at BDDs for Artificial Intelligence Research, 45:443-480 2012. doi: 10.1613/JAIR.3653.
Downey, R. G. and Fellows, M. R. Fundamentals of Parame- terized Complexity. Texts in Computer Science. Springer, 2013. doi:
Akers, S. B. Binary decision diagrams. IEEE Trans. Com- puters, 27(6):509-511 516, 1978. doi: 10.1109/TC.1978 1675141.
1-4471-5559-1.
Eiben, E., Ordyniak, S., Paesani, G., and Szeider, S. Learn ing small decision trees with large domain. In Proceed- ings of the 32nd International Joint Conference Arti- ficial Intelligence (IJCAI '23), pp. 3184-3192. Interna- tional Joint Conferences on Artificial Intelligence Organi- zation, 2023. doi: 10.24963UUCAA.2223333
Andersen, H. R., Hadzic, T., Hooker, J. N., and Tiede- mann, P. A constraint store based on multivalued de- cision diagrams. In Bessiere, C. (ed.), Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP 2007), volume 4741 of Lecture Notes in Computer Science, pp. 118- 132. Springer, 2007. ISBN 978-3-540-74969-1. doi: 10.1007/978-3-5400 00.1007/978-335400.220 749.54407797777111
Florio, A. M., Martins, P., Schiffer, M., Serra, T., and Vi- dal, T. Optimal decision diagrams for classification. In Proceedings of the 37th AAAI Conference on Artificial In- telligence (AAAI '23), pp. 7577-7585. AAAI Press, 2023. doi: 10. V3716.25922..
Bollig. B. and Wegener, I. Improving the variable ordering of OBDDs is NP-complete. IEEE Trans. Computers, 45
(9)9 1996. doi: 10.1109/12.537122.
Flum, J. and Grohe, M. Parameterized Complexity The- ory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. doi: 10.100773-540-2995544
Bryant, R. F. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv, 24(3): 293-318, 1992. doi: 10. 0..114//336035.136000
Gahlawat, H. and Zehavi, M. Learning small decision trees with few outliers: A parameterized perspective. In Pro- ceedings of the 38th AAAI Conference on Artificial Intel- ligence (AAAI '24), pp- 12100-12108, AAAI Press, 2024. doi: 10.1609/AAA
Cabodi, G., Camurati, P. E., Marques-Silva, J., Palena, M., and Pasini, P. Optimizing binary decision diagrams for interpretable machine learning classification. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 43(10)33083- 3087, 2024. doi: N0.1109/TCAD.2204.33333
Gottlob, G., Scarcello, F., and Sideri, M. Fixed-parameter complexity AI and nonmonotonic reasoning. Ar- tif. Intell., 138(1-2):55 86, 2002. doi: 10.1016/ $0004-3002022000188--0
Carrizosa, E., Molero-Rio, C., and Romero Morales, D. Mathematical optimization classification and regres- sion trees. Transactions in Operations Research, 29(1):
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024.
5-33, 2021. doi: 10.1007/s 17000111010000-0----11111
10

---

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
Harviainen, J., Sommer, F,, Sorge, M., and Szeider, S. Op- timal decision tree pruning revisited: Algorithms and complexity. In Proceedings of the 42th International Conference on Machine Learning (ICML '25), 2025. To appear.
Lee, C. Y. Representation of switching circuits by binary- decision programs. Bell System Technical Journal, 38(4): 985-999, 1959, doi: 10.10022/,153387705.. 1959
x.
Mues, C., Baesens, B., Files, C. M., and Vanthienen, J. De- cision diagrams in machine learning: an empirical study real-life credit-risk data. Expert Systems with Applica- tions, 27(2):257-264, 2004, doi: 1..101/J.ESWA.. 02.001.
Hu, H.,, Huguet, M., and Siala, M. Optimizing binary de- cision diagrams with MaxSAT for classification. In Pro- ceedings of the 36th AAAI Conference on Artificial Intel- ligence (AAAI '22), pp. 3767-3775. AAAI Press, 2022. doi: 10.1609/AAAI 211//AAAAA.333422222922
Niedermeier, R. Invitation to Fixed- Parumeter Algorithmms Oxford University Press, 2006. doi: 10.1093/acprof: 0009780198566066000..0000
Hyafil, L. and Rivest, R. L. Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett., 5(1): 15-17, 1976. doi: 02100660020001190766900000
Oliveira, A. L. and Sangiovanmi-Vinceellli A. L. Using the minimum description length principle to infer reduced ordered decision graphs. Machine Learning 25(1):23-50,
Ignatov, D. Y. and Ignatov, A. Decision stream: Culti- vating deep decision trees. In Proceedings of the 29th IEEE International Conference
1996. doi: 10. 1000/0/F0000 15299.
Tools with Artificial Intelligence (ICTAI 2017), pp. 905-912. IEEE Com- puter Society, 2017. ISBN 978-1-5386-38767. 10.1009ICTA1.2011.001444
Oliver, J. J. Decision graphs extension of decision trees. In In Proceedings of the 4th international workshop on artificial intelligence and statistics (AISTATS)), pp- 343-350, 1993.
doi:
Impagliazzo, R. and Paturi, R. On the complexity of k- SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. doi: 10. 2.1006/CSS.20000 1727.
Ordyniak, S. and Szeider, S. Parameterized complexity of small decision tree learning. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI '21), pp. 6454-6462. AAAI Press, 2021. doi: 10. 10.1609/AAAI. V3517.16800.
Impagliazzo, R., Paturi, R., and Zane, F. Which problems have strongly exponential complexity? Comput. Syst. doi: 10. 2000//css.2001.1777
Sci., 512-)351 2001.
Ordyniak, S., Paesani, G., Rychlicki, M., and Szeider, S. general theoretical framework for learning smallest inter- pretable models. In Proceedings of the 38th AAAI Con- ference on Artificial Intelligence (AAAI '24), pp. 10662- 10669. AAAI Press, 2024. doi: 10. A.009/AALV330 28937.
Kobourov, G., Löffler, M., Montecchiani, F., Pilipezuk, M., Rutter, I., Seidel, R., Sorge, M., and Wulms, The influence of dimensions the complexity of computing decision trees. Artif. Intell., 343:104322 2025. doi: ARIITT///ATIIT..2255......
Perez, G. and Régin, J. Efficient operations MDDs for building constraint programming models. In Yang, Q. and Wooldridge, M. J. (eds.), Proceedings of the Twenty- Fourth International Joint Conference on Artificial Intel- ligence (IJCAI 2015), pp. 374-380, AAAI Press, 2015. ISBN 978-1-57735-738-4
Komusiewicz, C., Kunz, P., Sommer, F., and Sorge, M. On computing optimal tree ensembles. In Proceedings of the International Conference Machine Leurning (ICMI. '23), volume 202 of Proceedings of Machine Learning Research, pp. 17364-17374, PMLR, 2023. doi: 01.5555/3618408.361912.
Romano, J. D., Le, T. T. Cava, W. G. L., Gregg, J. T., Goldberg, D. J., Chakraborty, P., Ray, N. L.. Himmel- stein, D. S., Fu, W., and Moore, J. H. PMLB v1.0: an open-source dataset collection for benchmarking machine learning methods. Bioinform., 38(3):878-88) 2022. doi:
Lai, Y., Liu, D., and Wang, S. Reduced ordered binary deci- sion diagram with implied literals: new knowledge com- pilation approach. Knowledge and Information Systems, 35(3):665-712, 2013. doi: 10. 10000/11115-002-0055
10. L.L.03BBBBOOFRAATTTTTBBAT777
Latour, A. L. D., Babaki, B., and Nijssen, S. Stochas- tic constraint propagation for mining probabilistic net- works. In Kraus, S. (ed.), Proceedings of the Twenty- Eighth International Joins Conference on Artificial Intelli- gence (IJCAI 2019), pp. 1137-1145. ijcai.org, 2019. doi: 10.24963/ICA1I.2019
Sanner, S., Uther, W. T. B., and Delgado, K. V. Approxi- mate dynamic programming with affine ADDs. In van der Hoek, W., Kaminka, G. A., Lespérance, Y., Luck, M., and Sen, S. (eds.). Proceedings of the 9th International Con- ference on Autonomous Agents and Multiagent Systems

---

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
(AAMAS 2010), pp. 1349-1356. IFAAMAS, 2010. ISBN 978-0-9826571-1-9, doi: 10.1145/1838206 1838383.
Schidler, A. and Szeider, S. SAT-based decision tree learn- ing for large data sets, Artif. Intell. Res., 000875--18. 2024. doi: (0.1613/JAIR...1555
Serra, T. Enumerative branching with less repetition. In He- brard, and Musliu, N. (eds.), Proceedings of the 17th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Re- search (CPAIOR 2020), volume 12296 of Lecture Notes in Computer Science, pp. 399-416. Springer, 2020. ISBN 978-3-030-58841-7, doi: 10. 26.
Shotton, J., Sharp, T., Kohli, P., Nowozin, S., Winn, J. M., and Criminisi, A. Decision jungles: Compact and rich models for classification. In Burges, C. J. C.,, Bottou, I.., Ghahramani, Z., and Weinberger, K. Q. (eds.), Proceed- ings of the 27th Anmual Conference on Neural Informa- tion Processing Systems (NIPS 2013), pp. 234-242. 2013. doi: 10.555//9999611399993.
Staus, L. P., Komusiewicz. C., Sommer, F., and Sorge, M. Witty: An efficient solver for computing minimum-size decision trees. In Proceedings of the 39th Conference on Artificial Intelligence (AAAI '25), pp. 20584-2055 AAAI Press, 2025, doi: A3911
Verhaeghe, H., Lecoutre, C., and Schaus, P. Compact- mdd: Efficiently filtering (s)MDD constraints with re- versible sparse bit-sets. In Lang, (ed.), Proceed- ings of the Twenty-Sevntth International Joint Confer- Artificial Intelligence (ICCAI 2018), pp. 1383- 1389. ijcai.org, 2018. ISBN 778-0-9992411-227 doi: 10. 10224963/ICA..221881922
12

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
Appendix
B. Additional Material for Section 4
A. Additional Material for Section 3
B.1. Proof of Theorem 4.1
A.I. Proof of Theorem 3.1
Proof. We provide a reduction from MULTICOLORED k- BICLIQUE, which cannot be solved in (V time unless the ETH fails (Cygan et al., 2015).
Proof. Let (I, 8) be an instance of BSBDD. We can assume [ S s + 1 since a BDD can have most + 1 leafs and therefore cannot correctly classify all examples if they have more than s different classes.
MULTICOLORED k- A-BICLIQUE
Imput: An integer A and a bipartite graph G =
The idea of the algorithm is to simply enumerate all possible BDDs of size 8 and check if they are perfect. We start by creating 8 split vertices and one designated leaf for each class in Σ for a total of at most 2s + 1 vertices. Each split vertex now needs a left child and right child. There at most 2s options for the endpoint of each arc. This means we can enumerate all possible BDD structures in g (z]0(1) time.
[P.Q, E) where P = {Pl..... Pe). Q =
[Q),...: Qk), and [P: = n = Q for
each i [n].
Question: Does G have multicolored k- biclique, that is, a vertex set S such that |S n P. = 1 = |S n Qil such that each vertex in S S P is adjacent to each vertex in S S Q?
Note that it is safe to assume that k S n. The property that all partite sets P. and Q2 have the same number of vertices is only used to simplify the proof. For each partite set P; and Q; we let p!. .i...., .,, and q/. ........g o be an arbitrary but fixed ordering of P; and Qi, respectively.
For each BDD structure we now need to go through all possible cuts for each split vertex. Since there are d dimen- sions and at most D thresholds in each dimension, this step requires d" D - (1)) time for each BDD structure.
Checking if BDD is perfect can be done in (o)0()) time. Hence, the overall running time is (s'. d. D). (7)0(1) n
We create two dimensions dip and d'p, and d' and de per partite set P and Q, respectively. Dimension d'p is partitioned into & different blocks T,,,, ........ T such that the ith block represents the vertex set P.. The other dimensions are partitioned similarly.
Intuition:
In our construction we use many badges, that is, sets of indistinguishable examples. Each block starts with a badge of blue forcing examples of size more than t and ends with badge of red enforcing examples of size more than (or vice versa). Consequently, each minimal-size BDD (a) has to separate each two consecutive blocks with cut to sepa- rate the red enforcing examples of the previous block and the blue forcing examples of the new block and (b) needs another cut within each block to separate the blue forcing examples and the red enforcing examples of that block to fulfill the error threshold We set the size of the BDD to 4 (k (k 1)) = 8k- 4. Hence, each minimal-size BDD has contain all cuts between two distinct blocks (these are 4 (k- 1)) and exactly one cut in each block (these are 4 k).
Transforming a BDD into an WBBD and vice versa. Given a reduced BDD B we can turn B into an equiva- lent consistent WBDD B' with size B) size B') and clag(leaf( e))= = clag: (leaf(B', e]) for all
E; for an example see Figure 1. We first add a new root with exactly one are going to the previous root BB) Next, we need to make sure that all vertices in B have in-degree one since they are all either split vertices or leafs. For a vertex u E (B) with an in-degree of at least two we add new merge vertex m and replace the end vertex in two of the incoming ares of with m. We also create
are (m, v). We repeat this until all vertices v E V(B) have in-degree one except for the new root and the merge vertices. Finally, we set wit (a) = F) B3' a) for all a E A(B'). Since B is reduced, we know that these sets are not empty.
Furthermore, the two cuts in the i-th blocks of dimen- sions d% and d'p, or de and de correspond to a vertex selection in P.. and Q., respectively. We achieve this as follows: Consider the ith block Tp. of dyp Block Th. (after the forcing examples and before the enforeing ex- amples) contains an alternating sequence of badges (size more than t) of blue separating examples and badges (size more than [EG but less than t) of red choice examples. Each consecutive badge of separating examples and badge of choice examples can only be separated the unique cut
Similarly, we can turn any consistent WBDD W into an equivalent reduced BDD W' with size(W)) size(W"') and claw (leaf( e)) = claw (leaf(ll"WWW" .)) for all E E, see Figure! 1. We just reverse the process described above by contracting the outgoing ares of any merge vertex and the root. Hence, a perfect reduced BDD of size s exists if and only if a perfect consistent WBDD of size 8 exists. Thus, we only need to consider consistent WBDDs in Wi LBDD.
13

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
Pi
P2
We create badge Si., of blue separating examples
of size for each H E (P. a E [K]] and each
pi
P2
P2
[n + 1].
We create badge F2 of blue restricting examples of size 2 for each vertex E V(G) and each j [2M:]
The following notation is useful for the assignment of thresh- olds to the examples: For each vertex u E V(G), we say that the badge F% of blue restricting examples for each a E [2A]. the badge C.2 of red choice examples, and the red edge ex- amples corresponding to all edges having one endpoint u. are the examples associated with vertex Observe that each edge example e(u,, w) is associated with both and w.
qi
qi
92
Q
Q2
Figure 4. An instance of MULTICOLORED 2- 2-BICLIQUEWith 2. multicolored 2-bielique is depicted in orange.
between them in this block T or in the corresponding block T in dimension dyp is part of the BDD. Our er- ror threshold t is chosen such that all separating examples have to be classified correctly and that exactly 2k badges of choice examples have to be classified correctly. Since each badge of separating examples has size more than i, at most one badge of choice examples of each block can be classified correctly. This badge of choice examples then corresponds to a vertex selection in P..
Note that [V(G)) = 2 k--k-nn n. In total, we add 4 k- 2 forcing examples. 4 k = enforcing examples, m S |V(G)) = k22 n² edge examples, [V(G)] - x choice examples, 2- k- (n+1) separating examples, and 2k- IV [V)) restricting examples. Since k S n. these are On2 examples.
Description of the dimensions: We create 4 dimensions dip- d'p, de. and dz. In each dimension dim, the examples are arranged in k blocks and one set Rest(dim), which contains all remaining examples. We next describe the ith block Tp, (Tp,,) of dimension di (dfp), see also Figure 5 for an visu- alization. We describe the example sets at each threshold in increasing order.
Additionally, we add one red edge example e per edge in G such that e can only by correctly classified if both endpoints of the corresponding edge are selected. To achieve this, we add badges of blue restricting examples of size more than which have the effect that selecting one endpoint of an edge is not sufficient to classify this edge correctly as red. By setting t accordingly, we ensure that the selected vertices from a multicolored k-biclique.
At the first threshold in the block Tp we have the badge Bj,, of blue forcing examples and the badge Fj of blue restricting examples for any vertex g E Q. At the first threshold in the block The we have the badge R2, of red enforcing examples and the badge 9 pk+1-1 of blue restricting examples for any vertex q E Q.
We first define the parameters s and t, and then we describe the data set. visualization is shown in Figures 4 to 7.
Construction:
Parameters: Let = n and x n Both numbers are used to set the size of sets of examples. We set 4k + 4(k ((k-1) 1) = 8k-4, 4, and we set t = 2- (2-k(nn))) + + 1.2
The next thresholds are populated alternatingly as fol- lows: First, have the badge S%,1 of blue separat- ing examples. Second, at the next threshold, we have all examples associated with the first vertex p] E P.. Third, at the next threshold, we have the badge S% of blue separating examples. Fourth, we have all exam- ples associated with the second vertex p² P, This continuous until the badge S Sp,,+1 of blue separating examples.
Description of the examples: By a badge we denote a set of indistinguishable examples, that is, all examples in that set have the same thresholds in all dimensions.
We create badge BH, of blue forcing examples of size = and a badge RHH of red enforcing examples of size for each H E {P. Q}, each y E (E, and each i [k].
At the last threshold in the block Th. we have the badge Rip, of red enforcing examples and the badge pk+ii of blue restricting examples for any ver- tex q E Q.
q
We create an red edge example e(u, w) for each edge (u, w) E EG")
At the first last in the block Tpe we have the badge BBy of blue forcing examples and the badge F2 of blue restricting examples for any vertex q E Q.
We create a badge Cn of red choice examples of size x for each vertex u E (G).
14

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
Tp.:
Bpr
F2
spp
B
Op
Fo
Spp
E(p))
Fpt
Sp3
F
Rp
Tpy:
Ry
F2
Blot)
Cpt
Fpt
S/2
E(yE)
Cp
Fpt
S/33
Byr
Figure 5. Visualization of the two blocks T and Tp.- corresponding the instance of Figure 4. Here, E(r)) refers all red edge examples corresponding edges having endpoint p!. Furthermore, F2 {Fa) g E Q) and F = { q Q). A possible cut in a block is depicted as "I"". The unique cut in each block of the optimal BDD shown in Figure 7 is shown in orange.
Note that for each badge of forcing examples and each badge of enforeing examples in one of the k blocks in di- mensions dyp and d'p, there exists exactly one badge of restricting examples F? for each E Q at the same thresh- old.
d;:
Tp.
T2
Rest(dp)
dp:
Rest(d"))
Tprr
Tpr
b;:
T2.
T222
Rest(dg)
The blocks TV and Té. for dimensions dg and di defined analogously.
do: Rest(dz)
T3
Tarr
Now, we describe how the blocks Tp. and Tpp are ar- ranged in dimensions d and d'p, respectively. For this, we also need the unused examples Rest(d')) in dimension d'p. Essentially, Rest(df)) contains all examples which not contained in any of the blocks Tpe..... P.e- The sets of unused examples Rest(d),). Rest(de), and Rest(dg) are de- fined analogously. We refer Figure 6 for visualization.
Figure 6. Visualization of the four dimensions using the blocks and the set of unused examples. The cuts "I" between each two consccutive blocks and between the last block and the set of unused examples has to be contained in every optimal BDD.
dy pl
layer
In dimension dip we have the blocks Tp. Tp.r...................... Ty. in that specific ordering, followed by the unused exam- ples Rest(d In dimension d'p we first have the unused ex- amples Rest(dfp,, and then the blocks T Tk-1 ...., TT, in that specific ordering. The arrangement of the blocks and unused examples in the dimensions de and de is analo- gously.
d Rpp
layer 2
d2p < ps
dp
layer
87 R1
We show that G' has multicolored k-biclique if and only if there exists a BDD B with at most s inner nodes making at most errors.
Correctness:
layer
di >
In the following, for dimension dim E (d'p, d'p,, dg % and a badge X (or an example e), we use the notation dim X (dim e), denote a cut, that is, all examples which have threshold smaller than the examples of badge X (example e) in dim go to the left child of this cut, and all remaining examples go to the right child of this cut. Moreover, we say that a cut dim < X violates an example e if e [ddim] 2 X, and otherwise we say that dim < X applies to e.
gf
layer
6 > 1he
layor
45 < 02
4/
layer
%/
Qh.
layer
(=) Let S be multicolored k- k-biclique of G, see Figure 4 for an example. By p: and q: denote the unique vertex of S in P. or in Q, respectively. We now design BDD B with exactly = 8k 4 inner nodes making at most errors, see also Figure for an visualization. We want to emphasis that the constructed BDD B is not unique, that is, there are also other BDD's 's with exactly inner nodes making most
blue
red
Figure 7. Visualization of the optimal BDD B and its 8 layers corresponding the instance of Figure which described in the (=) direction of the correctness proof.
15

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
1 errors.
Layer 2k consists of the two cuts d; Rpp and d'p > Pk-
Basically, the BDD B has 4k layers, see Figure 7 for visualization. A layer is a sequence of (at most two) cuts leading to the blue leaf if all cuts of this layer apply to an example e, and otherwise, if at least one cut of this layer violates an example e, then e is redirected into the next layer. Each example which is violated by at least one cut in the last layer is then put into the red leaf.
Layers 2k + 1 to 4k are defined analogously. We observe the following:
Claim B.2. If an example e has a threshold in some block T in some dimension dim, then the layer corresponding to T in dim is the unique layer in dim which can apply to e.
We say that layer j applies to an example if can be put to the blue leaf via layer j. Otherwise, we say layer j violates e, We use the following observation:
Proof of Claim. For simplicity assume without loss of generality that dim dyp and that T Tye Any ex- ample Tpp has a larger threshold than each vertex ps with j < i in d'p Consequently, the cut dy < Pj in layer j violates e. Also, e has a smaller threshold than each exam- ple in Ryp for each j E
Claim B.1. (a) If all layers violate an example e, then e is classified as red.
k.. Consequently, the cut dí. in layer j - violates e.
(b) Otherwise, if any of the 4k layers applies e, then e is classified as blue.
Claim B.2 implies that i E Rest(dim), then each layer in dimension dim violates e.
Consequently, in order to show that a blue example e is correctly classified it is sufficient that at least one of the layers applies to e. Furthermore, any red example e can only be correctly classified by B if all layers violate e.
Clearly, the BDD B consists of exactly s inner nodes. Hence, it remains to verify that B makes at most t errors.
The first k layers include all cuts in dimension dz. More- over, layer j corresponds to the block The Furthermore, the second k layers include all cuts in dimension d-p More- over, layer (k j) corresponds to the block TV Together these 2 layers correspond to the i vertices of S More precisely, layers j and (k: + j) correspond the vertex Pj selected in the partite set Pj-
B makes at most t 2 ())n-)))+((((()-- errors. Ob- serve that ples, all enforcing examples, all separating examples, and all restricting examples are correctly classified by B. Second, we show that exactly 2k badges of choice examples are cor- rectly classified by B. Recall that each badge of choice ex- amples has size x. Also, recall that we have IV (G)l -a choice examples in total. Thus, the BDD B then misclassifies ex- actly (VV k) x 2 k 2 k- (n- - 1) x choice examples. Finally, we show that B correctly classifies all edge examples corresponding to edges having both end- points in S. Since S is multicolored k-biclique, these are k22 examples. Recall that we have exactly |E(G) edge examples. Hence, we have shown the above steps, then we have verified that makes at most errors. We use Claims B.1 and B.2 to show these statements.
n We first verify that all forcing exam-
For the remaining 2k layers an analog property holds for dimensions & and dz. We now describe the first & layers and then the second & layers in detail:
First i layers:
Layer 1 only consists of the cut d'p < pl.
Layer 2 consists of the two cuts d; > R2p and dGp- p2.
Forcing examples: We show that for a badge Bip of blue forcing examples the ith layer applies: The cut dzp > RØ applies Bip, since Bip is contained in the next block Tp.-- Also the cut dip < Pt applies to Bi since the block Ti. starts with the set Bj.
Layer 3 consists of the two cuts dG > R2 and dGp- < P3-
Layer & consists of the two cuts dx > p and dz < Pt-
Analogously, one can show that the (k + i)th layer applies to Bi,,, that the (2k+ layer applies to B and that the (3k- + i'tth layer applies to B
Layers lo +1 1 to 2k:
Layer is + 1 only consists of the cut d'p > Pl.
Enforcing examples: Let E Rpp By Claim B.2, all layers except layer i violate e. Also, layer i violates e since the cut dG. < Pj violates
Layer & + 2 consists of the two cuts d'p Rby and dip > p2-
Layer l + 3 consists of the two cuts dp < B
Analogously, one can show that non of the layers ap- plies for any other red enforcing example.
and di > p3-
16

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
Separating examples: Consider the badge Shy of blue separating examples. Recall that S P.- By h [n]] we denote the index of p; in the order- ing pl .f.....PP P that is p; = pp. We show that either (a) the ith layer applies if j S h. or (b) the (k + s)th layer applies if j > h. Without loss of generality we assume that j S h. The ith layer applies since the cut do R',, applies to Sj, since S', is contained in the next block T..-- Also the cut d'p < p; applies to SJ. since j S h and p; = -f--
each block (these are exactly 4 k many). We achieve this since all blue forcing examples have to be separated from all red enforeing examples by B since both the forcing and the enforcing examples are arranged in badges of 2 >> ex- amples each. Second, we verify that the cuts in blocks Th, and Ter have the form dlp < pl or d'p S r and dp > p! or dp 2 p. for some vertex pt P,. An analog property also holds for the blocks Th and Tr.- Let S be the corre- sponding vertex set. Finally, we verify that S corresponds to a multicolored k-biclique. Clearly, S contains exactly one vertex of each partite set, and thus we only have to show that there exists an edge between any vertex in S P and any vertex in SnQ.
Analogously, one can find a layer which applies each other separating example.
Restricting examples: We show that for the badge Fi of blue restricting examples where u E Q and i E [k] the ith layer applies: The cut di. > Rpp applies Fü since Ft is contained in the next block The-- Also the
Step 1: First, we show that B contains all cuts between two consecutive blocks in all 4 dimensions. Recall that these are 4 (k- - 1) = 4k - 4 many. Without loss of general- ity, we consider the two consecutive blocks Ty and Tp. Now, consider the badge Rp,, of red enforcing examples of block Tp, and the badge B of blue forcing examples of block Th+11 Note that d'. < B is the unique cut in dimension d'p which separates R'y from B Further- more, we have Rpp. Rest(dim) for each remaining dimension dim E {dd'p, ) Consequently, B contains the unique cut dGp B between the two blocks Tp,e and T
cut d'p < p; applies to Fi since the block Tp, starts with the set F
Analogously, one can show that the (2k + i)th layer applies to the blue restricting examples Fú where u E Q and [ 1, 2k). Then, the argumentation for Fi with E P is analogously.
Choice examples: Consider the badge Cp. of red choice examples. Recall that [p:} = Sn P, By Claim B.2 we only need to consider layers i and (ks (i). Layer violates Cp, since the cut d'p < Ps violates Cp.- and layer k + i violates Cp, since the cut drp > pı vio- lates Cp.-
Second, we verify that B contains at least one cut within each block. Since we have 4k blocks and s I 8k 4, we can then conclude that B contains exactly one cut within each block. Without loss of generality, we con- sider the block Tp. Now, consider the badge By, of blue foreing examples and the badge R'p, of red en- forcing examples of this block Tp. Furthermore, we have Bip,e R'p, E Rest(dim) for each remaining dimen- sion dim E {ddp de d-). Consequently, B contains at least one cut within the block Ti.e-
Analogously, one can show that all layers violate the red choice examples Cg. where { = Snn Q,
q;) be an red edge example corresponding to an edge (p.,g)) E E(G) such that Pi, 9j E S.. The argumentation is almost identical to the choice examples Cp. with p; E S: By Claim B.2 we only need to consider layers i, (k + i), (2k + j), and (3k + j). Layer i violates e since the cut dep < p; violates e, layer (k- + i) violates e since the cut d'p > p; violates e, layer (2k + j) violates since the cut d² < 9j violates e, and layer (3k + violates since the cut d'22 > qj violates
Edge examples: Let
Step 2: By construction, all blue examples and also all red enforcing examples are arranged in badges of size z > t each. Consequently, all blue examples and also all red en- forcing examples have to be classified correctly by B. Moreover, observe that all red choice examples are ar- ranged in badges of size = n each, and that we have |E(G)] < (kn)² < n² red edge examples. Since t 2 k(n - 1) x + (EG) - 1:2, we conclude that B has to classify at least 21 badges of choice examples correctly.
(+) Let B be a BDD with at most s inner nodes making at most / errors. We now show that has a multicolored k-bielique.
Outline: First, we show that B has exactly s = 8k 4 in- ner nodes. Note that we only argue about which cuts the BDD B has to contain; the structure of B is not important. More precisely, we show that B contains all unique cuts which splits all blocks in all dimensions (these are exactly 4- (k- - 1)= = 4k 4 many) and exactly one cut within
We now show that B can classify at most one badge of choice example per partite set P. or Q, correctly. Since there are exactly 2k partite sets, we can then conclude that B classifies exactly one badge of choice example per partite set correctly.
17

---

Learning Minimum-Size BDDs; Towards Efficient Exact Algorithms
It remains to verify that B can classify most one badge of choice example per partite set, say P1, correctly. Con- sider the badge Cpi of red choice examples correspond- ing to the jth vertex of P1 and also the two badges S/.3 and Sp.j+1 of blue separating examples. By construction, ppt.Spp Sp.5+1 are contained in the blocks The and T and in Rest(dg) and Rest(d)). Moreover, we observe the following:
handled analogously by considering the set Fu+1, Hence, we have shown that gets misclassified by B.
Lower Bound: Recall that in the constructed instances, d = 4. Since MULTICOLORED k- K-BICLIQUEis NP-hard and the reduction runs in polynomial time, we obtain the claimed NP-hardness. Moreover, since 8 = 8k - - in the constructed instances and MULTICOLORED K-BICLIQUE cannot be solved in f(k) (G) (o(k) time unless the ETH fails (Cygan et al., 2015), we obtain that ERROR BSBDD cannot be solved in S d) [I]o(++d) time if the ETH is true, where [4] is the overall instance size, even if d = 4.
Claim B.3. (a) Cpf and s can only be separated by the cuts dp < pf and dpp 2 pl. and (b) Cpi and Sp can only be separated by the cuts dzp S p and d'p > pi-
Observe that the BDD constructed in the proof of Theo- rem 4. also an OBDD. Hence, we obtain the same hard- ness results also for ERROR BSOBDD.
By Step 1, we know that B contains exactly one cut in each block. Thus, both cuts in blocks Tp. and ppr are required to classify Cp conrectly. Moreover, for any other vertex p E PI, the two necessary cuts to classify C.p. cor- rectly are disjoint from the necessary cuts for Cgj. Conse- quently, B can classify at most one badge of choice example per partite set correctly.
B.2. Proof of Theorem 4.2
Proof. Initially, we bound the size of any minimal decision tree for the corresponding classification instance (E, A) of the ERROR BSBDD or ERROR BSOBDD instance. Since decision tree is also BDD, this number is then upper bound for any minimal size BDD. This upper bound then allows us to brute force the size of an optimal BDD. After- wards, we can use the same ideas of the XP-algorithm for s behind Theorem 3.1 to first guess the structure of the BDD and second to populate the inner nodes with cuts.
Hence, we have now verified that B classifies exactly one badge of choice examples per partite set correctly. Since each badge of choice examples corresponds to a vertex of V V(G), we obtain a vertex set S containing exactly one vertex per partite set P. and Q,
Note that in each minimal-size decision tree no leaf is empty, that is, each leaf contains at least one example. Conse- quently, the length of each root-leaf path is bounded by the maximal number of cuts which is d D. In other words, the depth of each minimum decision tree is at most d- D. Since decision trees are binary trees, each minimal size decision tree contains at most 2d.D inner nodes. Consequently, each minimal size BDD has size at most 2d.D.
Step 3: According to our choice of t = 2 k(nn - 1) x + [F( - 1² and to Step 2, we conclude that B has to correctly classify at least ka2 red edge examples. In the following, we show that any edge example corresponding to an edge (u, w) such that at least one of its endpoints is not contained in S, is misclassified by B. If we have verified this, we can then conclude that S is a multicolored k-biclique.
Now, we guess the size E [2d-D] of a minimum-size BDD. Next, for this size 2, we use the algorithm behind Theorem 3.1. In other words, first, in 22x (7)0(1) time, we guess the structure of the BDD, where |/| is the overall instance size. Second, in 2dDD (1)((11) time, we guess the cut for each node in the BDD. For OBBDs, we additionally check whether the order property is fulfilled. Overall, the running time is (2d-D)(z' D D +d-D) poll(( where [ is the overall instance size. The algorithm is correct since minimal BDD B has size < 2d-D and at one stage we try this specific value of z. Moreover, since we try all possibilities for the structure of the BDD, the algorithm also finds the structure of B and since we try all possibilities for all cuts, the algorithm also finds the correct cuts.
Now, let e = c(u, w) be an red edge example such that at least one of the endpoints of the corresponding edge (u, w),
say u, is not contained in S. Without loss of generality, we assume that u pi $ S. Now, let {x1} Note that i * j. First, we consider the case that i < J. see also Figure 5 for visualization. Consider the badge Fl of blue restricting examples. Observe that both and Fi are contained in the blocks The and Tp,,. Recall that by Claim B.3, the unique cut in dimension d'p is either dzp- < pi or d'p < pl and that the unique cut in dimension d%p is either dip 2 př or d'p > ri. Consequently, the unique cut of B in T7.6 applies to both and Fl and the unique cut of B in T violates by both e and FL. Moreover, and Fl use the identical thresholds in d and d Thus, we conclude that e and Fl. cannot be distinguished by B. By construction, F!ll = z > and thus both e and Fl are classified as blue. Second, the case that i > j can be
S n P1.
18

---

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
B.3. Proof of Proposition 4.3
Proof. (I) We reduce from HITTING SET. The input con- sists of universe U, family of subsets F of V and number k. The goal is to select S _ U of size k such that each set F E F contains at least one element of S. HITTING SET is NP-hard and cannot be solved in [kk (k()) time, unless the ETH fails (Cygan et al., 2015).
We create classification instance as follows: For each element U we create a binary dimension du. Further- more, for each set F F create blue example ep. Example ef has value 1 in each dimension corresponding to an element u contained in F, and value 0 in each other dimension. Afterwards, we add a red example e* which has value 0 in each dimension. Clearly, D 2. Finally, we set
Note that each minimal size decision tree is equivalent minimal size hitting set (Ordyniak & Szeider, 2021). Since the classification instance contains exactly one red exam- ple e", each minimal size decision tree is a path such that all leaves are blue except one leaf of the last cut which is red. Consequently, each minimal size BDD has the same structure. Furthermore, since the cuts in each such path can be reordered arbitrarily without misclassifying any example, this result extends to OBBDs.
(2) This result follows by the same reduction by reducing from the NP-hard VERTEX COVER which is the special case of HITTING SET where each set in the family F has size 2. As consequence, we obtain 8 =
C. Additional Material for Section 5
We improved the SAT-encoding of Cabodi et al. (2024) for the following reason: It not clear to us how the - implica- tion of the ++ constraint 19) of their model can be encoded efficiently without substantially increasing the number of used variables. This constraint models the classification path of an example m. However, for the correctness of the model it is sufficient have the implication in constraint 19): Initially, is contained in the root i and since the root has a dimension k. and a left and right child, example m is then redirected to exactly one of them, say This ensures that the right hand side for these values of i, n, m, k is fulfilled and thus c.n = 1. Applying this argument iteratively leads the classification path of example m.
19

---

Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms
Instance
vt'
d
d'
8
8'
D
D'
pustoperative-patieniee
72
72
22
17
22
22
14
14
2
3
hayes-roth
84
84
15
15
15
15
8
lupus
79
2
78
3
75
appendicitis
106
106
523
460
7
99
98
molecular www.bbiiooooooooooeeoooo promoters
106
106
228
228
228
228
104
104
2
2
106
106
96
94
5
46
45
cloud
108
108
585
555
7
108
100
cleveland-nominal
130
1:30
17
17
11
lymphography
1 148
148
50
37
50
50
26
23
2
3
hepatitis
155
155
39
28
355
335
28
25
85
85
glass2
162
162
709
667
9
136
132
backache
180
429
151
auto
202
202
35
961
916
31
29
184
182
glass
204
204
9
9
894
846
9
172
165
biomed
209
209
14
14
735
577
9
191
125
new-thyroid
215
214
5
5
329
232
100
73
spect
219
219
22
22
22
breast-cancer
266
266
31
25
40
40
15
15
11
11
heart-statlog
270
270
25
23
376
369
18
18
144
142
haberman
283
283
3
3
89
86
3
49
46
heart-h
22
318
hungarian
293
293
29
22
325
318
19
19
154
154
cleve
302
302
27
25
390
382
18
18
152
151
heart-c
302
302
27
25
390
382
18
18
152
151
cleveland
303
303
27
25
391
383
18
18
152
151
ecoli
326
233
81
schizo
340
340
14
14
2218
2209
14
14
203
203
bupa
341
341
5
5
307
302
5
5
94
94
colic
357
357
75
71
408
400
36
36
85
82
dermatology
366
366
188
188
61
cars
392
388
11
531
9
346
266
soybean
622
622
133
73
133
108
68
49
2
7
australian
690
690
18
16
1155
1119
16
15
350
350
diabetes
768
768
8
8
1246
1238
8
517
515
contraceptive
1358
1358
34
34
Table 1. Overview of the data sets we used for our experiments including their name, number of examples n, number of dimen-
sions d, number of total cuts maximum number of dimensions in which two examples differ, and the largest domain size D. The columns n' d", c', 8', and D' show the values of the data sets after applying all reduction rules described by Staus et al. (2025, Appendix B). Bold entries indicate change of this specific value in the input instance and after the application of all reduction rules.
20


Reviews:
[{"review_id": "xrZqNCFIWT", "reviewer": "Reviewer_cY6R", "summary": "The paper studies the decision problem of Bounded-Size Binary Decision Diagram (BSBDD). Given a labelled data set and a positive integer $s$, the algorithm asks if there exists a BDD that perfectly classifies each example in the labelled data set (each leaf node of the BDD represent a class), and has at most $s$ internal nodes.\n\nThe main result is an algorithm `WitBDD`  that takes as input $s$, a WBDD (witness BDD, a special representation of a BDD) with less than $s$ internal nodes $W$, and a labelled dataset. It returns a refined WBDD with less than $s$ internal nodes that perfectly classifies all examples in the labelled dataset if such a WBDD exists, and returns False otherwise.\n\nThe paper demonstrates that this algorithm runs in $\\mathcal{O}((6 s^2 \\delta D)^s \\cdot sn))$ time, and as such improves on previous theoretical results (Ordyniak et al., 2024). Here, $s$ is the number of internal nodes of the BDD, $n$ is the number of examples in the labelled dataset, $D$ is the domain size of the variable with the largest domain, and $\\delta$ is a parameter that is smaller than $D$.\n\nThe key trick to achieve this results lies in applying an algorithmic paradigm previously used for learning/constructing decision trees. The tree is built incrementally, using examples that are classified incorrectly by the tree (\"witnesses\") to refine the decision tree, by adding a separating hyperplane such that it classifies also that witness correctly.\n\nThe paper applies this principle to BDDs. To this end, the paper introduces a data structure called a  witness BDD (WBDD), which allows for node insertions to incrementally build the BDD. The paper discusses certain properties (consistency, perfection) of WBDDs and how they relate to BDDs that correctly classify all instances in the dataset.\n\nThe paper also derives some other computational complexity results regarding this problem, and performs a small empirical evaluation using a proof-of-concept implementation, to demonstrate the effectiveness of the algorithm against the state of the art (a SAT-based approach from (Cabodi et al., 2024)). The main observation is that `WitBDD` outperforms the SAT-based approach in terms of running time for BDDs with an $s$ of 4 or smaller.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\nQ1: First, Ordyniak et al. (2024) did not implement their algorithm. Moreover, it has a considerably worse theoretical running time bound ($O((3δD)^{s^2}\\cdot n^{O(1)}$) and some brute-force enumerative steps that cannot be avoided. Thus, our algorithm is clearly faster since it has a smaller search space with barely any additional overhead. Moreover, our algorithm is a branch-and-bound algorithm meaning that if we select a suitable object for branching the search space can be much smaller in practice.\n\nQ2: We use $a_2 = \\bot$ to signify that the one-step-refinement is a leaf-insertion since a leaf-insertion does not require a second arc.\n\n\nQ3: An overview of the 35 base instances from which we sampled our 700 test instances can be found in Staus et al., 2024 (https://doi.org/10.48550/arXiv.2412.11954, Table 3 in the Appendix). We will provide a full version of our paper on arxiv where we will include a similar overview.\nThe sampled instances contain between 7 and 271 examples with a median of 31. The largest domain size D is between 2 and 145 with a median of 25 and the number of dimensions d is between 3 and 228 with a median of 21. Also, all instances have exactly two classes.\n\nOur experimental results stratified for individual parameters show large variance which makes it difficult to deduce strong statements on the empirical dependence on the various parameters besides the exponential dependence on $s$ that is evident from the theoretical running time bound. There are many instances with small values for parameters like n, delta, or the number of cuts where our algorithm is faster than the SAT algorithm but there are also some instances with similarly small values for these parameters where we are slower. At first glance, it seems that our algorithm exhibits at most a weak running time dependence on n, delta, and the number of cuts whereas the SAT running times seem to be more dependent on these parameters. To illustrate this we will add more plots for these parameters similar to Figure 3 to the full version of the paper on arxiv.\n\nAppendix A is indeed empty; before submitting we forgot to remove it.", "claims_and_evidence": "I am inclined to believe all the claims made in the paper. However, I get the impression that this paper leans heavily on previous publications and its appendix. I find the paper very clearly written, but also very compactly. I can imagine that it would be easier to parse if the reader would've been familiar with some of the key references (which I am not). Additionally, the appendix contains a bunch of proofs that I honestly did not read, so that I would be trusting the authors on.", "methods_and_evaluation_criteria": "Yes and no. I find that the main contribution of this paper is theoretical. I *really* appreciate the efforts made to create a proof-of-principle implementation and a tiny empirical evaluation. However, I found the description of the empirical evaluation too reductive to be very useful (see below for more details), and the scope of the experiment too limited.\n\nThe introduction argues that minimising BDDs is useful because of explainability and because BDDs can be more compact than decision trees. The largest BDD in the experiments has 7 internal nodes. That doesn't seem like a lot compared to the BDDs that I encounter in daily life. I understand that there's a difference between theory and practice, but now this difference seems to be so big that the empirical evaluation seems somewhat pointless to me.", "theoretical_claims": "As stated above, I feel that the paper does rely a lot on the appendix for its proofs, and maybe also a bit on previous work for easier understanding of the contents. I am not necessarily against that, but it does make me feel that this paper isn't very \"standalone\", and might be more suited for a publication venue that allows for a higher page limit, to aid readability and trust.", "experimental_designs_or_analyses": "The complexity results presented in this paper involve a number of parameters. In particular: the paper states that `WitBDD`'s worst-case complexity dependency on $s$ is optimal. I would have liked to see more details on the experimentation to better understand which components of the theoretical complexity result are also reflected in the empirical evaluation.\n\nFor now, I do not know how many examples there are in the datasets used for the empirical evaluation (so I do not know $n$), and I do not know the domain sizes (so I do not know $D$). I also do not know the number of classes (doesn't matter for the complexity, but I would still be interested in knowing). All in all, I just wanted to have more information about these things, and maybe also about the theoretical complexity of the baseline.", "relation_to_broader_scientific_literature": "I find that the paper positions it very well in terms of the existing literature, as far as I can tell, based on my limited familiarity with the literature in this field. Claims are referenced diligently and timely.", "essential_references_not_discussed": "For completeness, the paper could mention [Latour et al., 2019] as another example of using BDDs for constraint propagation. The works mentioned use DDs to model the set of solutions to a set of constraints, and present filtering algorithms for those datastructures to facilitate propagation. In contrast, [Latour et al., 2019] uses a BDD to represent a *constraint* instead of a set of solutions, and presents a propagation algorithm whose complexity depends on the size of the BDD, making it a potentially relevant application for the work here presented in the paper under review.\n\n[Latour et al., 2019] A. L. D. Latour, B. Babaki, and S. Nijssen, ‘Stochastic Constraint Propagation for Mining Probabilistic Networks’, in _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence_, Macao, China: International Joint Conferences on Artificial Intelligence Organization, Aug. 2019, pp. 1137–1145. doi: [10.24963/ijcai.2019/159](https://doi.org/10.24963/ijcai.2019/159).", "other_strengths_and_weaknesses": "I find that the paper is well-written and mostly well thought-out. There are only a few typos, and the paper contains figures to aid understanding. The structure and signposting facilitate understanding. As mentioned above, I like the attempt at empirical evaluation. I also believe that the contribution is interesting, but mostly from an academic perspective, and less so from a practical one.", "other_comments_or_suggestions": "- Line 19: \"widely studied\" -> \"widely-studied\"\n- Line 65: \"a incorrectly\" -> \"an incorrectly\"\n- Lines 118 - 127: I found this paragraph very hard to parse, because I initially thought that there should be a single $h$ that applies to all pairs of $e_1, e_2 \\in E$. Maybe indexing it as $h_{1,2}$ would've made it easier to parse for me.\n- Figure 2: \"The arcs which\" -> \"The arcs that\"", "questions_for_authors": "Q1. Why only compare to (Cabodi et al., 2024) and not to (Ordyniak et al., 2024)?\nQ2. Lines 216-217: Can the authors please clarify what they mean by \"Additionally, $a_2$ is allowed to be $\\bot$.\"?\nQ3. Can the authors please address my questions about the experimental parameters as stated above, and share any insights that they have regarding how the theoretical complexity dependence on different parameters is translated into an empirical one?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eD2Ryc0R8T", "reviewer": "Reviewer_2cDX", "summary": "This paper proposes a method for learning binary decision diagrams (BDD) that classify given training examples. The proposed algorithm finds the minimum-size BDD that can perfectly classify given examples. Starting from an empty BDD, the proposed algorithm repeats one-step refinements to update the structure of BDD and finds the minimum-size BDD that can correctly classify given samples. The paper theoretically analyses the correctness and the running time of the paper.  In experiments, the paper shows that the proposed method runs faster than the baseline method using a SAT solver when the size of the output BDDs is small.\n\n### Update after rebuttal\nI thank the authors for their reply. I agree that this is an interesting theoretical contribution. However, I still feel that the paper's impact is limited since the proposed algorithm currently scales for small-size BDDs. In such cases, the merits of using BDDs instead of decision trees will be limited. \n\nI agree with the authors that algorithm engineering would further improve the scalability of the exact algorithm. However, we need more evidence to evaluate the practical potential of this paper.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\nThe main purpose of our work is to further develop the algorithmics of computing BDDs, including providing algorithms and proving their correctness. The goal of our experiments is to provide a proof-of-concept implementation of our new approach and to compare it against the SOTA solvers. Doing algorithm engineering to achieve a very fast implementation is beyond the scope of this paper (already most proofs and implementation details are in the appendix). \nSimilar to decision trees, a first paper (Komusiewicz et al., ICML 2023) provided the theoretical foundations for an efficient algorithm and in a later algorithm-engineering project this algorithm was lifted to a competitive solver (Staus et al., 2024).\nIn this second paper, many heuristic lower bounds and reduction rules were provided. Showing the correctness of these lower bounds and rules required some effort.\nSimilar to Staus et al., 2024 lots of promising improvements (symmetry breaking, improved lower bounds) are possible for WitBDD which then could yield a new SOTA solver.\nMoreover, even our proof-of-concept implementation can already contribute to a portfolio solver for the case of small $s$.\n\nExperimental Designs Or Analyses:\n1) There is an overlapping use case for decision trees and BDDs. BDDs are not as commonly used as decision trees, however, one reason for this may be that not too many efficient algorithms for computing them are known. With this work, we want to address this gap. Consequently, our work should be understood as a first step towards having efficient implementations for computing optimal BDDs which then can have a huge impact.\n\n2) Note that our solver WitBDD is not limited to instances where $s \\le 4$, but also solves some instances where $s=7$.\n\nOther Comments and Suggestions:\nIn our setting, $E$ is always a finite set. Hence, the cardinality is just the number of elements.", "claims_and_evidence": "The paper gives theoretical analyses to show that the proposed algorithm can find a minimum-size BDD. Moreover, it runs experiments to show that the proposed algorithm runs faster than the baseline method using a SAT solver.", "methods_and_evaluation_criteria": "The proposed approach to finding a minimum BDD involves an exhaustive search. Since finding a minimum BDD is known to be NP-complete, I think this approach makes sense if we want an exact method.", "theoretical_claims": "I briefly checked the proof of the theoretical claims. They seem correct.", "experimental_designs_or_analyses": "The experimental results are weak in supporting the proposal's effectiveness. The results show that WitBDD is faster than the baseline when BDD sizes are very small. The decision rules that can be represented with such a small BDD are simple ones. Therefore, the paper's results have limited impact in practical situations. \n\nHistorically, BDDs are used when binary decision trees are very large. If the minimum BDD sizes are smaller than 4, then the size of a decision tree representing the equivalent decision rules is also not large. Therefore, we do not have a strong motivation to use BDD in such cases.", "relation_to_broader_scientific_literature": "The paper shows an algorithm for finding the minimum BDD classifying given examples perfectly. This might be a new result. However, its impact is limited since the proposed algorithm works only when the minimum BDD is small. \n\nCompared with decision trees, BDDs are far less used in machine learning. Therefore, the impact of the results is limited.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper seems clearly written and easy to read.", "other_comments_or_suggestions": "- (Line 110) It seems strange to define a set of examples $E$ as a subset of $\\mathbb{R}^d$.  How can we define the cardinality $|E|$?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OhAGhTEkg1", "reviewer": "Reviewer_kRbE", "summary": "The paper presents a novel approach for generating classification Binary Decision Diagrams (BDDs) of bounded size using the witness paradigm. Specifically, given a labeled dataset, the BDD is constructed through a branch-and-bound mechanism that incrementally refines an initial graph. This refinement process involves identifying a data point that is incorrectly classified by the initial BDD, modifying the graph by adding nodes and edges, and associating the newly added edge with the data point (the \"witness\") to reduce the search space. The paper also develops complexity results and provides experimental comparisons against a SAT encoding.\n\n## update after rebuttal\nThank you for the rebuttal - it addressed my questions and I will keep my score as is.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review!\n\n> Suppose there are multiple \"dirty\" witnesses that can be chosen during Algorithm 1. Does the sequence of witnesses to be considered influence the procedure in terms of feasibility/final size?\n\nThe algorithm will always find a minimum-size perfect BDD independent of which specific dirty example is chosen in any call to Algorithm 1. However, the dirty example affects the size of the algorithm's search space. We exploit this property by choosing dirty examples which we deem to yield a small search space, see Appendix D.1 for details.", "claims_and_evidence": "The paper makes a strong contribution to the broad field of BDDs, and is mainly supported by a nice theoretical study. In particular, the proposed construction mechanism is efficient if the data points are \"sufficiently\" close, which is intuitive in the sense that it avoids extra branching. The numerical results also show promising results against one of the state-of-the-art compilation techniques, which I found to be another good evidence to the claims. Finally, I would like to highlight that the error analysis (Section 4) is shot but particularly interesting, and could serve as a foundation for future research streams in misclassification errors.", "methods_and_evaluation_criteria": "Although the proofs can be read as intricate, the methodology is actually intuitive: if a miss-classified point / counter example is found, the procedure applies a so-called one-step refinement that recursively inserts leaves (nodes with out-degree zero) to recover a notion of \"consistency\" relating witnesses with their expected classification paths. \n\nAs the authors mentioned, this technique is fundamentally a BDD extension of the work by Komusiewicz et al. (2023), who originally applied similar refinement principles to decision trees. The complexity results are also relatively comparable. However, this paper is by no means an incremental work, as there are fundamental structural differences between decision trees and BDDs (e.g., the one-step refinement here differs significantly in how leaves are generated). Instead, I see this as an intriguing example of how insights from the decision-tree literature can be extended to improve complexity results and advance the state-of-the-art in BDDs.", "theoretical_claims": "I read all proofs. I have not identified any particular issues, but they are generally significantly intricate because they rely on multiple constructive arguments. My general suggestion is to add further examples/figures in the proof to represent many of these constructive parts; e.g., in Claims C.1. and C.2 in the Supplemental Material, it would be great to connect the results more with Figure 7, which was very helpful to understand the underlying cuts and oeprations.", "experimental_designs_or_analyses": "The experiments are short and are more illustrative of the possible computational benefits of the theoretical approach studied here. I do believe they are sufficient in view of the theoretical scope of the paper.", "relation_to_broader_scientific_literature": "(See above.)", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Suppose there are multiple \"dirty\" witnesses that can be chosen during Algorithm 1. Does the sequence of witnesses to be considered influence the procedure in terms of feasibility/final size?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "i7pKoJvTlf", "reviewer": "Reviewer_Uo3X", "summary": "This is a paper about BDDs, intended as a more compact formulation of decision trees in the context of classification tasks. Komusiewicz et al. (2023) introduced the \"witness\" concept for decision trees, which is extended here to BDDs. The authors focus on the problem of deciding whether a BDD of given maximum size can exactly cover/classify a dataset. An algorithm for this (NP-hard) task is derived and shown to improve the sota. The algorithm can be employed as a subroutine for variants of the decision problem (e.g., partial coverage). The authors also present experiments where their algorithm is tested against a SAT-based approach to the problem. The proposed solution is much faster when small diagrams can cover the data, while the situation changes for medium and large models.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your review!\n\n> As the limitation of the paper is related to the size of the model that can be reasonably processed, the main question to the authors should be whether they believe that the s<=4 limitation should be intended as an intermediate step towards a further improvement of the procedure or not.\n\nFirst, note that our solver WitBDD is not limited to instances where $s \\le 4$, but also solves some instances where $s=7$. Furthermore, even in its current proof-of-concept state, already WitBDD would contribute to a portfolio solver for the case of small $s$. But to address the question, indeed, we believe there is large a potential for improvement and algorithm-engineering work, which we deem to be out of scope for the current paper: Our main focus is to develop the algorithmics of computing BDDs. Similar to decision trees, a first paper (Komusiewicz et al., ICML 2023) provided the theoretical foundations for an efficient algorithm and in a later algorithm-engineering project this algorithm was lifted to a competitive solver (Staus et al., 2024). Concretely, since WitBDD is based on branch-and-bound, symmetry-breaking techniques and improved lower bounds should give substantial speed-ups. However, this type of work would require a different presentation and set-up of the paper and would require much more content to be fitted hence we think this is out of scope for the present work.\n\n> In case of a positive answer, it would be essential to understand why the authors are convinced that the procedure could become faster and be used for larger models. In the case of a negative answer, convincing the reader that even the current limitation could make the procedure applicable for actual machine learning applications would be essential.\n\nSee, above, we believe there is large potential for speed-ups. Furthermore, in general, it is useful to validate heuristics on ground truths, for which we need efficient exact algorithms such as those we provide. Second, exploring the exact algorithmics of a problem often reveals structure that can also be exploited heuristically as well.\n\n> \"s >=4 should be <=\"\n\nThanks!", "claims_and_evidence": "The paper's central claim is Theorem 3.3, and its proof is well detailed in the (body of the) paper.\n\nIn the final outlook section, the authors claim that their algorithm has the potential for further improvement, ideally leading to more competitive results with larger diagrams. Future work will determine whether this is the case.", "methods_and_evaluation_criteria": "The authors also provide a numerical validation against a SAT approach. This is very useful for adequately evaluating the algorithm's potential, and the selected benchmark looks sufficient to identify the proposed approach's pros (and cons).", "theoretical_claims": "The proofs of the results look sound and quite readable. My check was only superficial, but I did not spot any flaw.", "experimental_designs_or_analyses": "The experiment's design and results analysis are relatively straightforward, but the approach seems fair for validating the new algorithm.", "relation_to_broader_scientific_literature": "This paper is focused on a particular field of machine learning. I didn't miss references to broader literature.", "essential_references_not_discussed": "I think all the relevant and recent literature in the field has been properly cited and considered for the discussion.", "other_strengths_and_weaknesses": "The contribution is evident, and the advantages to the SOTA are measurable. Applying the witness idea to this formalism is not trivial, and the result looks helpful. \n\nThe weakness is also evident. The algorithm is competitive only for small models.", "other_comments_or_suggestions": "s >=4 should be <=", "questions_for_authors": "As the limitation of the paper is related to the size of the model that can be reasonably processed, the main question to the authors should be whether they believe that the s<=4 limitation should be intended as an intermediate step towards a further improvement of the procedure or not. In case of a positive answer, it would be essential to understand why the authors are convinced that the procedure could become faster and be used for larger models. In the case of a negative answer, convincing the reader that even the current limitation could make the procedure applicable for actual machine learning applications would be essential.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No concerns."}}]

Author rebuttal:

Meta-review: Solid theoretical contribution for generating classification BDDs of bounded size. It has been appreciated by the reviewers, while it remains unclear the breadth of applicability of the ideas. The reviews may give more detailed suggestions on how to improve the manuscript. All in all, impact is indeed uncertain but the work is considered enough (by most) for presentation at the conference.
Decision: Accept (poster)