This is my first post in the folklore knowledge category about an algorithm first used by Yate. I stumbled over this technique while reading the beautiful paper “Determinant Sums for Undirected Hamiltonicity” by A. Björklund (more on this in a few days). Since I did not found an easy to understand presentation of this technique, I decided to write my own one.
When designing algorithms one is sometimes faced with the problem of computing the so-called Zeta Transform of a function , i.e. maps subsets of a given superset onto elements in a fixed computation ring . The Zeta Transform is defined as
Hence, the Zeta Transform is an operator mapping a function onto another function . The naive way of computing for all would be to simply compute from scratch for every . In terms of ring additions, this yields a complexity of
assuming that the evaluation of the function itself can be done in unit time.
Yeta’s algorithm gives a more efficient way to do so. Clearly, the naive computation contains a lot of double calculations which should be avoided. Essentially the trick is to derive a simple recursion formula that allows to apply dynamic programming. This allows to prove the following result.
Theorem (Yate’s Fast Zeta Transform). For every function , the Zeta Transform can be computed for all with ring additions.
Proof. For convenience we write . For every and we define
describing partial sums over all subsets covering all elements in . Obviously we obtain for every and . Now the important observation is the following recursion formula for given by
Clearly, for it holds . For the other case, observe that every subset that occurs in either contains or not and covers all of which explains the second equation in the above recursion formula. Now, the following dynamic programming algorithm allows to finally prove the theorem.
Output: for all
- For all set
- For all do
- For all update using the above recursion formula
- Output for all .
The first step takes evaluations of and the second step yields a total number of ring additions.