Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up
<|reference_start|>Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up: 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.<|reference_end|>
@article{nakamura2024single,
    title={Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential
  Blow-Up},
    author={Kengo Nakamura, Masaaki Nishino, Shuhei Denzumi},
    journal={arXiv preprint arXiv:2403.05074},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05074},
    primaryClass={cs.DS cs.CC}
}