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

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)}$ [12] and the implicit MSO-based algorithm for triangulated manifolds in [11]. The simple invariant and state space allowed us to implement the algorithm and verify it on small instances by exhaustive search.

Under ETH, our running time is optimal: using a known treewidth-based lower bound for Directed Feedback Vertex Set (DFVS), we show that there is no $2^{o(k\log k)}{n}^{O(1)}$-time algorithm for Optimal Morse Matching parameterized by treewidth $k$, even on $2$-dimensional complexes of top coface degree at most $4$. This follows from a new polynomial-time reduction from DFVS to Erasability, to which we apply the recent Width Preserving Strategy (WiPS) framework of [43] to ensure that treewidth is preserved. Combined with the standard equivalence between Erasability and OMM on $2$-dimensional complexes, this yields the ETH-tight $2^{\mathrm{\Theta }(k\log k)}$ dependence.

Our order-based formulation (Feedback Morse Order) shows that working indirectly with vertex orders rather than directly with matchings captures exactly what a treewidth DP for OMM needs to remember. This ordering viewpoint transfers to Alternating Cycle-Free/Uniquely Restricted Matchings (AC-FM/URM) on bipartite graphs, but the connection breaks on general graphs. Here, AC-FM and URM still only admit $2^{\mathrm{\Theta }(k^2)}{n}^{O(1)}$-time algorithms and lack tight-ETH lower bounds. We therefore point to AC-FM and URM as natural candidates for genuinely $2^{\mathrm{\Theta }(k^2)}$-time problems in treewidth and as targets for either $2^{O(k\log k)}n$-time algorithms or matching $2^{o(k^2)}{n}^{O(1)}$ lower bounds.

When we speak of the treewidth of a digraph or a complex, we mean the treewidth of the natural underlying undirected graph in the first case, and of the Hasse diagram in the second. Informally, treewidth measures how close a graph is to being a tree (see also Figure 2): we cover the graph by overlapping bags of vertices arranged in a tree so that each edge lies entirely inside some bag and the bags containing any fixed vertex form a connected subtree; the width is one less than the size of the largest bag, and the treewidth $k$ is the minimum width over all such decompositions; this $k$ will be our parameter throughout the paper. Such decompositions let us localize global constraints: a dynamic program only needs to maintain partial solutions on a bag of size $k+1$ and combine them along the tree, so we can brute-force over states per bag rather than over the whole graph and obtain running times of the form $f(k)n^{O(1)}$. We use rooted nice tree decompositions; unless stated otherwise, we fix an arbitrary root bag and process the decomposition bottom–up. Formal definitions are given in the full version [39, App. A.1]. In this paper we work with the standard nice node types (leaf, introduce-vertex, forget-vertex, and join), and we also use auxiliary introduce-edge bags: unary nodes whose bag is identical to that of their child and that are annotated with a single edge $uv$ in the bag, marking the point where that edge is processed in the dynamic program or reduction. This is a standard refinement that preserves width.

A parameterized problem with parameter $k$ is fixed-parameter tractable (FPT) if it can be solved in time $f(k)n^{O(1)}$ for some computable function $f$; such running times are considered efficient when $k$ is small compared to $n$, since the combinatorial explosion is confined to $f(k)$ while the dependence on the input size remains polynomial. For conditional lower bounds we assume the Exponential Time Hypothesis (ETH) [31], which states that 3-SAT on $n$ variables cannot be solved in time $2^{o(n)}$; ETH is a strengthening of $\mathrm{P}\ne \mathrm{NP}$ that has withstood decades of algorithmic progress and underpins many tight running-time lower bounds. Our hardness source is Directed Feedback Vertex Set parameterized by the treewidth $k$ of the underlying undirected graph of the input digraph $D$, where a feedback vertex set in a digraph $D=(V,E)$ is a set $J\subseteq V$ such that $D\setminus J$ is acyclic.

