Hardness of Approximation for Morse Matching
Ulrich Bauer Abhishek Rathod
math.AT cs.CC cs.CG math.CO






[5]





<cit.>
<ref>
7



arrows,calc



SeaGreen1







appsecAppendixAppendices

plain
thm[theorem]Theorem
cor[theorem]Corollary
prop[theorem]Proposition
lem[theorem]Lemma
definition
rmk[theorem]Remark
defn[theorem]Definition
thmTheoremTheorems
lemLemmaLemmas

pf
plainurl







































 
















































































































































Department of Mathematics,
Technical University of Munich, Germany. 
U. Bauer and A. Rathod 

Ulrich Bauer and A. Rathod


2
34th Symposium on Computational Geometry (SoCG 2018)
SoCG 2018
SoCG
2018







Hardness of Approximation for Morse Matching[Research supported by the DFG Collaborative Research Center TRR 109 Discretization in Geometry and Dynamics.]
    Abhishek Rathod
    December 30, 2023
==========================================================================================================================================================





Discrete Morse theory has emerged as a powerful tool for a wide range of problems, including the computation of (persistent) homology. In this context, discrete Morse theory is used to reduce the problem of computing a topological invariant of an input simplicial complex to computing the same topological invariant of a (significantly smaller) collapsed cell or chain complex. Consequently, devising methods for obtaining gradient vector fields on complexes to reduce the size of the problem instance has become an emerging theme over the last decade. While computing the optimal gradient vector field on a simplicial complex is NP-hard, several heuristics have been observed to compute near-optimal gradient vector fields on a wide variety of datasets. Understanding the theoretical limits of these strategies is therefore a fundamental problem in computational topology. 

In this paper, we consider the approximability of maximization and minimization variants of the Morse matching problem. We establish hardness results for  Max-Morse matching and  Min-Morse matching, settling an open problem posed by Joswig and Pfetsch <cit.>. In particular, we show that, for a simplicial complex of dimension d ≥ 3 with n simplices, it is NP-hard to approximate Min-Morse matching within a factor of O(n^1-ϵ), for any ϵ>0. Moreover, we establish hardness of approximation results for Max-Morse matching for simplicial complexes of dimension d ≥ 2, using an L-reduction from Degree 3 Max-Acyclic Subgraph to Max-Morse matching.





§ INTRODUCTION


Classical Morse theory <cit.> provides a method to analyze the topology of a smooth manifold by studying the critical points of smooth functions defined on it. Forman's discrete Morse theory is a combinatorial analogue of Morse theory that is applicable to regular cell complexes <cit.>. It has become a popular tool in computational topology and visualization <cit.>, and is actively studied in algebraic, geometric, and topological combinatorics <cit.>. In Forman's theory, discrete Morse functions play the role of smooth Morse functions, whereas discrete gradient vector fields are the analogues of gradient-like vector fields. Forman's theory also has an equivalent graph theoretic formulation <cit.>, in which the acyclic matchings (or Morse matchings) in the Hasse diagram of a simplicial complex correspond to the discrete gradient vector fields on the simplicial complex.  We shall use the terms gradient vector fields and Morse matchings interchangeably. In the next subsection, we will elaborate on the practical interest <cit.> in computing gradient vector fields on simplicial complexes with (near-)optimal number of critical simplices (unmatched nodes in the Hasse diagram).



 §.§ Motivation


The idea of using discrete Morse theory to speedup the computation of homology <cit.>, persistent homology <cit.>, and multidimensional persistence <cit.> hinges on the fact that discrete Morse theory helps to reduce the problem of computing homology groups of an input simplicial complex to computing homology groups of a smaller collapsed cell or chain complex. In fact, certain state of the art methods for computing homology groups of complexes  <cit.> and persistent homology of filtrations <cit.> depend crucially on discrete Morse theory. In particular, in the numerical experiments for homology computation reported in  Harker et al. <cit.>, a discrete Morse theory based preprocessing step led to a speedup of several orders of magnitude over existing methods on a wide variety of datasets. In a followup work, Harker et al. <cit.>  devised a discrete Morse theory based framework to efficiently compute the induced map on homology, a problem that arises in Conley index computations. More recently, Brendel et al. <cit.> designed a discrete Morse theory based algorithm to compute (typically small) presentations of the fundamental group of finite regular CW-complexes, and certain knot invariants.  

Thus, finding near-optimal gradient vector fields is a central problem computational topology, with a wide range of applications.
However, finding an optimal gradient vector field turns out to be an NP-hard problem, as shown by Joswig et al. <cit.> via a reduction from the erasability problem introduced by Eǧecioǧlu and Gonzalez <cit.>. 

On the other hand, certain heuristics for Morse matching have been reported to be highly effective, often achieving optimality in practice <cit.>. This naturally raises the question of approximability: to which extent is it feasible to obtain near-optimal solutions for Morse matching in polynomial time? By establishing bounds on the hardness of approximation, we make it evident that for certain instances, the otherwise effective heuristics would fail to compute near-optimal Morse matchings. 



 §.§ The Morse Matching Problems


