Parameterized inapproximability of Morse matching

Ulrich Bauer, Abhishek Rathod

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Article number102148
JournalComputational Geometry: Theory and Applications
Volume126
DOIs
StatePublished - Mar 2025

Keywords

  • Approximation algorithms
  • Discrete Morse theory
  • Parameterized complexity
  • Stochastic topology

Fingerprint

Dive into the research topics of 'Parameterized inapproximability of Morse matching'. Together they form a unique fingerprint.

Cite this