We use the standard notions of finite regular CW complexes and discrete Morse theory in the sense of Forman [21], and keep the topological preliminaries brief. Face relations are given by closure containment, so the face poset and its directed Hasse diagram encode the incidence data we use. We write $\overrightarrow{H}(X)$ for the directed Hasse diagram of a complex $X$; it has one vertex per cell and an arc $\sigma \to \tau$ whenever $\sigma$ is an immediate face of $\tau$ (a cover relation in the face poset), and hence $dim(\tau )=dim(\sigma )+1$. Let $H(X)$ be the underlying undirected graph; we measure treewidth on $H(X)$, denoted $k$. Simplicial complexes are the special case where cells are simplices (points, lines, triangles, tetrahedra, etc.); we use them in figures and in our reduction.

Forman’s discrete Morse theory can be phrased entirely in terms of matchings on the Hasse diagram $\overrightarrow{H}(X)$ of a finite regular CW complex $X$. A discrete vector field is a matching $W$ on $\overrightarrow{H}(X)$, i.e. a set of pairs $(\sigma ,\tau )$ with $\sigma \to \tau$ an arc of $\overrightarrow{H}(X)$ such that each cell appears in at most one pair. From $W$ we obtain a new digraph $\overrightarrow{H}{(X)}_W$ by reversing exactly the matched arcs and leaving all others unchanged; if $\overrightarrow{H}{(X)}_W$ is acyclic, then $W$ is a discrete gradient vector field. Forman’s correspondence states that (i) every discrete Morse function on $X$ induces such a gradient vector field, and (ii) conversely, every discrete gradient vector field arises from some discrete Morse function; in both directions, the unmatched cells in $W$ are precisely the critical cells of the corresponding Morse function. Collapsing $X$ along the gradient flow yields a smaller Morse complex (see Figure 1) that is homotopy equivalent to $X$ and can make downstream topological computations much cheaper. The Optimal Morse Matching problem (Problem 1) asks for a discrete gradient vector field minimizing the total weight of these unmatched cells.

For our lower bound we use the notion of erasibility of $2$-dimensional simplicial complexes $K$. A $1$-simplex (edge) $e$ is free if it is contained in exactly one $2$-simplex $\tau$, and removing $e$ together with $\tau$ is an elementary collapse. A $2$-simplex is erasible if it can be removed through a sequence of elementary collapses, and $K$ is erasible if every $2$-simplex can be eliminated in this way, that is, if $K$ collapses to a $1$-dimensional complex.

For our algorithmic purposes it is convenient to generalize the matching viewpoint from Hasse diagrams to arbitrary digraphs, and to allow both positive and negative weights. Given a digraph $D=(V,E)$ and a matching $M\subseteq E$, let $D_M$ be the digraph obtained by reversing every edge of $M$ and leaving all other edges unchanged; we call $M$ a feedback Morse matching if $D_M$ is acyclic. In the resulting Feedback Morse Matching (FMM) problem (Problem 3.1), the input is a digraph $D$ and a weight function $\omega :V(D)\to ℝ$, and the task is to find a feedback Morse matching minimizing the total weight of unmatched vertices. When $D$ is the Hasse diagram $\overrightarrow{H}(K)$ of a simplicial complex $K$ and $V(D)$ is identified with the simplices of $K$, discrete gradient vector fields on $K$ are exactly feedback Morse matchings on $D$. Thus OMM is the special case of FMM where $D$ comes from a complex and $\omega$ is nonnegative; in the classical unweighted case $\omega \equiv 1$, the objective is simply the number of critical simplices [32, 3]. Mixed-sign weights in this framework allow one to favour or penalize particular cells (useful for extending a Morse Matching), while the purely negative-weight variant (e.g. $\omega \equiv -1$) on general digraphs corresponds to finding a smallest feedback Morse matching, that is, a minimum-size matching whose reversals destroy all directed cycles in $D$.