The Max-Morse Matching problem () can be described
as follows: Given a simplicial complex 𝒦, compute a gradient
vector field that maximizes the cardinality of matched (regular) simplices,
over all possible gradient vectors fields on 𝒦. Equivalently,
the goal is to maximize the number of gradient pairs. For the complementary
problem Min-Morse Matching (), the goal is to compute
a gradient vector field that minimizes the number of unmatched (critical)
simplices, over all possible gradient vector fields on . While
the problem of finding an exact optimum are equivalent for and , the approximation variants of these problems have vastly
different flavors, as we shall note in Sections <ref> and <ref>.



 §.§ Related work


Based on the relationship between erasability and Morse Matching observed by Lewiner <cit.>,
Joswig et al. <cit.> established NP-completeness of the Morse Matching Problem, using a reduction that is not approximation preserving, and posing the approximability
of Morse matching as an open problem <cit.>.
The algorithmic question of finding optimal discrete Morse functions
on simplicial complexes is a well studied problem. Most methods so
far have relied on effective heuristics <cit.>.
The first theoretical result in context of Morse matchings was established by Burton et al. <cit.>, who developed a fixed parameter tractable algorithm for computing optimal Morse functions on 3-manifolds. More recently, Rathod et al. <cit.> proposed the first approximation algorithms for on simplicial complexes that provide constant factor
approximation bounds for fixed dimension. 

Methodologically, the mechanism of collapses employed in our proof of hardness of approximation for bears notable resemblance to sequential collapsing of Bing's house gadgets used by Malgouryes and Francés <cit.>  and Tancer <cit.> for proving NP-hardness results for certain collapsibility problems.



 §.§ Our contributions 


In Section <ref>, using Tancer's result <cit.> about NP-completeness
of collapsibility, we provide a straightforward proof of
inapproximability of on simplicial complexes with dimension d≥ 3.
In particular, we prove that, assuming P≠𝑁𝑃, 
there is no O(n^1-ϵ)-factor approximation algorithm
for for any ϵ>0, where n denotes the total number
of simplices in a given complex . 
Then, in Section <ref>, we prove that, for any ϵ>0, approximating for simplicial complexes of dimension d≥2 within a factor of (1 - 1/4914)+ϵ is NP-hard and approximating it within a factor of (1 - 1/702)+ϵ is UGC-hard. In particular, this shows that has no PTAS unless P=𝑁𝑃. 



§ BACKGROUND AND PRELIMINARIES 




 §.§ Simplicial complexes
 


A k-simplex σ= V is the convex hull
of a set V of (k+1) affinely independent points in ℝ^d. We call k the dimension of σ.
We say that σ is spanned by the points V.
Any nonempty subset of V
also spans a simplex, a face of σ. σ is a coface
of τ iff τ is face of σ. 
We say that σ is a facet of τ if σ is a face of τ with σ=τ-1. 
A simplicial complex   is a collection of simplices that satisfies the following conditions:


  * any face of a simplex in  also belongs to , and

  * the intersection of two simplices σ_1,σ_2∈ is either empty or a face of both σ_1 and σ_2. 

The underlying space of  is the union of its simplices, denoted by ||. The underlying space is implicitly used whenever we refer to  as a topological space.

An abstract simplicial complex  
is a collection of finite nonempty sets A ∈ such that every nonempty subset of A is also contained in .
The sets in  are called its simplices.
For example, the vertex sets of the simplices in a geometric complex form an abstract simplicial complex, called its vertex scheme.
If  is a geometric simplicial complex whose vertex scheme is isomorphic to an abstract simplicial complex , then  is a geometric realization of . It is unique up to simplicial isomorphism.

We will use the construction of a pasting map <cit.> to perform vertex and edge identifications on simplicial complexes.
Given a finite abstract simplicial complex , a labelling
of the vertices of  is a surjective map f:^(0)→ C where the set C is called the set of vertex labels.
Then, the set { f(σ) |σ∈} is an abstract simplicial complex. Let  be a geometric realization. Then f induces a simplicial quotient map g:||→||, called the pasting map associated with f. 

In particular, given an equivalence relation ∼ on the vertices of , the surjection sending each vertex to its equivalence class induces a pasting map. We will use this construction to perform identifications of simplices. For example, the wedge sum of a collection of pointed simplicial complexes (complexes with a distinguished vertex, called the basepoint) can be constructed this way using the equivalence relation identifying all basepoints.

 



 §.§ Discrete Morse theory and Erasability



Our focus in this paper is limited to simplicial complexes, and hence
we restrict the discussion of Forman's discrete Morse theory to simplicial
complexes. We refer to <cit.> for a compelling expository introduction. 

A function f on a simplicial complex  is called a discrete Morse function if


  * f is monotonic, i.e., σ⊆τ implies f(σ) ≤ f(τ), and

  * for all t ∈(f),  f^-1(t) is either a singleton {σ} (in which case σ is a critical simplex) or a pair {σ,τ}, where σ is a facet of τ (in which case (σ,τ) form a gradient pair and σ and τ are regular simplices). 

Given a discrete Morse function f defined on complex , the discrete gradient vector field  of f is the  collection  of pairs of simplices  (σ,τ), where (σ,τ) is in  if and only if σ is a facet of τ and f(σ)=f(τ).

