|
M.Sc. Thesis Defence 11:00 am, Lecture Hall 2 Fast exact exponential-time algorithms using computations over the subset lattice Avinandan Das Chennai Mathematical Institute. 27-04-18 Abstract In this survey talk we look at three algorithmic techniques, each of which makes use of the fast computation of certain functions over the subset lattice of a finite set. We demonstrate the effectiveness of this approach by describing, for each of these techniques, a deterministic algorithm which runs as fast as the fastest known deterministic algorithm for the corresponding problem. We first take up the Principle of Inclusion and Exclusion (PIE). We describe how PIE can be used to design an algorithm that solves the classical Steiner Tree problem in O*(2^k) time and polynomial space, where n is the number of vertices in the input graph, k is its number of terminals, and the O*() notation hides polynomial factors in the running time. We then describe an algorithm that counts the number of k-length paths in a graph on n vertices in O*(2^n) time and polynomial space. This algorithm is based on finite-difference formulas for polynomials, which are a generalization of PIE. Finally, we describe the Zeta Transform and its inverse the Moebius Inversion, the latter being another generalization of PIE. We describe how these can be computed in O*(2^n) time for the powerset P of a set S of size n. We then show how this pair of transforms can be used to compute the Subset Convolution of a pair of functions on the powerset P, also in time O*(2^n). We describe how this fast subset convolution algorithm can be used to compute the Chromatic Number of a graph on n vertices in O*(2^n) time.
|
