ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910042575339520 |
|---|---|
| author | Philip, Geevarghese Vågset, Erlend Raa |
| author_facet | Philip, Geevarghese Vågset, Erlend Raa |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_05406 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes Philip, Geevarghese Vågset, Erlend Raa Computational Geometry Computational Complexity Discrete Mathematics Data Structures and Algorithms General Topology 68Q27 (Primary) 68Q25, 68Q17, 05C85, 57Q05 (Secondary) F.2.2; G.2.2; I.3.5; F.1.3 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. |
| title | ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes |
| topic | Computational Geometry Computational Complexity Discrete Mathematics Data Structures and Algorithms General Topology 68Q27 (Primary) 68Q25, 68Q17, 05C85, 57Q05 (Secondary) F.2.2; G.2.2; I.3.5; F.1.3 |
| url | https://arxiv.org/abs/2603.05406 |