Discrete gradient vector fields have a useful interpretation in terms of acyclic graphs obtained from matchings on Hasse diagrams, due to Chari <cit.>.
Let  be a simplicial complex, let  be its Hasse diagram, and let M be a matching in the underlying undirected graph . Let (M) be the directed graph obtained from  by reversing the direction of each edge of the matching M. Then M is a Morse matching if and only if (M)	is a directed acyclic graph. Every Morse matching M on the Hasse diagram  corresponds to a unique gradient vector field _M on complex  and vice versa. For a Morse matching M, the unmatched vertices correspond to critical simplices of _M, and the matched vertices correspond to the regular simplices of _M.

A non-maximal face σ∈ is said to be a free face if it
is contained in a unique maximal face τ∈. 
If τ=σ+1,
we say that ^' = ∖{σ,τ} arises from  by an elementary
collapse, denoted by ↘^e^'. Furthermore, we say that
 collapses to , denoted by ↘,
if there exists a sequence =_1,_2,…_n=
such that _i↘^e_i+1 for all i. 
If ↘, or more generally, if  and  are related through a sequence
collapses and expansions (inverses of collapses),
then the two complexes are simple-homotopy equivalent
type. In particular,  and  are homotopy equivalent. Furthermore, if  collapses to a point, one says that  is collapsible
and writes ↘0.

A simplicial collapse can be encoded by a discrete gradient.

  
  Let  be a simplicial complex with a discrete gradient vector field ,
  and let ⊆ be a subcomplex.
  If ∖ is a union of pairs in , then ↘.

In this case, we say that the collapse ↘ is induced by the gradient . As a consequence of this theorem, we obtain:


Let  be a simplicial complex with a discrete gradient vector field  and let m_d denote the number of critical simplices of  of dimension d. Then  is homotopy equivalent to a CW complex with exactly m_d cells of dimension d.

In particular, a discrete gradient vector field on  with m_d critical simplices of dimension d gives rise to a chain complex having dimension m_d in each degree d, whose homology is isomorphic to that of . This condensed representation motivates the algorithmic search for (near-)optimal Morse matchings.

We will later use the following elementary lemma about gradient vector fields.


Let  be a connected simplicial complex, let p be a vertex of , and let _1 be a discrete gradient on  with m_0>1 critical simplices of dimension 0 and m critical simplices in total. Then there exists another gradient vector field  on  with p as the only critical simplex of dimension 0 and m - 2(m_0-1) critical simplices  in total. 
 
 Let  be the set of all the 1-simplices paired with 2-simplices in .
Let _1 be the 1-skeleton of . Then, by <cit.>, the 1-complex _1 ∖ is connected, and one can compute a gradient vector field _1 on _1 ∖ with p as the single critical 0-simplex 
using depth first search starting from p (see, e.g., <cit.>). Let ⊂ consist of all gradient pairs of  contained in ∖ (_1 ∖) = (∖_1) ∪. Note that, by construction,  does not contain any pairs of dimensions (0,1), while  _1 has only such pairs.
Since the gradient vector fields _1 and  are defined on disjoint sets of simplices, it follows that = _1∪ is a gradient vector field with the desired property.


  Given a collapsible simplicial complex  and an arbitrary vertex p ∈, there exists a gradient vector field  on  with p as the unique critical simplex of .


Borrowing and extending the terminology
used in <cit.>, we make the following definitions:
A maximal face τ in a simplicial complex  is called an internal simplex if it has no free face. 
If a 2-complex  collapses to a 1-complex, we say that  is erasable. Moreover, for a 2-complex , the quantity  is the minimum number
of internal 2-simplices that need to be removed so that the resulting complex collapses to a 1-complex. Equivalently, it is the minimum number of critical 2-simplices of any discrete gradient on .
For a complex , we denote the set of d-simplices of  by d. 

 Given a 2-complex , we say that a subcomplex ⊆ is an erasable subcomplex of  (through the gradient ) if there exists another subcomplex ⊆ with ↘ (induced by the gradient ) such that ∖⊆ and 
∖ =.


 We say that a simplex σ is eventually free (through the gradient ) in a complex  if there exists a subcomplex  of  such that ↘ (induced by ) and σ is free in .
Equivalently,  collapses further to a subcomplex not containing σ.




If _1,_2 are erasable subcomplexes of a 2-complex , then so is their union.


Let _1 be a discrete gradient erasing _1, and _2 a discrete gradient erasing _2.
Without loss of generality, we may assume that both gradients have only pairs (σ,τ) of dimension (1,2), and that all such pairs are in _1 or _2, respectively, and σ is eventually free; removing all other pairs still yields an erasing gradient.
Now consider the collapse ↘_1 induced by _1 and the collapse ↘_2 induced by _2. 
Restricting the gradient _2 to the subcomplex _1, we obtain
a gradient _12 = {(σ,τ) ∈_2 |σ, τ∈_1}. 
By induction, 
each σ appearing in such a pair (σ,τ) is eventually free in _1, since any 2-simplex ψ∈_1 that is a coface of σ other than τ must appear in a pair (ϕ,ψ) ∈_12 by the definition of _12 and the assumption that ϕ is eventually free through the gradient _2.
Thus,  collapses to a complex that contains no 2-simplices of either _1 or _2, as claimed.




 §.§ Approximation algorithms


An α-approximation algorithm for an optimization problem is a polynomial-time algorithm that, for all instances of the problem, produces a solution whose value is within a factor α of the value of an optimal solution. The factor α
is called the approximation ratio of the algorithm. An approximation preserving reduction is a procedure for transforming an optimization problem A to an optimization problem B, such that an α-approximation algorithm for B implies an h(α)-approximation algorithm for A, for some function h. Then, if A is hard to approximate within factor h(α), the reduction implies that B is hard to approximate within factor α.

