Treffer: On the Complexity of Computing a Maximum Acyclic Matching in Undirected Graphs

The problem of finding a maximum acyclic matching in a simple undirected graph is known to be NP-complete. In this paper, we present new results; we show that a maximum acyclic matching in a given undirected graph (with n vertices and m edges) can be computed recursively with a recursion depth O(lnm) in expectation. Consequently, employing a recursive computation of a maximum acyclic matching in a given graph, if the recursion depth meets the expectation O(lnm), then a maximum acyclic matching can be computed in time O(n3.4) and space O(mlnm). However, for the general case, the complexity of the recursive computation of a maximum acyclic matching is in O(n22m) time and in O(m2) space.