ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes

Abstract

The Optimal Morse Matching (OMM) problem asks for a discrete gradient vector field on a simplicial complex that minimizes the number of critical simplices. It is NP-hard and has been studied extensively in heuristic, approximation, and parameterized complexity settings. Parameterized by treewidth $k$, OMM has long been known to be solvable on triangulations of $3$-manifolds in $2^{O(k^2)}{n}^{O(1)}$ time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on $k$ has remained an open question. We resolve this by giving a new $2^{O(k\log k)}n$-time algorithm for any finite regular CW complex, and show that no $2^{o(k\log k)}{n}^{O(1)}$-time algorithm exists unless the Exponential Time Hypothesis (ETH) fails.

Full version. 44 pages, 21 figures. Conference version published in SoCG 2026