We will use a particular important and well-studied class of approximation preserving reductions, called L-reductions, which provide a simple and effective tool in proving hardness of approximability results <cit.>. 
To give the definition, consider a maximization problem A 
with a non-negative integer valued objective function m_A.
Given an instance x of A, the goal is to find a solution y (among a finite set of feasible solutions) maximizing the
objective function m_A(x,y). Define (x) as
the maximum value of the objective function on input x.   

An L-reduction
from one optimization problem A to another optimization problem
B is a pair of functions f and g that are computable in polynomial
time and satisfy the following conditions:


  * The function f maps instances of A to instances of B.

  * There is a positive constant μ such that, for all instances x of A, 
    (f(x))≤μ (x) .


  * The function g maps instances of A and solutions of B to solutions of A.

  * There is a positive constant ν such that, for any instance x of A and any solution y of f(x), we have

    (x) - m_A(x,g(x,y)) ≤ν( (f(x)) - m_B(f(x),y) ) .


If μ=ν=1, the reduction is strict.

We will use the following straightforward fact about L-reductions for proving hardness of approximation bounds. 
 If there is an L-reduction with parameters μ and ν from a maximization problem A to another maximization problem B, and there is a (1-δ)-approximation algorithm for B,
then there is a (1-μνδ)-approximation algorithm for A.




 §.§ Acyclic subgraphs


We recall some concepts and problems from graph theory that will be used in our reductions. A directed graph  with vertex set  and edge set 
is written as =(,). 
A directed graph is called an oriented graph if no pair of vertices is connected by an anti-parallel pair of edges.
In other words, an oriented graph is a directed graph without 2-cycles or loops.
Note that in contrast to a general directed graph, an oriented graph always has a simple underlying undirected graph, which is therefore a simplicial complex. We will be making use of this fact in <ref>. 

The problem of finding the maximum acyclic subgraph () of a given directed graph =(,) consists of determining a maximum subset _𝑚𝑎𝑥⊆ for which the subgraph _𝑚𝑎𝑥=(,_𝑚𝑎𝑥) has no directed cycles. A feedback arc set is a set of edges whose removal leaves a directed acyclic graph. A minimum feedback arc set is a feedback arc set of minimum cardinality. The problem of finding such a set is thus complementary to .

A directed degree-3 graph is a directed graph with total degree (indegree plus outdegree) at most 3. 
The restriction of the problem to directed degree-3 graphs is denoted by .
Moreover, the problem restricted to oriented graphs is denoted by , and the restriction to oriented degree-3 graphs is denoted by .

We will show that there is a L-reduction from to , allowing us to consider only oriented graphs later.



There is a strict reduction
from to ,
and from to .



The map f transforming an instance of (a directed graph ) to an instance of (an oriented graph f()) is given by removing from  all loops and all pairs of anti-parallel edges.
Furthermore, the map g transforming a solution of for the instance f() (an acyclic subgraph  of f()) to a solution of for the instance  (an acyclic subgraph = g(,) of ) is given as follows: 
Extend the acyclic graph  to a subgraph  of  by adding for each anti-parallel pair of edges in  one edge whose orientation is consistent with the partial order induced by . By construction, the subgraph  is still acyclic.

Let e be the number of edges in , let k be the number of pairs of anti-parallel edges in , and let a be the number of edges in . Then the number of edges in  is a+k. On the other hand, any acyclic subgraph  of  restricts to an acyclic subgraph of f() by removing at most k edges.
Thus we have

    m_(,g(,))    = m_(f(),) + k, 
    ()    = (f()) + k
    and thus (f()) ≤() and() - m_(,g(,))    = (f()) - m_(f(),),

establishing a strict reduction from to .
The same construction restricts to a strict reduction from to .


We state a few known hardness of approximation results for and related problems.
  It is NP-hard to approximate to within (1-1/126)+ϵ for any ϵ>0.


Moreover, the following result establishes hardness with respect to the unique games conjecture (UGC) <cit.>.  
A problem is said to be UGC-hard (or UG-hard) if the unique games conjecture implies that the problem is NP-hard.
We refer to <cit.> for a detailed account on this conjecture.

  Let δ∈ (0, 1/2). If for any directed graph G with an acyclic subgraph consisting of a fraction (1-δ) of its edges, one can efficiently find an acyclic subgraph of G with more than (1/2 + δ) of its edges, then the UGC  is false.
In particular, it is UGC-hard to approximate within a factor of 1/2+δ for any δ>0.


 By <ref>, the same is true for . Moreover, Newman <cit.> established an approximation preserving reduction from to , with the following consequence:

 For any constant ϵ>0, if there exists a ((1 - 1/18)+ϵ)-approximation algorithm for , then there exists a (1/2+δ)-approximation algorithm for for some constant δ>0.


From <ref>, we conclude:
 
It is UGC-hard to approximate and within a factor of (1 - 1/18)+ϵ, and NP-hard to approximate and to within (1 - 1/126)+ϵ, for any ϵ > 0.




§ HARDNESS OF APPROXIMATION OF MIN-MORSE MATCHING



