Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms

Christian Komusiewicz, Andre Schidler, Frank Sommer, Manuel Sorge, Luca Pascal Staus
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:31322-31341, 2025.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-komusiewicz25a, title = {Learning Minimum-Size {BDD}s: Towards Efficient Exact Algorithms}, author = {Komusiewicz, Christian and Schidler, Andre and Sommer, Frank and Sorge, Manuel and Staus, Luca Pascal}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {31322--31341}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/komusiewicz25a/komusiewicz25a.pdf}, url = {https://proceedings.mlr.press/v267/komusiewicz25a.html}, 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.} }
Endnote
%0 Conference Paper %T Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms %A Christian Komusiewicz %A Andre Schidler %A Frank Sommer %A Manuel Sorge %A Luca Pascal Staus %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-komusiewicz25a %I PMLR %P 31322--31341 %U https://proceedings.mlr.press/v267/komusiewicz25a.html %V 267 %X 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.
APA
Komusiewicz, C., Schidler, A., Sommer, F., Sorge, M. & Staus, L.P.. (2025). Learning Minimum-Size BDDs: Towards Efficient Exact Algorithms. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:31322-31341 Available from https://proceedings.mlr.press/v267/komusiewicz25a.html.

Related Material