ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
For researchers in computational topology and parameterized complexity, this gives the first tight ETH lower bound for OMM, settling the exact dependence on treewidth.
The paper resolves the parameterized complexity of Optimal Morse Matching (OMM) on bounded-treewidth complexes, providing a $2^{O(k \\log k)} n$-time algorithm for any finite regular CW complex and proving ETH-tightness by showing no $2^{o(k \\log k)} n^{O(1)}$-time algorithm exists.
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.