In this section, we work with abstract connected simplicial complexes. Recall that an abstract simplicial complex is connected if its 1-skeleton is connected as a graph. 

 Given a pointed simplicial complex  with n simplices and some integer c>0, the amplified complex _c is defined as the wedge sum of m copies of , with m = n^c-1. 


  Given a complex  of size n and integer c, consider the amplified complex _c of . Let  be a gradient vector field on _c. Then


  * _c is collapsible if and only if  is collapsible. 

  * If  is not collapsible, then  has more than n^c-1 critical simplices.
 

 Suppose that the complex  is collapsible. Then there exists a gradient vector field _ with a unique critical simplex q∈. Let p be an arbitrarily chosen distinguished vertex of  that will be used to construct amplified complex _c. Using <ref>, without loss of generality the vector field _ has p as its unique critical simplex. Now the gradient vector field on _c, say , is simply the gradient vector field _ repeated on each identical copy of . Since p is the unique critical simplex of  on _c, we conclude that _c is collapsible. 

Conversely, suppose that the complex _c is collapsible. Then, by <ref>, we can obtain a gradient vector field  on _c with the distinguished vertex p as its unique critical simplex. If we consider the gradient vector field  restricted to any one of the copies of _c, it follows immediately that  is collapsible.

Now suppose that  is not collapsible and  has less than or equal to n^c-1 critical simplices. By <ref>, without loss of generality we may assume that  has the distinguished vertex p as the unique critical 0-simplex. Now consider  restricted to each of the individual copies of . Then clearly at least one of the copies has p as its unique critical simplex (else we would have more than n^c-1 critical simplices in total). But this immediately implies that  is collapsible, a contradiction. Hence, if  is not collapsible, then   has more than n^c-1 critical simplices.


  For any ϵ∈ (0,1], if there exists an O(n^1-ϵ)-factor approximation algorithm for , where n denotes the number of simplices of an input simplicial complex, then there exists a polynomial time algorithm for deciding collapsibility of simplicial complexes.

 Given any ϵ∈ (0,1], suppose there exists an O(n^1-ϵ)-factor approximation algorithm for . Specifically, there exist p, M>0 such that for all n ≥ M, the approximation ratio is bounded above by p n^1-ϵ.  
Now choose c to be the smallest positive integer with the property 1/c < ϵ, i.e., c = ⌊1/ϵ + 1 ⌋. Consider an arbitrary connected complex  with n simplices and construct the amplified complex _c. Note that the total number of simplices in _c is n̂ = ( n - 1 ) n^c-1 + 1 = n^c - n^c-1 + 1.
Also, if  n < max{M,p^1/1+cϵ}, i.e., if n is bounded by a constant, the collapsibility of  can easily be checked in constant time. So, without loss of generality, we assume that n ≥max{M,p^1/1+cϵ}.

We now use the following Algorithm B to decide collapsibility of the complex . We execute the O(n^1-ϵ)-factor approximation Algorithm A for on the amplified complex _c. If the number C_A of critical simplices returned by Algorithm A is less than n^c-1, we report that the complex  is collapsible, else we declare that  is not collapsible.

When the complex is collapsible, the number C_A of critical simplices returned by Algorithm A can be bounded as follows:

    C_A  ≤   p n̂^1-ϵ <  p(n^c)^1-ϵ≤  n^c-1 .

The bound C_A < n^c-1 for a collapsible complex  with n simplices, along with part (ii) of Lemma <ref>, establishes the correctness of Algorithm B for determining collapsibility of the complex . Also, since n̂ <  n^c, Algorithm B runs in time polynomial in n.
 

Recently, Tancer <cit.> proved the following theorem about
collapsibility of 3-complexes.

  It is NP-complete to decide whether a given 3-complex is collapsible.


  For any ϵ∈ (0,1], there exists no O(n^1-ϵ)-factor approximation algorithm for , where n denotes the number of simplices of an input simplicial complex, unless P = 𝑁𝑃.




§ HARDNESS OF APPROXIMATION FOR MAX-MORSE MATCHING



In this section, we describe an L-reduction from to , establishing hardness of approximation for . Our construction is based on a modification of Zeeman's dunce hat <cit.>. The dunce hat is a simplicial complex which is contractible but has no free faces and is therefore not collapsible. 
In contrast, the modified dunce hat is collapsible but only through a single free face. 
The triangulation is given in <ref>. An equivalent triangulation has been described by Hachimori <cit.>. Its number of simplices is minimal among all complexes that are collapsible through a single free face, as can be verified by an exhaustive search <cit.>. The 1-simplex ω is the unique free face of the modified dunce hat .



For the remainder of the section, we will use the following notation: For a graph =(,), the indegree of a vertex v, in , is denoted v, and its outdegree is denoted v. 
We now construct a complex  from , and more generally, a complex  for any subgraph = (,) of .
Throughout this section, the graph  denotes an oriented connected degree-3 graph. Note that the connectedness assumption is not a restriction for the problem.

In order to aid the reader's intuition, we first outline the motivation behind some of the design choices for the gadget, before giving the formal description. 
Our aim is to construct a complex   so that there is a one-to-one correspondence between the cardinality of a (minimum) feedback arc set (<ref>) and the (minimum) number of simplices that need to be removed from  to make it erasable. 
To this end, we start with a disjoint union of copies of , one for each edge e∈, and make identifications of vertices to obtain a complex  which is homotopy equivalent to the undirected graph underlying .
However, we make additional identifications of edges to ensure that any subcomplex , corresponding to a subgraph , collapses to a 1-dimensional complex isomorphic to the undirected graph underlying  if and only if  is acyclic.
In order to obtain an L-reduction, we ensure that the size of the complex  is linear in size of graph .

