Fun with ZDDs: Notes from Knuth’s 14th Annual Christmas Tree Lecture

December 14th, 2008 | Categories: TAOCP
Leave a comment | Trackback

Pages: 1 2 3

Operations on families and Family Algebra

[This is actually Ex. 7.1.4 -- 203, 204.] People from different branches of combinatorics have different operations they want to perform on families of sets. The usual ones are:

  • Union: f\cup g=\{\alpha|\alpha\in f\ \mbox{or}\ \alpha\in g\}
  • Intersect: f\cap g=\{\alpha|\alpha\in f\ \mbox{and}\ \alpha\in g\}
  • Difference: f\setminus g=\{\alpha|\alpha\in f\ \mbox{and}\ \alpha\notin g\}
  • Symmetric Difference: f\oplus g=(f\setminus g)\cup(g\setminus f)

All four operations can be efficiently implemented given the ZDDs of f and g using an easy recursive process based on the smallest support for the two functions. The implementation can be sped up using a memo-cache.

In addition to the ones above, more operations are possible: f\sqcup g (meet), f\sqcap g (join), f\boxplus g (delta), f/g (quotient), f\mod g (remainder). Knuth said he had recently discovered another binary operation that he thinks might prove useful. He likes to call it disjoin since it is similar to the join operation, but works on disjoint sets:
f\star g=\{\alpha\cup\beta | \alpha\in f, \beta\in g, \alpha\cap\beta=\phi\}

The \star is not what Knuth uses as the symbol for disjoin (for the correct symbol, see his hand-written version in the snapshot above), but I haven’t yet figured out the \TeX name for that symbol.

Even more operations on families are possible (see Exercise 7.1.4 — 236): f^{\cap} (closure), f^{\uparrow} (maximal elements), f^{\downarrow} (minimal elements), f\nearrow g (nonsubsets), f\searrow g (nonsupersets), f^{\#} (cross elements). Seeing all these funny symbols, somebody chimed in an obligatory APL joke; somebody else mentioned “family values” in connection with family algebra. People were certainly having fun!

Towards the end, Knuth mentioned various applications of the ideas he had spoken of earlier.

Still More Family Operations (@1h9m45s)

Still More Family Operations (@1h9m45s)

Appl. 1: Covering a chessboard (@54m30s)

Appl. 1: Covering a chessboard (@54m30s)

Application 1. Exact Cover Problems

Exact Cover Problems essentially involves selecting rows from a given boolean matrix in such a way that each column among the selected rows has exactly one 1. A popular example of this kind of problem is Sudoku. Knuth, in an earlier musing, mentioned an efficient dancing links algorithm for solving such problems.
In the present musing, Knuth showed the examples of covering an 8×8-chessboard with 32 dominoes [7.1.4 -- displays (127) to (129)]; covering with monominoes/dominoes/trominoes [display 7.1.4 -- 130]; or covering with dominoes of three colors (red, white, blue) with no adjacent dominoes of the same color [Exercise 7.1.4 -- 216].

Appl. 2: ZDDs as Dictionaries (@1h03m15s)

Appl. 2: ZDDs as Dictionaries (@1h03m15s)

Appl. 2: Query ZDD words dict (@1h15m30s)

Appl. 2: Query ZDD words dict (@1h15m30s)

Application 2. Dictionaries

Knuth showed how, with 5*26 = 130 variables, it is possible to store all five-letter words of the SGB (Stanford GraphBase) in a ZDD, and perform operations such as:

  • Querying for words that match the pattern t?u?h. This involves using family algebra on ZDDs to compute (F/P)\sqcup P where P is the “pattern” t_1\sqcup u_3\sqcup h_5.
  • Finding all words such that when the letter b in it is changed to the letter o, we still get a valid five-letter word. This involves computing (F/(b_j\cup o_j))\sqcup b_j, which gives words like busts (j=1), herbs (j=3) etc.
Application 3. Graph problems

Knuth illustrated application of ZDDs to graph problems by showing how it can be used to find various constrained arrangement of queens on a chessboard (queens-graph): kernels, maximal cliques, dominating sets etc. [See Exercise 7.1.4 -- 241]. All these operations can be implemented using ZDDs and family algebra operations (see Knuth’s sheet). Letting g to be the family of edges of a graph/hypergraph (such that members of g are subsets of the sets of vertices V):

  • Independent Sets are f=\wp\searrow g (Knuth uses Weierstrass P \wp to denote the power set 2^V)
  • Maximal Independent Sets (or Kernels) are the maximal elements f^{\uparrow} of the independent sets
  • Dominating Sets are d=\{\alpha|\alpha\cap\Gamma(x)\neq\phi\ \forall x\in V\} where \Gamma(x)=\{\alpha\in g|x\in\alpha\}
  • Minimal Dominating Set is d^{\downarrow}
  • Maximal Induced Bipartite Subgraphs is (f\sqcup f)^{\uparrow}

Knuth had so much interesting stuff to talk about. But he had spoken for 90 minutes already — so he decided to stop.

I’ve been studying fasc1b for about three months now and have been enjoying myself thoroughly — learning new data-structures & proof techniques, developing my own BDD-base, working out the programming exercises, playing with Conway’s game of Life, coloring graphs and more. I’m still only two-thirds through with the exercises (that total to a respectable 263) — just about to start working on the ZDD exercises. I hope to be able to work my way through the exercises by the end of this year.

Pages: 1 2 3