Finite-difference algorithms for counting problems

Citation

Bax, Eric (1998) Finite-difference algorithms for counting problems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/fdc3-5s46. https://resolver.caltech.edu/CaltechETD:etd-01182008-113319

Abstract

We present a novel method to construct counting algorithms:

1. Construct a generating function in which one type of terms corresponds to the objects to be counted.

2. Apply the proper finite-difference operators to produce a formula that counts the terms.

3. Choose finite-difference parameters to reduce the computation required to evaluate the formula.

We compare this finite-difference method to two other methods, the dynamic programming method and the inclusion and exclusion method. Using the problem of counting Hamiltonian paths as an example, we show that finite-difference algorithms require only polynomial space for problems for which dynamic programming algorithms require exponential space. Also, we show that finite-difference algorithms are a generalization of inclusion and exclusion algorithms. Finite-difference algorithms have some free parameters, and inclusion and exclusion algorithms correspond to a particular setting of those parameters. Using the 0-1 matrix permanent problem as an example, we show that the finite-difference parameters can be chosen to produce finite-difference algorithms that are faster than their inclusion and exclusion counterparts.

We use the problems of counting paths by length and counting independent path sets to illustrate how the flexibility of generating functions and extensions to finite-difference operators allow the development of finite-difference algorithms for problems beyond the realm of inclusion and exclusion. Furthermore, we use the problems of sequencing, bin packing, and deadlock avoidance to demonstrate the development of finite-difference algorithms for NP-complete and #P-complete problems.

Thesis Files