We now describe the construction of the complexes  and  for an oriented degree-3 graph , by classifying the vertices of  into five types.



  * Consider an arbitrary
total order ≺ on the edge set  of .

  * Start with a disjoint union of copies of , one for each edge e∈, denoted by _e.

  * Using the pasting map construction as defined in <ref>, construct the complex  by identifying some of the distinguished simplices of each gadget
_e based on the following rules, as applied to each vertex v∈_ according to its indegree and outdegree:




  * For every vertex v∈
with v=v=0, no identifications are made.


  * For every vertex v∈
with v=0 and v>0, identify all 0-simplices s_e for every
outgoing edge e ∈. 


  * For every vertex v∈
with v=0 and v>0, identify all 0-simplices t_e for
every incoming edge e ∈. 


  * For every vertex v∈
with v=1, v=2, v>0 and v>0,
let k and l denote the outgoing edges of v in , with k ≺ l, and let j
denote the incoming edge of v in .


  * If j,k ∈, 
identify the 1-simplices ϕ_j∼ω_k such that the incident 0-simplices are identified as
u_k∼ v_j and s_k∼ t_j. 

  * Similarly, if j,l ∈, identify ψ_j∼ω_l such that u_l∼ w_j
and s_l∼ t_j.



  * For every vertex v∈
with v∈{1,2}, v=1, v>0 and v>0,
let k (and possibly l, with k ≺ l) denote the incoming edges of v in ,
and let j denote the outgoing edge of v in .


  * If j,k ∈, 
identify the 1-simplices ω_j∼ϕ_k such that u_j∼ v_k
and s_j∼ t_k.

  * (Similarly, 
if j,l ∈, identify ω_j∼ϕ_l such that u_j∼ v_l
and s_j∼ t_l.)




  * Furthermore, we define () = (,).



We choose an arbitrary linear order since there is no natural choice to determine some of the attachments in the construction. Using an (arbitrarily chosen) linear order on the edge set  of   allows us to make the construction of complexes  explicit and concrete. While it is clear that different linear orders on the edge set  may result in different complexes, the hardness results in this section do not depend on the choice of the linear order ≺. 



Since  is an oriented graph, it is easy to verify that  is a simplicial complex. Also, by construction,  is a subcomplex of  whenever  is a subgraph of .


  From <ref>, we observe that for a modified dunce hat _e, ψ_e is incident on exactly two 2-simplices of _e. The same holds true for ϕ_e. Also, note that ω_e is incident on a unique 2-simplex of _e, namely Γ_e.




 §.§ Structural properties of the reduction


  For a subgraph = (,) of a directed degree-3 graph  and an edge e∈:


  * If ω_e is eventually free in , then _e is erasable in  . 

  * If _e is erasable in  through a gradient , then ( ω_e, Γ_e   ) is a gradient pair in . 
If f is a discrete Morse function with gradient , then for any simplex σ∈_e such that σ∉{ω_e, Γ_e } we have f(ω_e) > f(σ).  
        
          
 Suppose ω_e is eventually free in . Then there exists a subcomplex  of  such that ↘ and ω_e is free in .
Note that, by construction of , this implies that _e is a subcomplex of .
Now using the gradient specified in <ref>
all the 2-simplices of _e can be collapsed, making _e erasable in . This proves the first statement of the lemma. The second statement of the lemma immediately follows from observing that ω_e is the unique free 1-simplex in complex _e, Γ_e is the unique coface incident on ω_e, and _e is erasable in  through the gradient  of f.   
         

  For a subgraph  of a directed degree-3 graph  and a vertex v ∈ with v = l > 0 and outgoing edges { f_1,…, f_l }∈, we have:


  * If v = 0, then each ω_f_j is free in .

  * If v = k>0, let { e_1,…, e_k }∈ be the set of incoming edges of v. If there is a gradient  such that each ω_e_i is eventually free in  through , then each ω_f_j is eventually free in  through  as well.


 If v = 0, then each ω_f_j is free by construction of .
Now suppose that v = k>0 and each ω_e_i is eventually free in .  
From Remark <ref> and from the construction of the complex , it can be deduced that for any edge f_j, the only 2-simplices incident on ω_f_j in the complex  are Γ_f_j and one pair of 2-simplices of _e_i for each e_i.
By assumption, each ω_e_i is eventually free, and so by part (i) of <ref>, each _e_i is erasable. Hence, by <ref>, their union is erasable too. This means that
 collapses to a complex  
in which each ω_f_j is free, proving the claim.
 

  A subgraph  of a directed degree-3 graph  is acyclic if and only if the corresponding complex  is erasable. 
 Suppose that the given subgraph  of , with n vertices , is acyclic. Consider an arbitrary total order on the vertices of  consistent with the partial order induced by the edges in , and index the vertices {v_1,v_2,…,v_n} according to this total order. 
