Constructing discrete Morse functions

This work aims to study optimality in discrete Morse functions on general cell complex, where optimality entails having the least number of critical elements. This problem is proven here to be MAX-SNP hard. However, we provide a linear algorithm that, for the case of 2-manifolds, always reaches optimality. We prove here various results on the structure of a discrete Morse function. In particular, we provide an equivalent representation by hyperforests. From this point of view, we designed a construction of discrete Morse functions for general cell complexes of arbitrary finite dimension. The resulting algorithm is quadratic in time and, although not guaranteed to be optimal, gives optimal answers in most of the practical cases.