Hardness Results in Discrete Morse Theory for 2-Complexes

Hardness Results in Discrete Morse Theory for 2-Complexes

Explore hardness results in discrete Morse theory for 2-complexes in this 34-minute conference talk. Delve into the problem of minimizing critical simplices (Min-Morse Matching) from inapproximability and parameterized complexity perspectives. Learn about approximation factor limitations, WP-hardness with standard parameterization, and the absence of FPT-approximation algorithms. Discover an O(n/log n)-factor algorithm for Min-Morse Matching on 2-complexes, leveraging polynomial-time erasability determination. Gain insights into monotone circuits, reductions, and constructions related to this topic in applied algebraic topology.