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

Geevarghese Philip, Erlend Raa Vågset · 2026

Read ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes by Geevarghese Philip, Erlend Raa Vågset (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05406.txt.

Introduction

Geevarghese Philip and Erlend Raa Vågset resolve Optimal Morse Matching treewidth dependence. The problem seeks a gradient vector field minimizing critical simplices. It is NP-hard. Parameterized by treewidth k, Optimal Morse Matching was long solvable on 3-manifold triangulations in 2 to the O(k squared) times n to the O(1) time. Arbitrary manifolds admitted tractable time, but k dependence was open. A 2 to the O(k log k) times n algorithm follows for regular CW complexes, ruling out 2 to the o(k log k) algorithms unless ETH fails.

Catalog record

CREATORGeevarghese Philip, Erlend Raa Vågset
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE115550
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.05406

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes Geevarghese Philip, Erlend Raa Vågset 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 k , OMM has long been known to be solvable on triangulations of 3 3 -manifolds in 2 O ⁡ ( k 2 ) ​ n O ⁡ ( 1 ) 2^{O(k^{2})}n^{O(1)} time and in FPT time for triangulations of arbitrary manifolds, but the exact dependence on k k has remained an open question. We resolve this by giving a new 2 O ⁡ ( k ​ log ⁡ k ) ​ n 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 ) 2^{o(k\log k)}n^{O(1)} -time algorithm exists unless the Exponential Time Hypothesis (ETH) fails. Chennai Mathematical Institute, Chennai, India, and IRL [email protected]://orcid.org/0000-0003-0717-7303 Western Norway University of Applied Sciences (HVL), Førde, Norway [email protected] https://orcid.org/0000-0003-2289-2268 Supported in part by the Research Council of Norway, grant “Parameterized Complexity for Practical Computing (PCPC)” (No. 274526). keywords Discrete Morse Theory, Simplicial Complexes, Optimal Morse Matching, Treewidth, Parameterized Algorithms, Computational Topology, Dynamic Programming, Exponential Time Hypothesis, Topological Data Analysis. ccs Theory of computation Parameterized complexity and exact algorithms ccs Theory of computation Algorithm design techniques ccs Mathematics of computing Combinatorial algorithms ccs Applied computing Computational topology † † runningauthor: G. Philip and E. R. Vågset 1 Introduction Classical Morse theory [ 37 ] and its discrete counterpart [ 21 , 22 ] provide a framework for simplifying spaces while preserving their essential topological features (see Figure 1 ). They do so by relating scalar functions to gradient flows in the smooth setting and discrete Morse functions to discrete gradient vector fields (Morse matchings) in the combinatorial setting. Much of the computational work on discrete Morse theory has focused on the matching perspective [ 32 , 34 , 39 , 27 , 1 , 23 ] , with the pioneering work on treewidth in computational topology [ 11 ] being no exception. At first sight, this close relationship suggests that the two formulations are interchangeable. In reality, they form diverging roads in the algorithmic landscape; let us follow the one less traveled by. Figure 1: Discrete Morse theory can simplify a space while preserving its homotopy type. Morse theory has applications in topological data analysis and computational topology [ 27 , 2 , 33 , 38 , 23 , 16 ] , robotics and configuration spaces [ 20 , 24 ] , molecular modeling [ 14 ] , and mesh and image processing [ 35 , 18 ] . A recurring primitive in these works is to construct a discrete gradient vector field, also known as a Morse matching, with few critical simplices, yielding strong homotopy-preserving simplifications. Intuitively, such a field is a discrete vector field without “swirls”: there are no loops in the flow lines, so one can contract the space along them without changing the homotopy type. Combinatorially, such a field corresponds to a matching in the Hasse diagram of the complex such that reversing the matched edges does not create any directed cycles. This motivates the Optimal Morse Matching (OMM) problem, also known as Min-/Max-Morse Matching , depending on whether the objective is to minimize the number of critical simplices or maximize the number of matched pairs: Problem 1.1 . Optimal Morse Matching (OMM) Input: A finite simplicial complex K and a weight function \omega:K\to\mathbb{R}_{\geq 0} . Task: Find a discrete gradient vector field W on K . Optimize: Minimize the total weight of critical (i.e., unmatched) simplices. From a computational complexity perspective, OMM and closely related variants are highly intractable: they are NP-hard [ 32 ] , admit strong classical inapproximability bounds [ 3 ] , and are linked to other hard topological decision problems such as Collapsibility [ 41 , 36 ] , Erasibility of 2 -complexes [ 11 , 3 ] , and Shellability [ 25 ] . Algorithmic work includes approximation algorithms for Max-Morse Matching [ 39 ] and a variety of heuristic and workflow-based methods for practical simplification [ 2 , 34 , 27 , 23 , 1 ] . On the parameterized side, using the optimum number of critical simplices as parameter, Erasability and Min-Morse Matching are \mathsf{W[P]} -hard and admit no FPT approximation schemes [ 11 , 4 ] . Figure 2: Three spaces from left to right, all of relatively low (but increasing) treewidth. To circumvent these complexity barriers we turn to treewidth, which intuitively measures how close a combinatorial object is to being a tree; see Figure 2 . An early systematic use of treewidth in discrete Morse theory is the fixed-parameter algorithm of [ 11 ] for OMM , which runs in time 2^{O(t^{2})}n^{O(1)} when parameterized by the treewidth t of an associated spine graph for 2 -complexes, and by the treewidth of either the spine graph or the dual graph for triangulated 3 -manifolds. This was complemented by a Courcelle-style metatheorem for MSO-definable properties on triangulations [ 10 ] , which yields fixed-parameter tractability for OMM on triangulated manifolds of fixed dimension when parameterized by the treewidth of the dual graph. Since then, treewidth has become central in computational topology, leading to FPT algorithms for a range of NP-hard topological problems and invariants [ 13 , 12 , 6 ] , ETH-tight lower bounds for several of these problems [ 8 , 5 , 7 , 42 ] , and detailed studies of the width of triangulated 3 -manifolds [ 28 , 29 , 30 ] . Remark 1.2 . Across the literature, “treewidth k ” is measured on different associated graphs (dual graphs, spine graphs, Hasse diagrams), chosen to suit the problem at hand. For fixed dimension, [ 10 ] shows that the treewidth of the Hasse diagram of a triangulation is bounded by a constant factor times the treewidth of its dual graph, and [ 11 ] shows that in dimension 3 the spine treewidth is likewise linearly bounded in terms of the dual treewidth. Thus, for fixed dimension these parameters coincide up to constant factors hidden in the O(\cdot) -notation. In this paper we simply write “treewidth k ” and, in practice, work with the Hasse diagram. 1.1 Contributions Algorithmic. We give an explicit dynamic program (DP) for a digraph formulation of Optimal Morse Matching parameterized by treewidth k , which in particular solves OMM on all finite regular CW complexes of treewidth k . It runs in time 2^{O(k\log k)}n , thereby extending and improving both the earlier explicit treewidth-based algorithms for 2 -complexes and triangulated 3 -manifolds with running time 2^{O(k^{2})}n^{O(1)} [ 11 ] and the implicit MSO-based algorithm for triangulated manifolds in [ 10 ] . The simple invariant and state space allowed us to implement the algorithm and verify it on small instances by exhaustive search. Optimality. Under ETH, our running time is optimal: using a known treewidth-based lower bound for Directed Feedback Vertex Set (

Read the complete text