# What is a ZDD?

> A zero-suppressed decision diagram is a BDD variant tuned for families of sparse sets: exact covers, paths, word lists. How it differs from a BDD.

**ZDD (zero-suppressed decision diagram)**: A ZDD is a variant of the binary decision diagram, introduced by Shin-ichi Minato, that represents families of sets compactly by removing nodes whose HI branch leads to 0.

A **ZDD**, or zero-suppressed decision diagram, is a [BDD](https://cracked.guide/glossary/bdd) with a different reduction rule, designed for **families of sets** where each set contains few elements. Shin-ichi Minato introduced it in 1993; Knuth calls ZDDs one of the nicest ideas in the subject.

## The one rule that changes

A reduced BDD removes a node when both of its branches go to the same place. A ZDD instead removes a node when its HI branch goes to 0, meaning "this element is never in any set from here". For sparse families (most elements absent from most sets) that removes almost everything, so the ZDD is far smaller than the BDD of the same family.

## What they are good for

Representing every solution of an [exact cover](https://cracked.guide/glossary/exact-cover) problem at once, all simple paths in a graph, a dictionary of words, or prime implicants, and then counting, filtering and combining those families with a family algebra. Knuth covers them at the end of [§7.1.4](https://cracked.guide/guide/knuth-w108-0), in Volume 4A.

## Questions

### When should I use a ZDD instead of a BDD?

When the objects are sets with few members out of many possible elements. For general Boolean functions, a BDD is usually the better fit.

---

Source: https://cracked.guide/glossary/zdd
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.