As committed procrastinators, we now do our best to avoid thinking about matchings. Instead, we turn to vertex orders. Let $\pi =(v_1,\mathrm{\dots },v_n)$ be a total order of $V$. An edge $(u,v)\in E$ is backward with respect to $\pi$ if $v$ appears before $u$ in $\pi$, and let $M(\pi ):=\{(u,v)\in E:(u,v)\text{ is backward w.r.t. }\pi \}$ be the set of backward edges. Once $\pi$ is fixed, the set of edges to reverse is determined: we always take $M(\pi )$ and reverse exactly these edges. We call $\pi$ a feedback Morse order if $M(\pi )$ is a matching (no two edges in $M(\pi )$ share a vertex).

For any order $\pi$, reversing all backward edges makes every edge point forward along $\pi$, so reversing all backward edges yields an acyclic digraph; if $M(\pi )$ is a matching, it is a feedback Morse matching. Conversely, if $M$ is a feedback Morse matching, then $D_M$ is acyclic, and any topological order $\pi$ of $D_M$ satisfies $M(\pi )=M$. $◀$

By Lemma 11, FMO and FMM are equivalent optimization problems: every optimal feedback Morse order induces an optimal feedback Morse matching and vice versa, so in what follows we work entirely with the order-based formulation.

We run our dynamic program over a rooted nice tree decomposition of the underlying undirected graph of $D$, refined with introduce-edge bags as in Section 2. For a bag $t$ let $X_t$ be its vertex set, $T_t$ the subtree rooted at $t$, $W_t$ the vertices appearing in bags of $T_t$, and $G_t$ the subgraph on $W_t$ whose edges are exactly those whose introduce-edge bags lie in $T_t$. Intuitively, $G_t$ is the part of the graph already processed when we are at $t$, and $X_t$ is its boundary. A global feedback Morse order $\pi$ on $D$ restricts at $t$ to a total order $g$ on $X_t$ and a set $U\subseteq X_t$ of boundary vertices already matched inside $G_t$; we view $U$ as a mask on $X_t$, marking which boundary vertices are already matched. This leads to the following boundary subproblem.

The global optimum of FMO (and hence of FMM) is the value of an R-FMO instance at the root bag, whose boundary is empty; in particular, every state in our dynamic program will consist of an order on the bag together with a mask of matched boundary vertices.

The processed subgraph is empty, so there is a single state with empty order and empty matched set, and cost $0$.

A new vertex $v$ enters the bag (and the graph) with no incident edges yet. It cannot already be matched, so $v\in U$ is forbidden. Otherwise we extend the order $g$ by inserting $v$ at its chosen position; the cost does not change.

A new edge $(u,v)$ is introduced between vertices already in the bag. The order $g$ determines whether it is forward or backward: (i) if $(u,v)$ is forward in $g$, it can never be backward in any extension and thus can never enter the matching; (ii) if $(u,v)$ is backward in $g$, it must be in the matching, and this is the unique place where it is introduced along the path. In the backward case we insist that $u$ and $v$ are currently unmatched in the child and become matched in the parent. Any state where this would create a double match in $G_t$ is discarded.

A vertex $v$ leaves the bag. At this moment all edges incident to $v$ have already been introduced below, so $v$’s matching status is final. We branch on whether $v$ is matched in the child: if $v$ is unmatched, we add $\omega (v)$ to the cost; if $v$ is matched, $v$ never contributes again. We then take the minimum over all child states in which $v$ appears at some position in the child order and the projected order on the remaining bag is $g$.

