{"id":"arxiv/2603.05406","url":"https://arxiv.org/abs/2603.05406","tags":["cs.CG","cs.CC","cs.DM","cs.DS","math.GN"],"score":0,"title":"ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes","domain":"cs.CG","source":"arxiv","authors":["Geevarghese Philip","Erlend Raa Vågset"],"reviews":0,"subject":"cs.CG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-05","reactions":{}}