Binary Decision Diagrams

Take a map of mainland USA, and consider the following problems:

Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?

Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.

There are several ways to colour the map with four colours such that no two adjacent states have the same colour. If the colours have weight 2, 3, 5 and 7, which colourings have the least total weight?

Or consider these:

How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?

List all 5-letter words that remain words after replacing a b with o.

How can we solve these efficiently?

Families and ZDDs

Take the second map problem for example. Let U (the universe) be the set of all mainland USA states. Any selection of non-adjacent states can be viewed as a subset of U.

Consider F, the set of all such subsets. For clarity, we call a set of subsets of U such as F (equivalently, a subset of the power set of U) a family of sets over U. Thus "set" usually means a subset of U, and "family" means a collection of these subsets. Hypergraphs are equivalent to families of sets, but we follow Knuth’s lead and prefer "families" over "hypergraphs", due to greater familiarity.

It turns out we can describe F in terms of basic families that by themselves are easy to describe. If we had a clever method to represent families on a computer, we might be able to quickly construct a representation for F from the basic families. If the method were really clever, we could subsequently determine the set in F of maximum weight, and solve the problem.

A ZDD is a really clever data structure that represents a family of sets. ZDD stands for zero-suppressed binary decision diagram but this is unimportant.

Combinatorial problems such as the above can be viewed as asking questions about a particular family of sets. With ZDDs, we can answer them efficiently.

References

See:

Roughly speaking, BDDs beat ZDDs when the membership of many elements is often irrelevant, while ZDDs beat BDDs when many elements are often absent. I focus on ZDDs, because when I started these notes I was interested in a problem that I felt was better suited for ZDDs.

Joan Thibault sent me several articles describing more variants of binary decision diagrams, including a sort of hybrid BDD-ZDD that combines the best of of both worlds:


Ben Lynn blynn@cs.stanford.edu 💡