Two subtrees with the same bag $X_t$ are merged. The processed subgraph $G_t$ is the union of $G_s$ and $G_{s^{\prime }}$, and the bag order $g$ is the same in all three bags. The order $g$ already decides which bag-internal edges are backward, and hence which bag vertices are forced to be matched via those edges; call this set $M_I(g)$. Every feasible state $(g,U_{\bullet })$ must satisfy $M_I(g)\subseteq U_{\bullet }$ for the parent and both children (if $g$ induces conflicting backward edges, all such states are infeasible and $c[t,g,\cdot ]=+\mathrm{\infty }$). Outside $M_I(g)$, a bag vertex can be matched strictly below $t$ in at most one of the two subtrees (there are no edges between the forgotten parts of the two subgraphs). Thus for a parent state $(g,U_t)$ we look over all pairs of child matched sets $(U_s,U_{s^{\prime }})$ such that $M_I(g)\subseteq U_s,U_{s^{\prime }},U_t$ and $U_t\setminus M_I(g)=(U_s\setminus M_I(g))\dot{\cup }(U_{s^{\prime }}\setminus M_I(g)).$ We then set $c[t,g,U_t]$ to the minimum of $c[s,g,U_s]+c[s^{\prime },g,U_{s^{\prime }}]$ over all such pairs.

A formal DP invariant and soundness/completeness proofs can be found in [39, App. A]. At the root bag $r$, the bag is empty, so there is a single state $(\mathrm{\varnothing },\mathrm{\varnothing })$; its value $c[r,\mathrm{\varnothing },\mathrm{\varnothing }]$ is exactly the optimum of FMO on $D$, and hence of FMM and OMM.

Let $D$ be a DFVS instance. For each vertex $v\in V(D)$ we build a local gadget $Y^v=ℱ(v)\cup ℒ(v)$, illustrated in Figure 11. The fuse $ℱ(v)$ is a 2-dimensional simplicial complex homeomorphic to a hollow cylinder $S^1\times I$ with two boundary circles: one is a free boundary circle (marked in red) from which we can start collapsing the complex, “unravelling” the fuse by elementary collapses along the cylinder; the other boundary circle is non-free and is glued to the lock $ℒ(v)$. The lock $ℒ(v)$ is a 2-dimensional simplicial complex homeomorphic to a compact orientable surface of genus ${\mathrm{deg}}^{+}(v)$ with a single boundary component, which is attached to this non-free boundary circle of the fuse. For each outgoing arc $v\to w$ in $D$, we select a distinct simple closed curve on $ℒ(v)$ and glue it to a cross-section circle of the fuse $ℱ(w)$, so that each such curve acts like a finger pinching the fuse: it prevents $ℱ(w)$ from collapsing past that cross-section as long as the lock $ℒ(v)$ is present. In the interior of $ℒ(v)$ we mark a single triangle $\mathrm{deton}(v)$ (the detonator); deleting this triangle makes the entire lock collapsible, eliminates all its pinches, and simultaneously releases every constraint that $ℒ(v)$ imposes on neighbouring fuses. We triangulate $ℒ(v)$ so that it becomes collapsible in either of two situations: after deleting $\mathrm{deton}(v)$, or after its attached fuse $ℱ(v)$ has been completely collapsed. In particular, as long as $\mathrm{deton}(v)$ is present and $ℱ(v)$ is intact, the lock cannot be collapsed while it still pinches some neighbouring fuse.

Fix a directed cycle $C=(v_1,\mathrm{\dots },v_{\mathrm{\ell }})$ in $D$. For each arc $(v_i,v_{i+1})$ (indices modulo $\mathrm{\ell }$) we use one outgoing handle of $ℒ(v_i)$ and glue it so that it pinches the fuse $ℱ(v_{i+1})$ as described above. Taking exactly these pieces along the cycle yields a closed ring of vertex gadgets in which each lock pinches the next fuse; because of the visual similarity to a snake eating its own tail, we call such a ring an $\mathrm{\ell }$-ouroboros, see Figure 12. Along an ouroboros, each fuse can be collapsed from its free boundary until it reaches the first pinch, but it cannot be collapsed past that point while the corresponding lock is present. By construction, every edge in this ring belongs to at least two triangles (coming from the fuse, the lock, or their intersection), so inside this subcomplex there are no free edges and hence no elementary collapses. In particular, an ouroboros persists under any sequence of elementary collapses until at least one of its locks is destroyed, and we will use these rings as obstructions witnessing the presence of directed cycles in $D$.

