Approximation algorithms for Max Morse matching (Q2362103)

The authors deal with the Max Morse matching problem (MMMP). In the problem we have a Hasse graph \(H_K\) of a simplicial complex \(K\) whose edges are all directed from a simplex to its lower dimensional facets. We associate a matching induced orientation to \(H_K\) such that the resulting oriented graph is acyclic. The goal in the MMMP is to maximize the cardinality of matched (regular) nodes. In the paper the authors describe a \((D+1) / (D^2 + D +1)\)-factor approximation algorithm for the MMMP on \(D\)-dimensional simplicial complexes. The algorithm uses maximum-cardinality bipartite matching on the Hasse graph to orient it. Then it uses a BFS-like traversal of the oriented Hasse graph to classify matching edges as either forward or backward edges. To prove the approximation bound that holds for manifold and non-manifold complexes a counting argument is used. Next, the authors propose two approximation algorithms for simplicial \(D\)-manifolds. The first approximation algorithm provides a ratio of \(2 / (D+1)\) for \(D \geq 3\) and next the ratio is improved to \(2 / D\) for \(D \geq 5\) using a refinement that specifies the order in which the graph is processed. This leads to \(1/2\)- and \(4/9\)-factor approximation for \(3\)- and \(4\)-manifolds, respectively. To show the effectiveness of the proposed algorithms the authors compare the Java implementation of these algorithms with three other algorithms.