  Discrete Morse theory has emerged as a powerful tool for a wide range of
problems, including the computation of (persistent) homology. In this context,
discrete Morse theory is used to reduce the problem of computing a topological
invariant of an input simplicial complex to computing the same topological
invariant of a (significantly smaller) collapsed cell or chain complex.
Consequently, devising methods for obtaining gradient vector fields on
complexes to reduce the size of the problem instance has become an emerging
theme over the last decade. While computing the optimal gradient vector field
on a simplicial complex is NP-hard, several heuristics have been observed to
compute near-optimal gradient vector fields on a wide variety of datasets.
Understanding the theoretical limits of these strategies is therefore a
fundamental problem in computational topology. In this paper, we consider the
approximability of maximization and minimization variants of the Morse matching
problem, posed as open problems by Joswig and Pfetsch. We establish hardness
results for Max-Morse matching and Min-Morse matching. In particular, we show
that, for a simplicial complex with n simplices and dimension $d \leq 3$, it is
NP-hard to approximate Min-Morse matching within a factor of
$O(n^{1-\epsilon})$, for any $\epsilon > 0$. Moreover, using an L-reduction
from Degree 3 Max-Acyclic Subgraph to Max-Morse matching, we show that it is
both NP-hard and UGC-hard to approximate Max-Morse matching for simplicial
complexes of dimension $d \leq 2$ within certain explicit constant factors.
