Hardness of approximation for Morse matching

DOI10.1137/1.9781611975482.165MaRDI QIDQ5236355zbMATH OpenOpenAlexFDO

Authors Ulrich Bauer, Abhishek Rathod

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.08380

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of digital topology (68U03)

Abstract: 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 $dleq3$, 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 $dleq2$ within certain explicit constant factors.

Recommendations

• Computing Optimal Morse Matchings
• Approximation algorithms for Max Morse matching
• Computing Optimal Discrete Morse Functions

Cited in

(5)

• Parametrized complexity of expansion height
• Approximation algorithms for Max Morse matching
• Multivariate central limit theorems for random clique complexes
• Computing Optimal Morse Matchings
• Frontiers of sphere recognition in practice

This page was built for publication: Hardness of approximation for Morse matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236355)