Hardness of Approximation for Morse Matching
share
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 ≤ 3, it is NP-hard to approximate Min-Morse matching within a factor of O(n^1-ϵ), for any ϵ > 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 ≤ 2 within certain explicit constant factors.
READ FULL TEXT