TY - JOUR
T1 - Parameterized inapproximability of Morse matching
AU - Bauer, Ulrich
AU - Rathod, Abhishek
N1 - Publisher Copyright:
© 2024
PY - 2025/3
Y1 - 2025/3
N2 - We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of MIN-MORSE MATCHING within a factor of 2log(1−ϵ)n. Our second result shows that MIN-MORSE MATCHING is W[P]-hard with respect to the standard parameter. Next, we show that MIN-MORSE MATCHING with standard parameterization has no FPT approximation algorithm for any approximation factor ρ. The above hardness results are applicable to complexes of dimension ≥2. On the positive side, we provide a factor [Formula presented] approximation algorithm for MIN-MORSE MATCHING on 2-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa–Farber model of random complexes.
AB - We study the problem of minimizing the number of critical simplices from the point of view of inapproximability and parameterized complexity. We first show inapproximability of MIN-MORSE MATCHING within a factor of 2log(1−ϵ)n. Our second result shows that MIN-MORSE MATCHING is W[P]-hard with respect to the standard parameter. Next, we show that MIN-MORSE MATCHING with standard parameterization has no FPT approximation algorithm for any approximation factor ρ. The above hardness results are applicable to complexes of dimension ≥2. On the positive side, we provide a factor [Formula presented] approximation algorithm for MIN-MORSE MATCHING on 2-complexes, noting that no such algorithm is known for higher dimensional complexes. Finally, we devise discrete gradients with very few critical simplices for typical instances drawn from a fairly wide range of parameter values of the Costa–Farber model of random complexes.
KW - Approximation algorithms
KW - Discrete Morse theory
KW - Parameterized complexity
KW - Stochastic topology
UR - http://www.scopus.com/inward/record.url?scp=85208669485&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2024.102148
DO - 10.1016/j.comgeo.2024.102148
M3 - Article
AN - SCOPUS:85208669485
SN - 0925-7721
VL - 126
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
M1 - 102148
ER -