2026-07-25T02:54:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22180 2024-12-04T06:53:45Z ddc:004 open_access

Single Family Algebra Operation on BDDs and ZDDs Leads to Exponential Blow-Up Nakamura, Kengo Nishino, Masaaki Denzumi, Shuhei Binary decision diagrams family of sets family algebra Binary decision diagram (BDD) and zero-suppressed binary decision diagram (ZDD) are data structures to represent a family of (sub)sets compactly, and it can be used as succinct indexes for a family of sets. To build BDD/ZDD representing a desired family of sets, there are many transformation operations that take BDDs/ZDDs as inputs and output BDD/ZDD representing the resultant family after performing operations such as set union and intersection. However, except for some basic operations, the worst-time complexity of taking such transformation on BDDs/ZDDs has not been extensively studied, and some contradictory statements about it have arisen in the literature. In this paper, we show that many transformation operations on BDDs/ZDDs, including all operations for families of sets that appear in Knuth’s book, cannot be performed in worst-case polynomial time in the size of input BDDs/ZDDs. This refutes some of the folklore circulated in past literature and resolves an open problem raised by Knuth. Our results are stronger in that such blow-up of computational time occurs even when the ordering, which has a significant impact on the efficiency of treating BDDs/ZDDs, is chosen arbitrarily. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kengo Nakamura and Masaaki Nishino and Shuhei Denzumi 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.52 urn:nbn:de:0030-drops-221803 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.52 eng https://creativecommons.org/licenses/by/4.0/legalcode