Let $S\subseteq V(D)$ be a feedback vertex set of size at most $s$, and let $T:=\{\mathrm{deton}(v)\mid v\in S\}$. Deleting $\mathrm{deton}(v)$ makes the entire lock $ℒ(v)$ collapsible and removes all its pinches on neighbouring fuses, so in $Y\setminus T$ we can collapse every lock $ℒ(v)$ with $v\in S$. Since $D\setminus S$ is acyclic, we can order its vertices topologically and, in that order, collapse each remaining gadget $Y^v$: once all incoming locks to $ℱ(v)$ have been removed, the fuse $ℱ(v)$ collapses completely, and by the gadget design the remaining lock $ℒ(v)$ then collapses as well. At the end only gadgets for vertices in $S$ remain, but their locks have already been removed and their fuses are just cylinders with a free boundary, so they also collapse. Thus $Y\setminus T$ is erasible after deleting $|T|=|S|\le s$ triangles.

Conversely, let $T$ be a set of at most $s$ triangles such that $Y\setminus T$ is erasible, and define $S^{\prime }:=\{v\in V(D)\mid Y^v\cap T\ne \mathrm{\varnothing }\}$. Clearly $|S^{\prime }|\le |T|\le s$. Suppose for contradiction that $D\setminus S^{\prime }$ still contains a directed cycle $C=(v_1,\mathrm{\dots },v_{\mathrm{\ell }})$. By construction, the gadgets $Y^{v_1},\mathrm{\dots },Y^{v_{\mathrm{\ell }}}$ contain an $\mathrm{\ell }$-ouroboros subcomplex $Z$. Since no gadget on $C$ intersects $T$, $Z$ is disjoint from $T$, and every edge of $Z$ still lies in at least two triangles in $Y\setminus T$. Hence no edge of $Z$ is ever free, so no sequence of elementary collapses can remove $Z$, and $Y\setminus T$ is not erasible – a contradiction. Thus $D\setminus S^{\prime }$ is acyclic, and $S^{\prime }$ is a feedback vertex set of size at most $s$.

Hardness reductions for problems parameterized by treewidth must control the width of the target instance: a naïve “glue all gadgets at once” construction can easily turn a bounded-treewidth graph into a complex whose Hasse diagram has very large treewidth. In our setting, globally attaching all vertex gadgets $Y^v$ would allow long fuses and many handles to interact and form large grid-like regions in the Hasse diagram, even when $D$ itself has small treewidth; see [5] for a concrete construction or Figure 13 for intuition.

To avoid this blow-up, we assemble the same gadgets incrementally along a nice tree decomposition of $D$, following the Width Preserving Strategy (WiPS) [43]. For each bag $X_t$ we maintain a partial complex $Y_t$ together with a small interface of boundary circles associated with the vertices in $X_t$, and when moving from a child bag to its parent we only apply constant-size local updates touching this interface: at an introduce-vertex bag we attach a fresh gadget $ℱ(v)\cup ℒ(v)$; at an introduce-edge bag we add a single pinching handle between $ℒ(u)$ and $ℱ(v)$; at a forget-vertex bag we cap off the remaining boundary components of $v$; and at a join bag we merge the two partial gadgets for each $v$ along a constant-size interface (on the lock side via a pair-of-pants, on the fuse side by attaching both child cylinders to a common boundary circle and extending it by a short cylinder). Intuitively, each bag only “sees” a bounded portion of the complex, and only a bounded number of new simplices is introduced per bag; see Figure 14.

Instantiating WiPS with our gadgets, we obtain that if $D$ has treewidth $k$, then the complex $Y$ produced by the above construction has a Hasse diagram of treewidth at most $ck+c_0$ for fixed constants $c,c_0$ independent of $D$, and $|Y|$ remains polynomial in $|D|$. A detailed WiPS induction invariant and the exact bag-by-bag construction are in [39, App. B]. Here we only use this width bound together with the gadget behavior described above. Together with the correctness of the DFVS-to-Erasibility reduction proved above, this yields Theorem 13.