We can now apply Lemma <ref> and part (i) of Lemma <ref> inductively for all v_i from v_1 to v_n-1 to establish the erasability of _f_j for each of the outgoing edges f_j of v_i in . Hence, the entire complex  is erasable.

To show the reverse implication, we prove that if  has directed cycles, then  is not erasable. Assume for a contradiction that  is erasable through a gradient , and let f be a discrete Morse function with that gradient.
Let a,b be two consecutive edges in a directed cycle of .
Then, by construction of , either ϕ_a ∼ω_b or ψ_a ∼ω_b, and so by part (ii) of <ref> we have f(ω_a) > f(ω_b). Applying this argument to each pair of consecutive edges in the cycle yields a contradiction.
Hence, if  has directed cycles, then  is not erasable.


  For any edge e∈(), the subcomplex 
_e ∖{Γ_e} is erasable in .

 
Consider the discrete gradient specified in <ref> as a gradient _e on _e ⊆.
First note that _e ∖{Γ_e} is erasable in _e through the gradient _e ∖{(ω_e,Γ_e)}.
Moreover, all 1-simplices of _e that are paired in _e with a 2-simplex do not appear in _c for any edge c ≠ e.
It follows that _e ∖{Γ_e} is erasable in  .


 Let  be a set of 2-simplices such that ∖ is erasable, and let = { f∈|∩_f ≠∅}. Then  is a feedback arc set of .

 Each 2-simplex σ∈ lies in _f for a unique f∈, which implies f∈. 
In particular, σ∈ implies σ∉_e for any e ∈∖. 
Now consider the subgraph = (, ∖) of .
Then ⊆∖ is erasable, since any subcomplex of an erasable complex is easily seen to be erasable. 
Hence, by Lemma <ref>,  is acyclic, i.e.,  is a feedback arc set of .


  Given an oriented degree-3 graph  and the corresponding complex , = ().

 Given a graph = (,), let ⊆ be a minimum feedback arc set of , and let =(,∖) be the corresponding maximum acyclic subgraph. We construct a new complex ^' from  as follows: For every f ∈, we remove {Γ_f} from _f ⊆ and erase _f ∖{Γ_f} in  using Lemma <ref>. 
Note that (∖{Γ_f | f ∈}) ↘^'.
In order to show that ^' is erasable, it suffices to show erasability of the pure subcomplex of ^' induced by its 2-simplices. It is easy to check that the subcomplex of ^' induced by the 2-simplices in ^' is precisely . However, from Lemma <ref>, we can deduce that  is erasable. This implies that ^' is erasable, and hence (∖{Γ_f | f ∈}) is erasable. Since the total number of 2-simplices that were removed to erase  is equal to | | = (), we have established that ≤().

Now assume for a contradiction that < (). Let  be a minimal set of 2-simplices that need to be removed to erase , i.e., || =. Let ^' = { f ∈|∩_f ≠∅}. By Lemma <ref>, the graph (,∖^') is acyclic and ^' is a feedback arc set. Since each 2-simplex lies in _e for some unique e∈, it follows that 
|^'| ≤||.
We conclude that
|^'| < (), which contradicts the minimality of (). Hence, the claim follows.


In order to relate the homotopy type of  with that of , we construct a new complex  as follows:


  * Start with a disjoint union of copies of , one for each edge in , denoted by _e.

  * Similar to the construction of , the complex  is constructed by identifying some of the distinguished vertices of each gadget _e based on the following rules, as applied to each vertex of  based on its indegree and outdegree:

	
  * For every vertex of  that has incoming as well as outgoing edges, identify s_j with t_i for every incoming edge i  and outgoing edge j of .
	
  * For every vertex of  that has only incoming edges, identify all 0-simplices t_e for every incoming edge e.
	
  * For ever vertex of  that has only outgoing edges, identify all 0-simplices s_e for every outgoing edge e.



 
 is homotopy equivalent to .


Comparing the two constructions, first note that  can be obtained from  by further identifying certain 1-simplices ϕ_e ∼ω_f or ψ_e ∼ω_f (together with vertices v_e ∼ u_f or w_e ∼ u_f) in subcomplexes _e,_f ⊆, where these two 1-simplices already have a common vertex by the identification t_e ∼ s_f in the construction of , and are otherwise not connected by another 1-simplex. 
In both  and , the union of the two 1-simplices is contractible, and so each complex is homotopy equivalent to the space that further identifies each such pair of 1-simplices to a single point <cit.>. The claim follows.


   collapses to the undirected graph underlying . 

 First note that ω_e is free in  for each e in . Moreover, the only simplices that are possibly shared by gadgets _i and _j for i ≠ j are the vertices s and t of _i and _j. Therefore, we can use the gradient vector field depicted in Figure <ref> to collapse each gadget _e to the 1-simplex η_e together with the vertices s_e and t_e. 
Thus,  collapses to the subcomplex   of  induced by these 1-simplices.
By construction of , this complex  is isomorphic to the undirected graph underlying .


 
 is homotopy equivalent to the undirected graph underlying . 




 §.§ Inapproximability results


Given an oriented connected degree-3 graph =(,) and the corresponding complex , let  denote the optimal value of the problem on , and let  denote the optimal value of the problem on .

We now describe an L-reduction from to .
The map : ↦() transforms instances of
(directed graphs) to instances of (simplicial complexes). 
The map 
that transforms solutions of (discrete gradients  on ) to solutions of (acyclic subgraphs (,)) is defined as follows:
Let 
    .

By Lemma <ref>,  is a feedback arc set.
The corresponding solution (,) for is then simply the subgraph of  with edges ∖. 
The value of the objective function  is the number of regular simplices in ; the value of the objective function   is the number of edges of the acyclic subgraph, |∖|.

For a discrete gradient  on , let n denote the number of simplices in , let m denote the total number of critical simplices in , and let m_d denote the number of critical simplices in dimension d. Also, let β_d denote the Betti number of  in dimension d, and let β be the sum of all Betti numbers. 

  With the above notation,

    ≤ n - 2  m_2 - β  and  ≥ || - m_2.

 

 By the Morse inequalities <cit.>, we have m_0 ≥β_0 and

    m_2 - m_1 + m_0 = β_2 - β_1 + β_0 .

From <ref>, we have β_0=1 and β_2= 0.
This gives us:

    m_1 = β_1 + m_2 + (m_0 - β_0).

Moreover, 

    m     = m_2 + m_1 + m_0       (by definition)
        =  2  m_2 + β_1 + 2  m_0 -β_0       (from Equation (<ref>))
        = 2  m_2 + β + 2 (m_0 -β_0)       (since β_2 = 0)
       ≥ 2  m_2 + β      (since m_0 ≥β_0).

Hence, = n - m ≤ n - 2  m_2 - β.

In the construction of the acyclic subgraph (,), 
for every critical 2-simplex in , we remove at most one edge in . Hence, we conclude that ≥ || - m_2.


 Given a graph  and the corresponding complex , 

    = n -  2  - β = n - 2 () - β .

   
 
First note that for an optimal gradient vector field on , we have m_0 = 1 and m_2 =.
The first equality now follows by observing that in the proof of Lemma <ref>, equality = n - 2  m_2 - β is obtained for β_0 = m_0. The second equality follows immediately follows from Proposition <ref>.


 ≤ 78.
    

For the Max-Acyclic Subgraph problem, from the trivial 1/2-factor approximation algorithm mentioned in <cit.>, one knows that it is always possible to find an acyclic subgraph _ of a directed graph  that contains at least half the number of edges in . Clearly, this bound continues to hold when the class of graphs is restricted to degree-3 oriented graphs. This gives the following inequality:

    ≥/2 .
 

First note that the number of simplices in the modified dunce hat  is 7+19+13=39. 
The complex  described in <ref> is constructed from a disjoint union of  copies of  with several simplices identified, giving us

    n ≤ 39  .

From <ref> we obtain the bound

    ≤ n  ≤  39 ≤ 78   .



 

    (  - ) ≤1/2(  - ) .


 By definition, =  - (). By Lemma <ref>, 
    ≥ || - m_2.
 Hence,

    (  - ) ≤ m_2 - () .

Using Lemma <ref> and Lemma <ref>, we obtain

    (  - ) ≥ 2 (m_2 - ()) .

Substituting Equation <ref> in Equation <ref>, we obtain the lemma.


 It is NP-hard to approximate within a factor of (1 - 1/4914)+ϵ and UGC-hard to approximate it within a factor of (1 - 1/702)+ϵ, for any ϵ>0.

 From Lemma <ref> and Lemma <ref> we conclude that the reduction from to is an L-reduction with parameters μ=78 and ν=1/2. By Theorem <ref>, if there exists a ( 1 - 1/μνδ + ϵ)-approximation algorithm for , then there exists a  (1 - δ + μνϵ)-algorithm for . Using Corollary <ref>, we choose δ = 1/126 to deduce that it is NP-hard to approximate within a factor of (1 - 1/4914)+ϵ,
and choose δ = 1/18 to deduce that it is UGC-hard to approximate within a factor of (1 - 1/702)+ϵ.




§ CONCLUSION & DISCUSSION
 

In this paper, we provide the first hardness of approximation results for
the maximization and the minimization variants of the Morse matching
problems. 

While we established a hardness result for Min-Morse Matching on simplicial complexes
of dimension d≥3, the question
of hardness of approximation for Min-Morse matching for 2-dimensional
simplicial complexes remains open. We will address this question in future work.

For the Max-Morse Matching problem on d-dimensional simplicial complexes, although our work clears a major hurdle of going beyond NP-hardness, a gap remains between the best approximability and inapproximability bounds. The best known approximation algorithm for Max-morse matching on simplicial complexes yields an approximation ratio of  d+1/d^2+d+1 <cit.>. We believe that our result and techniques will pave way for further work in improving the gap, and in placing Max-Morse Matching in the right kind of approximation-algorithms related complexity class. In particular, devising an approximation algorithm for Max-Morse Matching with an approximation factor independent of the dimension of the complex, or establishing a hardness of approximation result for Max-Morse Matching that is dependent on the dimension is a challenging open problem.
 

 We close the discussion with some additional open problems. 
 Note that the complex  employed in the hardness result for Max-Morse Matching described in <ref> is not a manifold. Hence, the question of hardness of approximation for Max-Morse Matching on simplicial manifolds is open. The best known approximation algorithm for Max-Morse Matching on d-dimensional simplicial manifolds has approximation factor 2/d <cit.>. 
 
 Finally, we also leave it as an open question to investigate sharper inapproximability bounds for Max-Morse Matching on regular cell complexes.




	